T1 卷
一看跟没有上司的舞会一样，直接敲了然后试个自己造的样例对了就跑了。。。
然而把它想简单了，乘积取模，还能比大小吗？？？？？
显然不能
所以直接让对数的加和跟着$dp$直接一起跑，比大小的都用对数就行
1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 inline int AE86(){ 5 int x=0,f=1; char ch=getchar(); 6 while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } 7 while(ch>=‘0‘&&ch<=‘9‘){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} 8 return x*f; 9 } 10 const int NN=2e5+5,p=1e9+7; 11 int n,w[NN],dp[NN][2]; 12 double lg[NN],l[NN][2]; 13 struct SNOW{int fr,to,next;};SNOW e[NN<<1]; int head[NN],rp; 14 inline void add(int x,int y){ 15 e[++rp]=(SNOW){x,y,head[x]};head[x]=rp; 16 e[++rp]=(SNOW){y,x,head[y]};head[y]=rp; 17 } 18 inline void dfs(int f,int x){ 19 (dp[x][0]*=w[x])%=p; l[x][0]+=lg[x]; 20 for(int i=head[x],y;i;i=e[i].next) if((y=e[i].to)!=f){ 21 dfs(x,y); 22 (dp[x][1]*=(l[y][1]>l[y][0]?dp[y][1]:dp[y][0]))%=p; 23 (dp[x][0]*=dp[y][1])%=p; 24 l[x][1]+=max(l[y][1],l[y][0]); 25 l[x][0]+=l[y][1]; 26 } 27 } 28 namespace WSN{ 29 inline short main(){ 30 n=AE86();for(int i=1;i<=n;i++) dp[i][0]=dp[i][1]=1; 31 for(int i=1;i<=n;i++) w[i]=AE86(),lg[i]=log(w[i]); 32 for(int i=1;i<n;i++) add(AE86(),AE86()); 33 // for(int i=1;i<=rp;i++) cout<<e[i].fr<<" "<<e[i].to<<endl; 34 dfs(0,1); 35 printf("%lld\n",l[1][0]>l[1][1]?dp[1][0]:dp[1][1]); 36 return 0; 37 } 38 } 39 signed main(){return WSN::main();}
T2 简单题
组合数学。。。。。不会，永远不会。。。。。。
发现每个偶数都可以拆成一个奇数乘$2^k$得到
不妨把能用那个奇数得到的偶数都划分给那个奇数
如果一个集合选择了这个奇数，那么这个集合相应的选择$x*2^0,x*2^2,x*2^4,x*2^6...$
另外的集合选择剩下的$x*2^1,x*2^3...$，我们分别叫这两种选择的个数为一个数$x$的偶数权和奇数权
这样我们会发现，有时候左右选择不同，两个集合会有一定的数量上的差值，即有时$偶数权-奇数权=1$
因为这个数可能只有偶数个偶数和他构成关系，这样每次进行分配，两个集合都会有相差$1$
那么，我们假设把所有偶数权的放到一个集合，那么算出他集合内元素个数$sum$，
再相应的算出偶数权比奇数权多$1$的奇数个数$Y$，奇数偶数权相等的个数$X$
那么答案可以表示为$2^X*C_{Y}^{sum-m}$
自认为计算这几个量的过程不太好说，也比较喵，所以直接看码吧。
1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 inline int AE86(){ 5 int x=0,f=1; char ch=getchar(); 6 while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } 7 while(ch>=‘0‘&&ch<=‘9‘){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} 8 return x*f; 9 } 10 const int NN=10000020,p=10000019; 11 int n,q,h[NN],v[NN],sum,num[100],X,Y; 12 inline int qmo(int a,int b){ 13 int ans=1,c=p; a%=c; 14 while(b){ 15 if(b&1) ans=(ans*a)%c; 16 b>>=1; a=(a*a)%c; 17 }return ans; 18 } 19 inline void pre(){ 20 h[0]=h[1]=1; v[0]=v[1]=1; 21 for(int i=2;i<=10000018;i++) h[i]=h[i-1]*i%p; 22 v[10000018]=qmo(h[10000018],p-2); 23 for(int i=10000017;i>=2;i--) v[i]=v[i+1]*(i+1)%p; 24 } 25 inline int C(int n,int m){ 26 if(n<0||m<0||n<m) return 0; 27 return h[n]*v[n-m]%p*v[m]%p; 28 } 29 inline int lucas(int n,int m){ 30 if(!m) return 1; 31 return lucas(n/p,m/p)*C(n%p,m%p)%p; 32 } 33 namespace WSN{ 34 inline short main(){ 35 n=AE86(); q=AE86(); pre(); 36 int cnt=0; 37 while(pow(2ll,cnt)<n){ 38 int mi=pow(2ll,cnt),f=n/mi; 39 num[cnt]=(f+1)/2; ++cnt; 40 }--cnt; 41 for(int i=2;i<=cnt;i+=2) sum+=num[i]; 42 for(int i=0;i<=cnt;i++) num[i]-=num[i+1]; 43 for(int i=0;i<=cnt;i++) 44 if(i&1) X+=num[i]; 45 else Y+=num[i]; 46 sum+=(1+n)>>1; 47 int aa=qmo(2,X); 48 while(q--) printf("%lld\n",aa*lucas(Y,sum-AE86())%p); 49 return 0; 50 } 51 } 52 signed main(){return WSN::main();}
T3 粉丝
求划分数，先科普两种$dp$
$f_{i,j}$表示$dp$到$i$，总和为$j$的划分数，则可以按照完全背包$dp$，每次枚举$i$选择了几个即可
$g_{i,j}$表示划分了$i$个数，总和为$j$的划分数，这是经典的划分数$dp$，有$g_{i,j}=g_{i-1,j}+g_{i,j-i}$
然后发现可以之考虑下界，最后按照前缀和的处理方式算答案就行
$dp$分成两部分，前$\sqrt n$用$f_{i,j}dp$，后面的用$g_{i,j}dp$，最后整合答案即可
1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 namespace AE86{ 5 inline int read(){ 6 int x=0,f=1;char ch=getchar(); 7 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 8 while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f; 9 }inline void write(int x,char opt=‘\n‘){ 10 char ch[20];int len=0;if(x<0)x=~x+1,putchar(‘-‘); 11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x); 12 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);} 13 }using namespace AE86; 14 15 const int NN=3e5+1; 16 int x,y,n,p,f[NN],g[NN],s[NN],B; 17 inline int work(int ss){ 18 if(ss>n) return 0; 19 int m=max(B,ss); f[0]=g[0]=s[0]=1ll; 20 for(int i=ss;i<m;i++) 21 for(int j=i;j<=n;j++) (f[j]+=f[j-i])%=p; 22 for(int i=1;i<=n/m;i++){ 23 int t=i*m; 24 for(int j=i;j+t<=n;j++) (g[j]+=g[j-i])%=p; 25 for(int j=0;j+t<=n;j++) (s[j+t]+=g[j])%=p; 26 } 27 int ans=0; 28 for(int i=0;i<=n;i++) (ans+=f[i]*s[n-i]%p)%=p; 29 memset(f,0,sizeof(f)); 30 memset(g,0,sizeof(g)); 31 memset(s,0,sizeof(s)); 32 return ans; 33 } 34 namespace WSN{ 35 inline short main(){ 36 x=read();y=read();n=read();p=read(); B=sqrt(n); 37 write((work(x)-work(y+1)+p)%p); 38 return 0; 39 } 40 } 41 signed main(){return WSN::main();}
T4 字符串
刚学会$manacher$，先沽了