T1.随

　　看题第一眼，就瞄到最下面 孙金宁教你学数学  ？？？？？原根？目测神题，果断跳过。

　 最后打了个快速幂，愉快的收到了达哥送来的10分。

　　实际上这题暴力不难想，看到一个非常小的mod应该就能想到复杂度与mod有关，然后dp式子也挺显然的。

　　比较神的是最后的优化，我们用 f[i][j]表示经过i次操作，最终%mod后与原根的j次方同余的方案数，然后，之前的转移

　　f[i][j*k%mod]=f[i-1][j]*sum[k](sum[k]为k在n个数中出现的次数) 就变成了f[ i ] [ ( j + k ) % ( mod-1 ) ]=f[i-1][j]*sum[k];

　　那么这有什么卵用呢，原来的转移矩阵变成了循环矩阵，于是乎就可以mod^2乘一次。

　　另外，对于这道题，原根没有必要O（mod^1/4）求，mod^2暴力就行。。。

　　总复杂度O（mod^2logm）.

　　数据差评，没有80分算法

 

1 #include
      
        2 #define p 1000000007 3 using namespace std; 4 int n,m,mod,a,sum[1005],yuan,ys[1005],yx[1005]; 5 long long b[1000][1000],aa[1000],c[1000],d[1000]; 6 bool v[1000]; 7 inline void cheng() 8 { 9     for(int i=1;i
       
        >=1;40     }41     return ans;42 }43 int main()44 {45     scanf("%d%d%d",&n,&m,&mod);46     for(int i=1;i
        
         >=1;80     }81     for(int i=1;i
        
       
      

 

T2.单

　　这也是一道很帅的题，首先对于t=0的操作，令sum为所有节点的权值之和，我们首先进行暴力求出b[1]的值，然后对于其他节点，我们可以进行换根：

　　b[x]=b[fa]-siz[x]+(sum-siz[x]);这个式子比较显然。于是30分到手。

　　对于t=1的操作，我们把上面那个式子变一下就可以得到2*siz[x]=b[fa]-b[x]+sum。也就是说，我们只要求出sum的值，就可以求出所有的a。

　　考试的时候就死在了这里，发现不会求sum，不同与其他人的高斯消元，我采取了一种更为sha diao的做法：枚举sum值，代进去看能不能成立。。。。。由于题中有a[i]<=100的限制，所以sum不会很大，理论上有60分，但是不知道为啥死掉了。

　　实际上，有一个隐藏的条件：d[1]=∑siz[i] (2<=i<=n)，然后我们将上面那个式子x=2到x=n的情况全都写下来相加，将前面这个式子×2，再将这两部分相减，我们就会惊喜的发现：

　　sum=(∑d[fa]-d[x]-d[1]*2)/(n-1);

　　于是我们就可以愉快的ac了。

1 #include
      
         2 #define int long long  3 using namespace std;  4 int t,n,fi[1000005],ne[2000005],to[2000005],tot,a[1000005],b[1000005],sum,siz[1000005],de[1000005];  5 bool o;  6 inline void add(int x,int y)  7 {  8     ne[++tot]=fi[x];  9     to[tot]=y; 10     fi[x]=tot; 11 } 12 void dfs1(int x,int fa) 13 { 14     siz[x]=a[x];b[1]+=(de[x]-1)*a[x]; 15     for(int i=fi[x];i;i=ne[i]) 16     { 17         int y=to[i]; 18         if(y!=fa) 19         { 20             de[y]=de[x]+1; 21             dfs1(y,x); 22             siz[x]+=siz[y]; 23         } 24     } 25 } 26 void dfs2(int x,int fa) 27 { 28     b[x]=b[fa]-siz[x]+sum-siz[x]; 29     for(int i=fi[x];i;i=ne[i]) 30     { 31         int y=to[i]; 32         if(y!=fa) 33         { 34             dfs2(y,x); 35         } 36     } 37 } 38 void dfs3(int x,int fa) 39 { 40     siz[x]=(b[fa]-b[x]+sum)>>1;a[x]=siz[x]; 41     for(int i=fi[x];i;i=ne[i]) 42     { 43         int y=to[i]; 44         if(y!=fa) 45         { 46             dfs3(y,x); 47             a[x]-=siz[y]; 48         } 49     } 50 } 51 void gsm(int x,int fa) 52 { 53     for(int i=fi[x];i;i=ne[i]) 54     { 55         int y=to[i]; 56         if(y!=fa) 57         { 58             sum+=b[x]-b[y]; 59             gsm(y,x); 60         } 61     } 62 } 63 main() 64 { 65     scanf("%lld",&t); 66     while(t--) 67     { 68         tot=sum=0; 69         memset(fi,0,sizeof(fi)); 70         memset(b,0,sizeof(b)); 71         memset(a,0,sizeof(a)); 72         memset(siz,0,sizeof(siz)); 73         memset(de,0,sizeof(de)); 74         scanf("%lld",&n); 75         for(int i=1,x,y;i
       
        >o; 81         if(o) 82         { 83             for(int i=1;i<=n;i++) 84                 scanf("%lld",&b[i]); 85             gsm(1,0); 86             sum=(b[1]*2-sum)/(n-1); 87             siz[1]=sum; 88             for(int i=fi[1];i;i=ne[i]) 89             { 90                 dfs3(to[i],1); 91                 siz[1]-=siz[to[i]]; 92             } 93             a[1]=siz[1]; 94             for(int i=1;i<=n;i++) 95                 printf("%lld ",a[i]); 96             puts(""); 97         } 98         else 99         {100             for(int i=1;i<=n;i++)101                 scanf("%lld",&a[i]),sum+=a[i];102             de[1]=1;103             dfs1(1,0);104             for(int i=fi[1];i;i=ne[i])105             {106                 int y=to[i];107                 dfs2(y,1);108             }109             for(int i=1;i<=n;i++)110                 printf("%lld ",b[i]);111             puts("");112         }113     }114     return 0;115 }
       
      

