Start Time：2017-07-15 12:00:00 End Time：2017-07-15 15:46:00 

A -- 计算几何你瞎暴力

Time Limit：5s Memory Limit：256MByte

Submissions：1764Solved：348

DESCRIPTION

今天$\mathrm{HHHH考完了期末考试,他在教学楼里闲逛,他看着教学楼里一间间的教室,于是开始思考:}$

如果从一个坐标为 $(x1,y1,z1)(x1,y1,z1)的教室走到(x2,y2,z2)(x2,y2,z2)的距离为\; |x1-x2|+|y1-y2|+|z1-z2||x1-x2|+|y1-y2|+|z1-z2|$

那么有多少对教室之间的距离是不超过$\mathrm{RR的呢?}$

INPUT

第一行是一个整数

$\mathrm{T(1\le T\le 10)T(1\le T\le 10),\; 表示有TT组数据\; 接下来是TT组数据,对于每组数据:\; 第一行是两个整数n,q(1\le n\le 5\times 104,1\le q\le 103)n,q(1\le n\le 5\times 104,1\le q\le 103),\; 表示有nn间教室,\; qq次询问.\; 接下来是nn行,\; 每行3个整数xi,yi,zi(0\le xi,yi,zi\le 10)xi,yi,zi(0\le xi,yi,zi\le 10),表示这间教室的坐标.\; 最后是qq行,每行一个整数R(0\le R\le 109)R(0\le R\le 109),意思见描述.}$

OUTPUT

对于每个询问

$\mathrm{RR输出一行一个整数,表示有多少对教室满足题目所述的距离关系.}$

SAMPLE INPUT

1 3 3 0 0 0 1 1 1 1 1 1 1 2 3

SAMPLE OUTPUT

1 1 3

HINT

对于样例,1号教室和2号教室之间的距离为3, 1号和3号之间的距离为3, 2号和3号之间的距离为0

SOLUTION

这道题就是要暴力，不过一般的暴力是要出问题的，因为数组你要开的特别大。所以我想FFT去做，可是不存在的啊，怎么做的出来

${\mathrm{xi,yi,zi(0\le xi,yi,zi\le 10)xi,yi,zi(0\le xi,yi,zi\le 10),这个是真的骚，所以就是10^6了，具体实现如下}}^{}$

