解题:HNOI 2013 Cards

时间:2023-03-09 07:58:54
解题:HNOI 2013 Cards

题面

除了不洗牌以外,每种洗牌方式的每个循环里的颜色必须一样,然后大力背包一下就好了。最后记得把不洗牌的方案也算进去

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,m,p,c1,c2,c3,ans;
int dp[][N][N][N],noww,last;
int trs[N][N],vec[N][N],siz[N],vis[N];
void exGCD(int a,int b,int &x,int &y)
{
if(!b) x=,y=;
else exGCD(b,a%b,y,x),y-=a/b*x;
}
int Inv(int x)
{
int xx,yy;
exGCD(x,p,xx,yy);
return (xx%p+p)%p;
}
void Mod(int &x,int y)
{
x+=y;
if(x>=p) x-=p;
}
void Getcir(int idx,int pos)
{
vis[pos]=true,vec[idx][siz[idx]]++;
if(!vis[trs[idx][pos]])
Getcir(idx,trs[idx][pos]);
}
int main()
{
scanf("%d%d%d%d%d",&c1,&c2,&c3,&m,&p),n=c1+c2+c3;
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
scanf("%d",&trs[i][j]);
memset(vis,,sizeof vis);
for(int j=;j<=n;j++)
if(!vis[j]) siz[i]++,Getcir(i,j);
}
for(int i=;i<=m;i++)
{
memset(dp,,sizeof dp),noww=dp[][][][]=,last=;
for(int j=;j<=siz[i];j++)
{
int sz=vec[i][j];
for(int k=;k<=c1-sz;k++)
for(int h=;h<=c2-sz;h++)
for(int l=;l<=c3-sz;l++)
{
int t=dp[last][k][h][l];
if(k+sz<=c1) Mod(dp[noww][k+sz][h][l],t);
if(h+sz<=c2) Mod(dp[noww][k][h+sz][l],t);
if(l+sz<=c3) Mod(dp[noww][k][h][l+sz],t);
}
last=noww,noww^=;
}
ans+=dp[last][c1][c2][c3],ans%=p;
}
memset(dp,,sizeof dp),noww=dp[][][][]=,last=;
for(int i=;i<=n;i++)
{
for(int k=;k<=c1;k++)
for(int h=;h<=c2;h++)
for(int l=;l<=c3;l++)
{
int t=dp[last][k][h][l];
if(k+<=c1) Mod(dp[noww][k+][h][l],t);
if(h+<=c2) Mod(dp[noww][k][h+][l],t);
if(l+<=c3) Mod(dp[noww][k][h][l+],t);
}
last=noww,noww^=;
}
printf("%lld",1ll*(ans+dp[last][c1][c2][c3])*Inv(m+)%p);
return ;
}