T3.题

　　送分题，但我没有全部接到。。

　　对于opt=0，ans=C(n,n/2)^2;

　　对于opt=1，ans=catalan(n);

　　对于opt=2，dp即可

　　对于opt=3，枚举一个方向走的步数，ans=∑catalan(i)*catalan((n-i-i)/2)*C(n,i+i);

　　另外，求大神解释我曾经的visit题解（那两个组合数怎么解释啊）

1 #include
      
        2 #define mod 1000000007 3 using namespace std; 4 int n,k; 5 long long js[200005],ni[200005],f[2][2005][2005]; 6 inline long long qpow(long long x,long long y) 7 { 8     long long ans=1; 9     while(y)10     {11         if(y&1)ans=ans*x%mod;12         x=x*x%mod;13         y>>=1;14     }15     return ans;16 }17 inline long long c(long long x,long long y)18 {19     return js[x]*ni[x-y]%mod*ni[y]%mod;20 }21 int main()22 {23     scanf("%d%d",&n,&k);24     js[0]=ni[0]=1;25     for(int i=1;i<=n+n;i++)26         js[i]=js[i-1]*i%mod,ni[i]=qpow(js[i],mod-2);27     if(k==0)28     {29         printf("%lld\n",c(n,n/2)*c(n,n/2)%mod);30         return 0;31     }32     if(k==1)33     {34         printf("%lld\n",c(n,n/2)*qpow(n/2+1,mod-2)%mod);35         return 0;36     }37     if(k==2)38     {39         f[0][1001][1001]=1;40         for(int i=1;i<=n;i++)41         {42             f[i&1][1001][1001]=(f[(i-1)&1][1001][1000]+f[(i-1)&1][1000][1001]+f[(i-1)&1][1002][1001]+f[(i-1)&1][1001][1002])%mod;43             for(int j=1001-n;j<=1001+n;j++)44                 if(j!=1001)45                     f[i&1][1001][j]=(f[(i-1)&1][1001][j-1]+f[(i-1)&1][1001][j+1])%mod;46             for(int j=1001-n;j<=1001+n;j++)47                 if(j!=1001)48                     f[i&1][j][1001]=(f[(i-1)&1][j-1][1001]+f[(i-1)&1][j+1][1001])%mod;49         }50         cout<
       
        <