#include 
       
        using namespace std;typedef long long LL;int M[11][11][11];LL N[32];int main(){int t;cin>>t;while(t--){    memset(M,0,sizeof(M));    memset(N,0,sizeof(N));    int n,q;    cin>>n>>q;    for(int i=0;i
        
         >x>>y>>z;        M[x][y][z]++;    }    for(int i=0;i<11;i++)    for(int j=0;j<11;j++)    for(int k=0;k<11;k++)    for(int l=0;l<11;l++)    for(int m=0;m<11;m++)    for(int n=0;n<11;n++){        if(i==j&&k==l&&m==n)        N[0]+=M[i][k][m]*1LL*(M[i][k][m]-1);        else        N[abs(j-i)+abs(l-k)+abs(n-m)]+=M[i][k][m]*1LL*M[j][l][n];    }    LL f=0;    for(int i=0;i<31;i++){        N[i]+=f;        f=N[i];    }    while(q--){        int p;        cin>>p;        if(p>30)            cout<
        
       

C -- 图论你先敲完模板

Time Limit：5s Memory Limit：256MByte

Submissions：786Solved：201

DESCRIPTION

今天$\mathrm{HHHH在操场上跑步,HHHH作为一个爱运动的人,肯定会想方设法把跑步所消耗的能量减到最少.}$

现在这个操场上有$\mathrm{nn个可以休息的点,他们的坐标分别为x1,x2...xn(xi\le xi+1)x1,x2...xn(xi\le xi+1),HHHH刚开始在\; x1x1\; ,并且他只能在这些点休息,在中途不能停下来,否则会因为旁边的音浪太强而被晃到.}$

如果$\mathrm{HHHH连续跑一段长度为ll的距离,那么他将会消耗2l+a2l+a的能量(aa为HHHH的可爱值)}$

现在给你这些点的坐标,请帮$\mathrm{HHHH计算他跑到xnxn点所需要消耗的能量最少是多少.}$

INPUT

第一行是一个整数

$\mathrm{T(1\le T\le 10)T(1\le T\le 10),表示有TT组数据\; 对于每组数据输入一行2个整数n,a (1\le n\le 105,1\le a\le 106)n,a (1\le n\le 105,1\le a\le 106)\; 表示总共有nn个休息点,HHHH的可爱值为aa.\; 接着一行nn个数x1,x2...,xn(0\le xi\le 3\times 106,0\le xi+1-xi\le 30)x1,x2...,xn(0\le xi\le 3\times 106,0\le xi+1-xi\le 30),表示点的位置.}$

OUTPUT

每组数据输出一行,一个整数,表示最小需要花费的体力

SAMPLE INPUT

2 3 2 3 5 7 3 10 3 5 7

SAMPLE OUTPUT

12 26

HINT

对于第一组样例,最少的体力消耗是先从3跑到5,消耗6点体力,再从5跑到7,消耗6点体力,共12点 对于第二组样例,最少的体力消耗是直接从3跑到7,消耗26点体力.

SOLUTION

图论个皮皮虾啊，分明就是dp，

d[i]=min(d[j]+2xi−xj+a)，

而且t=2xi−xj增长相当快,而答案显然不超过1e5∗2^30,

#include 
         
          using namespace std;typedef long long ll;ll a[100005],dp[100005];int main() {    int t,n,m;    scanf("%d",&t);    while(t--) {        scanf("%d%d",&n,&m);        for(int i=1; i<=n; i++)            scanf("%lld",&a[i]);        dp[1]=0;        for(int i=2; i<=n; i++) {            dp[i]=1e18+10;            ll l=0;            for(int j=i-1; j>=1; j--) {                l+=a[j+1]-a[j];                if(l<=40)                    dp[i]=min(dp[i],dp[j]+((1ll)<
         

 

B -- 数论你还会快速幂

Time Limit：5s Memory Limit：256MByte

Submissions：539Solved：122

DESCRIPTION

今天$\mathrm{HHHH在学数论,他看到一个很优美的式子:}$

${\sum ni=1ik mod p\sum i=1nik mod p}^{}$

一向热衷于抱队友大腿的$\mathrm{HHHH便问队友ZZZZ怎么做}$

$\mathrm{ZZZZ:"n,kn,k多大?"}$

$\mathrm{HHHH:"105,105105,105"}$

$\mathrm{ZZZZ:"快速幂嘛"}$

$\mathrm{HHHH:"109,105109,105"}$

$\mathrm{ZZZZ:"拉格朗日插值嘛"}$

$\mathrm{HHHH:"1018,10181018,1018"}$

队友:"让我想想.."

INPUT

第一行是一个整数

$\mathrm{T(1\le T\le 1000)T(1\le T\le 1000),表示有TT组数据\; 对于每组数据输入一行3个整数n,k,p(1\le n\le 1018,0\le k\le 1018,1\le p\le 1018,0\le n-p\le 100)n,k,p(1\le n\le 1018,0\le k\le 1018,1\le p\le 1018,0\le n-p\le 100)且模数\; pp\; 是质数,}$

OUTPUT

对于每组数据输出题目中的表达式的值

SAMPLE INPUT

2 5 2 3 7 2 3

SAMPLE OUTPUT

1 2

HINT

对于第一组样例我们有

${\mathrm{12+22+32+42+52=1(mod3)12+22+32+42+52=1(mod3)\; 对于第二组样例我们有\; 12+22+32+42+52+62+72=2(mod3)12+22+32+42+52+62+72=2(mod3)}}^{}$

SOLUTION

快速幂加快速乘法，骚操作，这个快快速幂还好，这个快速乘法是真的骚

#include 
          
           using namespace std;typedef long long LL;LL p, k;LL quick_mul(LL x,LL y,LL MOD) {    x = x%MOD,y = y%MOD;    return ((x*y-(LL)(((long double)x*y+0.5)/MOD)*MOD)%MOD+MOD)%MOD;}LL quick_Mod(LL x, LL n) {    LL ans = 1;    while(n) {        if(n&1) {            ans = quick_mul(ans, x, p);        }        x = quick_mul(x, x, p);        n >>= 1;    }    return ans;}int main() {    LL n;    int t;    scanf("%d", &t);    while(t--) {        scanf("%lld%lld%lld", &n, &k, &p);        if(k==0) {            printf("%lld\n",n%p);            continue;        }        LL ans = 0;        if(k%(p-1) == 0) {            ans = (ans + quick_mul(p-1, n/p, p))%p;        }        n %= p;        for(LL i = 1; i <= n; i++) {            ans = (ans + quick_Mod(i, k))%p;        }        printf("%lld\n", ans);    }    return 0;}