联赛模拟测试5 涂色游戏 矩阵优化DP

微信扫一扫,分享到朋友圈

联赛模拟测试5 涂色游戏 矩阵优化DP

题目描述

分析

定义出 \(dp[i][j]\) 为第 \(i\) 列涂 \(j\) 种颜色的方案数

然后我们要解决几个问题

首先是求出某一列涂恰好 \(i\) 种颜色的方案数 \(d[i]\)

如果没有限制必须涂 \(i\) 种,而是有的颜色可以不涂,那么方案数为 \(i^n\)

为了避免少涂的情况,我们减去只涂 \(1 \sim i-1\) 种颜色的方案数

\(d[i]=i^n-\sum_{j=1}^{i-1}C_i^j \times d[j]\)

初始化为 \(d[1]=1\)

接下来考虑转移

\(f[i][j]=f[i-1][k] \times d[j] \times C_k^{cf} \times C_{p-k}^{j-cf}\)

其中 \(i\) 为当前列的编号, \(j\) 为当前列选了几种颜色, \(k\) 为上一列选了几种颜色, \(cf\) 为这些颜色有几种相同的

注意两个组合数不能写成

\(C_j^{cf} \times C_{p-j}^{k-cf}\)

因为我们要选出 \(j\) 个,而不是 \(k\)

时间复杂度 \(m \times n^3\)

期望得分: \(40\) ,实际得分: \(50\)

下一步我们考虑怎么优化

我们会发现,如果 \(j\)\(k\) 确定了,那么 \(f[i-1][k]\) 乘的系数就确定了

根据乘法分配率,我们可以把系数预处理出来,优化掉一维

时间复杂度 \(m \times n^2\)

期望得分: \(70\) ,实际得分: \(70\)

我们继续观察会发现,每一列的转移乘的系数都是固定的

结合 \(m\) 的大小,我们可以使用矩阵快速幂优化

时间复杂度 \(logm \times n^3\)

期望得分:
\(100\)

,实际得分:

\(70\)

因为出题人卡常卡到丧心病狂,最后几个点仍然会跑到 \(2s\)

所以我们要优化代码的常数

能不用
\(longlong\)

就不用

\(longlong\)

减少取模的次数

加几个玄学的
\(register\)

\(inline\)

再手动吸一下氧就可以了

时间复杂度 \(logm \times n^3\)

期望得分:
\(100\)

,实际得分:

\(100\)

代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define fastcall __attribute__((optimize("-O3")))
%:pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-fhoist-adjacent-loads")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
const int maxn=1e4+5;
const int maxm=105;
const int maxp=1e4+5;
const int mod=998244353;
int ny[maxn],jc[maxn],jcc[maxn],f[maxp][maxm],n,m,p,q,d[maxm],xs[maxm][maxm];
int a[maxm][maxm];
int ans;
int getC(int nn,int mm){
return 1LL*jc[nn]*jcc[mm]%mod*jcc[nn-mm]%mod;
}
int ksm(int ds,int zs){
int ans=1;
while(zs){
if(zs&1) ans=1LL*ans*ds%mod;
ds=1LL*ds*ds%mod;
zs>>=1;
}
return ans;
}
struct asd{
int sz[maxm][maxm];
asd(){
memset(sz,0,sizeof(sz));
}
}da,xss;
#define reg register
asd cf(asd aa,asd bb){
asd cc;
for(reg int i=1;i<maxm;i++){
for(reg int j=1;j<maxm;j++){
for(reg int k=1;k<maxm;k++){
cc.sz[i][j]=(cc.sz[i][j]+1LL*aa.sz[i][k]*bb.sz[k][j]%mod);
if(cc.sz[i][j]>=mod) cc.sz[i][j]-=mod;
}
}
}
return cc;
}
int main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&p,&q);
ny[1]=1;
for(int i=2;i<maxm;i++){
ny[i]=1LL*(mod-mod/i)*ny[mod%i]%mod;
}
jc[0]=jcc[0]=1;
for(int i=1;i<maxm;i++){
jc[i]=1LL*jc[i-1]*i%mod;
jcc[i]=1LL*jcc[i-1]*ny[i]%mod;
}
int mmax=std::min(n,p);
d[1]=1;
for(reg int i=2;i<=mmax;i++){
d[i]=ksm(i,n);
for(reg int j=1;j<i;j++){
d[i]=(d[i]-1LL*d[j]*getC(i,j)%mod+mod);
if(d[i]>=mod) d[i]-=mod;
}
}
for(reg int i=1;i<=mmax;i++){
f[1][i]=1LL*getC(p,i)*d[i]%mod;
da.sz[i][1]=f[1][i];
}
for(reg int j=1;j<=mmax;j++){
for(reg int k=1;k<=mmax;k++){
int noww=std::min(j,k);
for(reg int cf=0;cf<=noww;cf++){
if(j+k-cf<q || j+k-cf>p) continue;
xs[j][k]=(xs[j][k]+1LL*d[j]*getC(k,cf)%mod*getC(p-k,j-cf)%mod);
if(xs[j][k]>=mod) xs[j][k]-=mod;
xss.sz[j][k]=xs[j][k];
}
}
}
m--;
while(m){
if(m&1) da=cf(xss,da);
m>>=1;
xss=cf(xss,xss);
}
for(int i=1;i<=mmax;i++){
ans+=da.sz[i][1];
if(ans>=mod) ans-=mod;
}
printf("%d\n",ans);
return 0;
}

微信扫一扫,分享到朋友圈

联赛模拟测试5 涂色游戏 矩阵优化DP

罗永浩:6亿的债务已经还了超4亿 预计一年多之内就能还清

上一篇

全球首款64核工作站联想ThinkStation P620震撼发布

下一篇

你也可能喜欢

联赛模拟测试5 涂色游戏 矩阵优化DP

长按储存图像,分享给朋友