BZOJ 1004([HNOI2008]Cards-Polya计数+k背包) (二)

2014-11-24 01:07:55 · 作者: · 浏览: 7
x=y;y=t-(a/b)*y;
return g;
}
int inv(int a)
{
int x,y;
int g=exgcd(a,F,x,y);
return g==1 (x+F)%F:-1;
}
int st[MAXN],size=0,sum[MAXN]={0},id[MAXN]={0};
bool b[MAXN];
int f[MAXN/3][MAXN/3][MAXN/3];
int C()
{
size=0;memset(b,0,sizeof(b));memset(id,0,sizeof(id));
For(i,n)
if (!b[i])
{
int ans=0;
while (!b[g[i]]) i=g[i],b[i]=1,ans++;
//i=g[i];
st[++size]=ans;sum[size]=sum[size-1]+st[size];id[sum[size]]=size;
}
// For(i,size) cout< memset(f,0,sizeof(f));f[0][0][0]=1;
Rep(i,sr+1) Rep(j,sb+1) Rep(k,sg+1)
if (id[i+j+k])
{
int v=st[id[i+j+k]];
if (i-v>=0) f[i][j][k]=(f[i][j][k]+f[i-v][j][k])%F;
if (j-v>=0) f[i][j][k]=(f[i][j][k]+f[i][j-v][k])%F;
if (k-v>=0) f[i][j][k]=(f[i][j][k]+f[i][j][k-v])%F;
}
return f[sr][sb][sg];
}
int main()
{
// freopen("bzoj1004.in","r",stdin);
scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&F);n=sr+sb+sg;
int ans=0;
For(i,m)
{
For(j,n) scanf("%d",&g[j]);
ans=(ans+C())%F;
}
For(j,n) g[j]=j;
ans=(ans+C())%F;
ans=ans*inv(m+1)%F;
cout< return 0;
}