又考崩了咕咕咕。。。
T1:随 好题标记
前置芝士：
原根：质数P的原根g满足1<=rt<P,且rt的1次方,2次方…(P-1)次方在模P意义下可以取遍1到(P-1)的所有整数。
欧拉定理：对于质数P,1<=x<P的任意x的P-1次方在模P意义下都为1。
显然,原根的1次方,2次方…（P-2）次方在模P意义下都不为1,只有(P-1)次方在模P意义下为1.这也是一个数成为原根的充分必要条件。
x^b≡x^(b%φ(p)) (%p)
考虑到这道题的m很大，但状态具有传递性，用倍增算法。
设状态f[i][j]表示选了i波后为原根的j次方的方案总数，另求一个辅助数组g[i][j]表示选择2^i次后为原根的j次方的方案总数，那么dp转移显然：
f[i][(j+k)%(p-1)]=Σf[i-1][j]*g[now][k] (0<=k,j<mod-1)（可以滚动）
注意这里是p-1！由前置芝士可得（因为表示的是次方嘛）。
求g数组同理：
g[i][(j+k)%(mod-1)]=g[i-1][k]*g[i-1][j](0<=k,j<mod-1)
1 #include<bits/stdc++.h>
2 #define int long long
3 #define ts puts("----------");
4 using namespace std; 5 const int MOD=1000000007; 6 int g[1005][50],f[2][1005],num[1005],Map[1005],bin[50],To[1005]; 7 bitset<1001>s; 8 int qpower(int a,int b){ 9 int ans=1; 10 while(b){if(b&1)ans=ans*a%MOD;a=a*a%MOD;b>>=1;} 11 return ans%MOD; 12 } 13 signed main() 14 { 15 int n,m,mod; 16 scanf("%lld%lld%lld",&n,&m,&mod); 17 int t=log(m)/log(2)+1; 18 bin[0]=1; 19 for(int i=1;i<=31;i++)bin[i]=bin[i-1]<<1; 20 for(int i=1;i<mod;i++){ 21 s.reset(); 22 int base=1; 23 for(int j=1;j<mod;j++){ 24 (base*=i)%=mod; 25 s[base]=1; 26 } 27 if(s.count()==mod-1){ 28 // cout<<i<<endl;
29 int base=1; 30 for(int j=1;j<mod;j++) 31 (base*=i)%=mod,Map[base]=j,To[j]=base; 32 Map[1]=0;To[0]=1; 33 break; 34 } 35 } 36 for(int i=1;i<=n;i++) 37 { 38 int a; 39 scanf("%lld",&a); 40 num[a]++; 41 g[Map[a]][0]++; 42 } 43 for(int i=1;i<=t;i++) 44 for(int j=0;j<mod;j++) 45 for(int k=0;k<mod;k++) 46 (g[(j+k)%(mod-1)][i]+=g[k][i-1]*g[j][i-1])%=MOD; 47 // for(int i=0;i<=t;i++) 48 // for(int j=0;j<mod;j++) 49 // cout<<j<<' '<<i<<' '<<g[j][i]<<endl;
50 f[1][Map[1]]=1; 51 int now=0; 52 int cur=0; 53 for(int i=t;i>=0;i--){ 54 if(now+bin[i]>m)continue; 55 for(int j=0;j<mod;j++)f[cur][j]=0; 56 // cout<<i<<endl;
57 now+=bin[i]; 58 for(int j=0;j<mod;j++) 59 for(int k=0;k<mod;k++) 60 // cout<<k<<' '<<f[cur^1][k]<<" "<<j<<' '<<i<<' '<<g[j][i]<<endl,
61 (f[cur][(j+k)%(mod-1)]+=(f[cur^1][k]*g[j][i]))%=MOD;//,cout<<(j+k)%(mod-1)<<' '<<f[cur][(j+k)%(mod-1)]<<endl;
62 if(now==m)break; 63 cur^=1; 64 } 65 int a=0; 66 for(int i=0;i<mod;i++) 67 // cout<<i<<' '<<f[cur][i]<<endl,
68 (a+=To[i]*f[cur][i])%=MOD; 69 int b=qpower(qpower(n,m),MOD-2); 70 cout<<(a*b)%MOD<<endl; 71 return 0; 72 }
T2：单 好题标记
咕咕咕
这题嘛高斯消元就溜啦，然后获得了10的好成绩，但高斯消元没骗到分。
直接贴代码
注意的点吧：
1.高斯消元不管是不是整数解，一定要开double！
2.整数解向上取整！
3.fabs必须有！
4.sb错误！
总而言之，不要被题里说的保证有整数解蒙蔽了双眼=_=
上正解：
先看一条链的情况：
已知a[i]求b[i]:
考虑每条边的贡献，辣么，b[i]=pr[1]+pr[2]+pr[3]+......+pr[i-1]+ls[i+1]+ls[i+2]+........+ls[n]。
这是因为第一条边对于i来说只有a[1]的贡献，而第二条边有a[1]+a[2]的贡献，然后处理前缀的前缀和后缀的后缀就好啦！
已知b[i]求a[i]:
先把柿子列出来：
b[1]=ls[2]+.....+ls[n]。
b[2]=pr[1]+ls[3]+.....+ls[n]。
作差发现b[1]-b[2]=ls[2]-pr[1]，设sum=a[1]+......+a[n]。
辣么显然pr[i]+ls[i+1]=sum
=>b[1]-b[2]=sum-2*pr[1]。
以此类推 b[i]-b[i+1]=sum-2*pr[i]。
累加发现b[1]-b[n]=(n-1)*sum-2*Σpr[i](1<=i<n)
又发现后面那个sigma可以变成b[n]。
所以b[1]+b[n]=(n-1)*sum => sum=(b[1]+b[n])/(n-1)
知道sum就可以利用前面的柿子愉快的推出来了！
树上的以此类推就好啦，不过把前缀后缀换成了子树a[i]的和
AC代码：
1 #include<bits/stdc++.h>
2 #define mem(a) memset(a,0,sizeof(a))
3 #define MAXN 100050
4 #define int long long
5 using namespace std; 6 int n,a[MAXN],b[MAXN],tot,head[MAXN],nxt[MAXN*3],to[MAXN*3],cnt,rt,sz[MAXN]; 7 int mmp; 8 void add(int u,int v) 9 { 10 to[++cnt]=v; 11 nxt[cnt]=head[u]; 12 head[u]=cnt; 13 } 14 void clear() 15 { 16 mem(a);mem(b);tot=0;cnt=0;mem(head);mem(sz);mmp=0; 17 } 18 void dfs(int x,int fa,int depth) 19 { 20 b[rt]+=a[x]*depth; 21 sz[x]=a[x]; 22 for(int i=head[x];i;i=nxt[i]) 23 { 24 int y=to[i]; 25 if(y==fa)continue; 26 dfs(y,x,depth+1); 27 sz[x]+=sz[y]; 28 } 29 return ; 30 } 31 void dfs1(int x,int fa) 32 { 33 if(x!=rt)b[x]=b[fa]+tot-2*sz[x]; 34 for(int i=head[x];i;i=nxt[i]) 35 { 36 int y=to[i]; 37 if(y==fa)continue; 38 dfs1(y,x); 39 } 40 } 41 void dfs2(int x,int fa) 42 { 43 if(x!=rt)tot+=b[x]-b[fa]; 44 for(int i=head[x];i;i=nxt[i]) 45 { 46 int y=to[i]; 47 if(y==fa)continue; 48 dfs2(y,x); 49 } 50 } 51 void dfs3(int x,int fa) 52 { 53 if(x!=rt)a[x]=sz[x]=(tot+b[fa]-b[x])/2; 54 for(int i=head[x];i;i=nxt[i]) 55 { 56 int y=to[i]; 57 if(y==fa)continue; 58 dfs3(y,x); 59 if(x!=rt)a[x]-=sz[y]; 60 } 61 if(x!=rt)mmp+=a[x]; 62 return ; 63 } 64 signed main() 65 { 66 int t;rt=1; 67 scanf("%lld",&t); 68 while(t--) 69 { 70 clear(); 71 scanf("%lld",&n); 72 for(int i=1;i<n;i++) 73 { 74 int a,b; 75 scanf("%lld%lld",&a,&b); 76 add(a,b);add(b,a); 77 } 78 int mt; 79 scanf("%lld",&mt); 80 if(!mt) 81 { 82 for(int i=1;i<=n;i++)scanf("%lld",&a[i]),tot+=a[i]; 83 dfs(1,0,0); 84 dfs1(1,0); 85 for(int i=1;i<=n;i++)printf("%lld ",b[i]); 86 puts(""); 87 } 88 else
89 { 90 for(int i=1;i<=n;i++)scanf("%lld",&b[i]); 91 tot=b[1]*2; 92 dfs2(1,0); 93 tot/=(n-1); 94 dfs3(1,0); 95 a[rt]=tot-mmp; 96 for(int i=1;i<=n;i++)printf("%lld ",a[i]); 97 puts(""); 98 } 99 } 100 return 0; 101 }
T3是个打表找规律题，不说啦
考试反思：
第一次写考试反思，以前只写了题解（甚至有的题解都没写）。
连续爆炸后是波澜不惊，还是任其东西，在你自己，wd大佬一次rk15把自己说的什么都不是，而你次次落后还不知悔改。
你可以笨，但不能自甘堕落，也许努力没有结果，但不努力一定没有结果！
人生百态，世事沉浮，你，只能靠自己啊。
以前的你虽然菜，但基本上不挂分，现在又菜又挂分，是能力问题吗？
为什么以前能做到的现在反而做不到了？
暴力变难了吗？ 你变傻了吗？ 还是你的态度有问题？
你怎么做的你自己清楚，你想干什么你自然也清楚，而你能不能做到，在你心里也早有定数。
模板不会，知识点理解不透彻，思维不够，你还剩什么呀！
只有暴力，难道你就要用一直挂分的暴力苟且？ 就算你能苟过联赛，下面的路呢？ 就不走了吗？
一个题的分数是有限的，但算法的优化是无限的，你还在为T3 95分沾沾自喜吗？
一个显然的规律，被你打了两个小时的表，那么多人AC，你就不能找找规律吗？
还是，你就认为自己找不出来？
这不是什么考试技巧，这是你对自己的定位，你凭什么认为就那么难，你就推不出来？
在不该浪费时间的题上浪费时间，该得的分却拿不到。
你的考试策略出现了很大的问题
不管什么题，先试着推一下，骗分是迫不得已的行为。
某学长曾说过：或许这，或许那，都是经历，愿OI，成为你无悔的历练。