计数专题测试？？？
三题三计数，两个是$O(n^5)$。诡异。
可能我的脑子比较适合想暴力，所以两个$O(n^5)$折腾来折腾去居然都弄出来了。
然后$T2$一个$nlog$的题没时间写了，写暴力，结果还因为着急写挂了线段树丢了$30$分。
$T2$其实也是个套路，花点时间想应该问题也不大。但是只能说这场考试明显的前松后紧了。
本来时间没这么紧张的。但是还是效率不够高吧。。。
T1：容器
大意：序列，$k$次操作，第$i$次可以指定一个$L_i,R_i$使得区间$+1$。要求最后整个序列每个值都$le T$。求有多少中可行的操作方案。$n,k le 40$
设$dp[i][j][[l]$表示考虑到序列第$i$位，有$j$次操作的左端点已确定，有$l$个操作的右端点未确定。转移带两个含义上的组合数就行。$O(n^5)$
上下界并不满，可以卡一卡。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 1011110011 4 int C[44][44],dp[44][44][44],n,k,t; 5 int mo(int x){return x>=mod?x-mod:x;} 6 int main(){ 7 for(int i=0;i<41;++i)for(int j=C[i][0]=1;j<=i;++j)C[i][j]=mo(C[i-1][j-1]+C[i-1][j]); 8 dp[0][0][0]=1; cin>>n>>k>>t; 9 for(int i=1;i<=n+1;++i)for(int j=0;j<=k;++j)for(int l=0;l<=j&&l<=t;++l)if(dp[i-1][j][l]) 10 for(int x=0;x<=l;++x)for(int y=0;y<=k-j&&l-x+y<=t;++y) 11 dp[i][j+y][l-x+y]=(dp[i][j+y][l-x+y]+1ll*dp[i-1][j][l]*C[l][x]%mod*C[k-j][y])%mod; 12 cout<<dp[n+1][k][0]<<endl; 13 }
T2：果树
大意：点有颜色，求树上有多少路径满足路径上没有一种颜色出现了两次。每种颜色在树上最多出现$20$次。$n le 10^5$
相当于有$20n$条限制：经过这两个点的路径不能同时选。
如果这两个点是祖先后代关系，那么你就不能同时选择$x$的$y$方向外的子树的一个点以及$y$子树内的一个点。
如果不是祖先后代关系那么限制就是不能同时选择$x,y$子树内的一点。
放到$dfs$序就是一两个区间。如果放在二维的$dfs$序为下标的矩阵上那就是一个矩形。
我们发现我们要求的就是这些矩形的并的补集的面积。经典的线段树扫描线。$O(20nlogn)$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 800005 4 int fir[S],l[S],to[S],col[S],dfr[S],tim,ec,n,dfn[S],w[S],val[S],f[20][S];long long ans; 5 vector<int>v[S],_l[S],_r[S],_o[S]; 6 #define lc p<<1 7 #define rc lc|1 8 #define md (L+R>>1) 9 void add(int l,int r,int v,int p=1,int L=1,int R=n){//cerr<<l<<' '<<r<<' '<<v<<endl; 10 if(l<=L&&R<=r){w[p]+=v,val[p]=w[p]?R-L+1:val[lc]+val[rc];return;} 11 if(l<=md)add(l,r,v,lc,L,md); if(r>md)add(l,r,v,rc,md+1,R); 12 val[p]=w[p]?R-L+1:val[lc]+val[rc]; 13 } 14 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;} 15 void dfs(int p,int fa=0){ 16 dfn[p]=++tim; f[0][p]=fa; 17 for(int i=1;i<17;++i)f[i][p]=f[i-1][f[i-1][p]]; 18 for(int i=fir[p];i;i=l[i])if(to[i]!=fa)dfs(to[i],p); 19 dfr[p]=tim; 20 } 21 int getson(int y,int x){for(int i=16;~i;--i)if(dfn[f[i][y]]>dfn[x])y=f[i][y];return y;} 22 void ins(int l,int r,int L,int R){ 23 if(l>r||L>R)return; //cerr<<l<<' '<<r<<' '<<L<<' '<<R<<endl; 24 r++; 25 _l[l].push_back(L); _r[l].push_back(R); _o[l].push_back(+1); 26 _l[r].push_back(L); _r[r].push_back(R); _o[r].push_back(-1); 27 r--; swap(l,L); swap(r,R); r++; 28 _l[l].push_back(L); _r[l].push_back(R); _o[l].push_back(+1); 29 _l[r].push_back(L); _r[r].push_back(R); _o[r].push_back(-1); 30 } 31 int main(){ 32 cin>>n; 33 for(int i=1;i<=n;++i)scanf("%d",&col[i]),v[col[i]].push_back(i); 34 for(int i=1,a,b;i<n;++i)scanf("%d%d",&a,&b),link(a,b),link(b,a); 35 dfs(1); 36 for(int i=1;i<=n;++i)for(int j=0;j<v[i].size();++j)for(int k=j+1;k<v[i].size();++k){ 37 int x=v[i][j],y=v[i][k],z; 38 if(dfn[x]>dfn[y])swap(x,y); 39 if(dfn[y]<=dfr[x])z=getson(y,x),ins(1,dfn[z]-1,dfn[y],dfr[y]),ins(dfr[z]+1,n,dfn[y],dfr[y]); 40 else ins(dfn[x],dfr[x],dfn[y],dfr[y]); 41 } 42 for(int i=1;i<=n;++i){ 43 for(int j=0;j<_l[i].size();++j)add(_l[i][j],_r[i][j],_o[i][j]); 44 ans+=n-val[1];//cerr<<ans<<endl; 45 }cout<<(ans-n)/2+n<<endl; 46 }
T3：流浪
大意：二维网格每次走一个格，求不能走到坏点，走了$t$步，其中经过次数$ge k$的格子个数的期望。$n,t le 30$
由于期望的线性性，我们可以转而去对每一个格子求出它被经过$k$次的方案有多少种。
下列所有路径均表示不经过坏点的路径，转移时判断即可。
设$g[i][x][y]$表示走了$i$步，过程中不经过$(x,y)$最后停在了$(x,y)$的方案数。
设$f[i][x][y]$表示从$(x,y)$出发走了$i$步中途不经过$(x,y)$最后停在了$(x,y)$的方案数。
设$h[i][x][y]$表示从$(x,y)$出发走了$i$步中途不经过$(x,y)$最后停在了任意非$(x,y)$位置的方案数。
转移都比较显然。最后枚举每一个格子去做一下背包就行了。
每一部分的复杂度都是$O(n^5)$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 998244353 4 int bad[66][66],n,k,t,ans,p[33][66][66],g[33][66][66],f[33][66][66],bp[33][33],h[33][66][66]; 5 void add(int&a,int b){a+=b;if(a>=mod)a-=mod;} 6 int main(){ 7 cin>>t>>n>>k; 8 for(int x,y,i=1;i<=n;++i)scanf("%d%d",&x,&y),bad[x+33][y+33]=1; 9 for(int ex=-t;ex<=t;++ex)for(int ey=-t+abs(ex);ey<=t-abs(ex);++ey)if(!bad[33+ex][33+ey]){ 10 p[0][33][33]=1;ex+=33;ey+=33; 11 for(int i=0;i<=t;++i)for(int x=-i;x<=i;++x)for(int y=-i+abs(x);y<=i-abs(x);++y)if(p[i][x+33][y+33]&&!bad[x+33][y+33]){ 12 x+=33;y+=33; 13 if(x==ex&&y==ey)g[i][x][y]=p[i][x][y]; 14 else add(p[i+1][x+1][y],p[i][x][y]),add(p[i+1][x-1][y],p[i][x][y]), 15 add(p[i+1][x][y+1],p[i][x][y]),add(p[i+1][x][y-1],p[i][x][y]); 16 p[i][x][y]=0; x-=33;y-=33; 17 }ex-=33;ey-=33; 18 } 19 for(int ex=-t;ex<=t;++ex)for(int ey=-t+abs(ex);ey<=t-abs(ex);++ey)if(!bad[33+ex][33+ey]){ 20 p[0][33+ex][33+ey]=1; 21 for(int i=0;abs(ex)+abs(ey)+i<=t;++i)for(int x=ex-i;x<=ex+i;++x)for(int y=ey-i+abs(x-ex);y<=ey+i-abs(x-ex);++y)if(p[i][x+33][y+33]&&!bad[x+33][y+33]){ 22 x+=33;y+=33;ex+=33;ey+=33; 23 if(i&&x==ex&&y==ey)f[i][x][y]=p[i][x][y]; 24 else add(p[i+1][x+1][y],p[i][x][y]),add(p[i+1][x-1][y],p[i][x][y]), 25 add(p[i+1][x][y+1],p[i][x][y]),add(p[i+1][x][y-1],p[i][x][y]),add(h[i][ex][ey],p[i][x][y]); 26 p[i][x][y]=0; x-=33;y-=33;ex-=33;ey-=33; 27 }memset(p[t-abs(ex)-abs(ey)+1],0,sizeof p[0]); 28 } 29 for(int ex=-t;ex<=t;++ex)for(int ey=-t+abs(ex);ey<=t-abs(ex);++ey)if(!bad[33+ex][33+ey]){ 30 ex+=33;ey+=33; 31 for(int i=0;i<=t;++i)bp[1][i]=g[i][ex][ey]; 32 for(int i=1;i<=t;++i)for(int j=0;j<=t;++j)if(bp[i][j])for(int l=j+1;l<=t;++l) 33 bp[i+1][l]=(bp[i+1][l]+1ll*bp[i][j]*f[l-j][ex][ey])%mod; 34 for(int i=k;i<=t;++i)for(int j=abs(ex-33)+abs(ey-33);j<=t;++j)ans=(ans+1ll*bp[i][j]*h[t-j][ex][ey])%mod; 35 memset(bp,0,sizeof bp); ex-=33;ey-=33; 36 }cout<<ans<<endl; 37 }