昨天误删了两篇博客QAQ
所以直接写正解了：
此T1实则为T3
由1<=ai<mod,且x=x*ai%mod 得 1<=任意状态<mod
定义f[i][j]为到第i位的当前状态为j的方案数
可得$f[i*2][j*k\%mod]=f[i][j]*f[i][k]$，
考虑对m进行优化
考虑快速幂的思想，a^b%c
f数组为a，m为b，定义g数组为ans
g[i][j]为累计到m的二进制第i位的状态为j的方案数
$g[2^a+2^b+2^c][j*k\%mod]=g[2^a+2^b][j]*f[2^c][k]$
时间复杂度O(log(m)mod^2)
因为f和g的转移只与第一维的上一位有关，滚动起来优化空间
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #define int long long 6 using namespace std; 7 const int modd=1e9+7; 8 int read() 9 { 10 int f=1,x=0;char ch=getchar(); 11 while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} 13 return f*x; 14 } 15 int n,m,p,a[100005],t[1005]; 16 int f[3][1005],g[3][1005]; 17 int qpow(int a,int b,int c) 18 { 19 int ans=1; 20 while(b) 21 { 22 if(b&1) ans=ans*a%c; 23 b>>=1; 24 a=a*a%c; 25 } 26 return ans%c; 27 } 28 signed main() 29 { 30 n=read(),m=read(),p=read(); 31 for(int i=1;i<=n;i++) 32 a[i]=read(),t[a[i]]++; 33 if(n==1) 34 { 35 int ans=qpow(a[1],m,p); 36 printf("%lld\n",ans%modd); 37 return 0; 38 } 39 if(p==2) 40 { 41 puts("1"); 42 return 0; 43 } 44 m--; 45 f[0][1]=1; 46 for(int j=1;j<p;j++) 47 for(int k=1;k<p;k++) 48 f[1][j*k%p]+=f[0][j]*t[k]%modd,f[1][j*k%p]%=modd; 49 for(int j=1;j<p;j++) 50 g[0][j]=f[1][j]; 51 int cnt=1,cnt2=0; 52 while(m) 53 { 54 if(m&1) 55 { 56 cnt2^=1; 57 memset(g[cnt2],0,sizeof g[cnt2]); 58 for(int j=1;j<p;j++) 59 for(int k=1;k<p;k++) 60 g[cnt2][j*k%p]+=g[cnt2^1][j]*f[cnt][k]%modd,g[cnt2][j*k%p]%=modd; 61 } 62 cnt^=1; 63 memset(f[cnt],0,sizeof f[cnt]); 64 for(int j=1;j<p;j++) 65 for(int k=1;k<p;k++) 66 f[cnt][j*k%p]+=f[cnt^1][j]*f[cnt^1][k]%modd,f[cnt][j*k%p]%=modd; 67 m>>=1; 68 } 69 int a1=0,a2=0; 70 for(int j=1;j<p;j++){ 71 a1=(a1+j*g[cnt2][j]%modd)%modd; 72 a2=(a2+g[cnt2][j])%modd; 73 } 74 int ans=a1*qpow(a2,modd-2,modd)%modd; 75 printf("%lld\n",ans%modd); 76 } View Codet=0:
暴力预处理出b[1]，1为根,
dfs处理sum[x],sum[x]为x的子树大小
在树上，x与其父亲fa的转移关系：
b[x]=b[fa]+sum[1]-2*sum[x]
dfs O(n)转移
t=1：
将上式变形，
b[x]-b[fa]=sum[1]-2*sum[x]
n-1（除了x=1）个式子相加
左式为定值，右=(n-1)sum[1]-2*Σ(sum[2]+……sum[n])
Σ(sum[2]+……sum[n])=b[1]
求的sum[1]后代回求解
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<cmath> 6 #include<queue> 7 #define int long long 8 using namespace std; 9 const int maxn=100005; 10 int read(){ 11 int f=1,x=0;char ch=getchar(); 12 while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} 13 while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} 14 return f*x; 15 } 16 int n,a[maxn],b[maxn],h[maxn],nu,d[maxn],fa[maxn]; 17 struct node{int v,nxt;}e[2*maxn]; 18 void add(int x,int y){e[++nu].v=y;e[nu].nxt=h[x];h[x]=nu;} 19 void bfs() 20 { 21 queue<int>q; 22 d[1]=1; 23 q.push(1); 24 while(q.size()) 25 { 26 int x=q.front();q.pop(); 27 for(int i=h[x];i;i=e[i].nxt) 28 { 29 int y=e[i].v; 30 if(d[y])continue; 31 q.push(y); 32 d[y]=d[x]+1; 33 fa[y]=x; 34 } 35 } 36 } 37 bool v[maxn];int sum[maxn]; 38 void dfs1(int x) 39 { 40 v[x]=1; 41 sum[x]=a[x]; 42 for(int i=h[x];i;i=e[i].nxt) 43 { 44 int y=e[i].v; 45 if(v[y])continue; 46 dfs1(y); 47 sum[x]+=sum[y]; 48 } 49 } 50 void dfs2(int x) 51 { 52 v[x]=1; 53 for(int i=h[x];i;i=e[i].nxt) 54 { 55 int y=e[i].v; 56 if(v[y])continue; 57 b[y]=b[x]+sum[1]-2*sum[y]; 58 dfs2(y); 59 } 60 } 61 void dfs3(int x) 62 { 63 v[x]=1; 64 for(int i=h[x];i;i=e[i].nxt) 65 { 66 int y=e[i].v; 67 if(v[y])continue; 68 sum[x]-=sum[y]; 69 dfs3(y); 70 } 71 a[x]=sum[x]; 72 } 73 void init() 74 { 75 nu=0; 76 memset(e,0,sizeof e); 77 memset(h,0,sizeof h); 78 memset(a,0,sizeof a); 79 memset(b,0,sizeof b); 80 memset(d,0,sizeof d); 81 memset(sum,0,sizeof sum); 82 } 83 signed main() 84 { 85 int T=read(); 86 while(T--) 87 { 88 init(); 89 n=read(); 90 for(int i=1;i<n;i++) 91 { 92 int x=read(),y=read(); 93 add(x,y),add(y,x); 94 } 95 bfs(); 96 int tt=read(); 97 if(tt==0) 98 { 99 for(int i=1;i<=n;i++) a[i]=read(); 100 for(int i=1;i<=n;i++) 101 b[1]+=a[i]*(d[i]-d[1]); 102 memset(v,0,sizeof v); 103 dfs1(1); 104 memset(v,0,sizeof v); 105 dfs2(1); 106 for(int i=1;i<=n;i++) 107 printf("%d ",b[i]); 108 } 109 else 110 { 111 for(int i=1;i<=n;i++) b[i]=read(); 112 int tot=0; 113 for(int i=2;i<=n;i++) 114 tot+=(b[i]-b[fa[i]]); 115 sum[1]=(tot+2*b[1])/(n-1); 116 for(int i=2;i<=n;i++) 117 sum[i]=(sum[1]-b[i]+b[fa[i]])/2; 118 memset(v,0,sizeof v); 119 dfs3(1); 120 for(int i=1;i<=n;i++) 121 printf("%d ",a[i]); 122 } 123 puts(""); 124 } 125 } View Code
typ==1时为catalan数，可以看成括号匹配
typ==2
1 #include<bits/stdc++.h> 2 #define int long long 3 #define R register 4 using namespace std; 5 const int mod=1e9+7; 6 const int maxn=200005; 7 int n,typ; 8 int f[2][2005][2005]; 9 int fac[maxn],inv[maxn],facinv[maxn]; 10 void init() 11 { 12 fac[0]=fac[1]=inv[0]=inv[1]=facinv[0]=facinv[1]=1; 13 for(R int i=2;i<=2*n+1;i++) 14 { 15 fac[i]=fac[i-1]*i%mod; 16 inv[i]=(mod-mod/i)*inv[mod%i]%mod; 17 facinv[i]=facinv[i-1]*inv[i]%mod; 18 } 19 } 20 int C(R int n,R int m) 21 { 22 return fac[n]*facinv[m]%mod*facinv[n-m]%mod; 23 } 24 int cat(R int n) 25 { 26 return C(2*n,n)*inv[n+1]%mod; 27 } 28 signed main() 29 { 30 scanf("%lld%lld",&n,&typ); 31 if(typ==2) 32 { 33 R int m=n<<1; 34 f[0][n][n]=1; 35 int t=0; 36 for(R int k=1;k<=n;++k) 37 { 38 t^=1; 39 for(R int i=0;i<=m;++i) 40 f[t][i][n]=f[t][n][i]=0; 41 for(R int i=1;i<=m;++i) 42 f[t][i][n]=(f[t][i][n]+f[t^1][i+1][n]+f[t^1][i-1][n])%mod; 43 for(R int j=1;j<=m;++j) 44 f[t][n][j]=(f[t][n][j]+f[t^1][n][j+1]+f[t^1][n][j-1])%mod; 45 46 } 47 printf("%lld\n",f[t][n][n]%mod); 48 return 0; 49 } 50 51 R int ans=0; 52 init(); 53 if(typ==0) 54 for(R int i=0;i<=n;i+=2) 55 ans=(ans+C(n,i)*C(i,i>>1)%mod*C(n-i,(n-i)>>1)%mod)%mod; 56 if(typ==1) 57 ans=cat(n>>1); 58 if(typ==3) 59 for(R int i=0;i<=n;i+=2) 60 ans=(ans+C(n,i)*cat(i>>1)%mod*cat((n-i)>>1)%mod)%mod; 61 printf("%lld\n",ans); 62 } View Code
转载于:https://www.cnblogs.com/casun547/p/11261789.html
相关资源：模拟电子线路答案（课后题解）