题解 P1446 【[HNOI2008]Cards】

Tgotp · 2017-06-14 14:40:55 · 题解

算法：数论+dp

时间：0ms；

思路：套用burnside引理，这题因为对颜色有限制 不能用 polya ，用动归求出对于一个置换的不动方案数 ；

一些解释：f[i][j][k]表示前i个循环 用了1号颜色j个 2号颜色k个的方案数,num[n]表示该洗牌法下的循环节个数；

其余没啥了，就这样，看看代码就熟悉了。

c++代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
inline void read(int&x)
{
    x = 0;char c; int sign = 1;
    do{ c = getchar();if(c == '-') sign = -1; }while(c < '0' || c>'9');
    do{ x = x*10 + c - '0';c = getchar(); }while( c <= '9' && c >= '0');
    x *= sign;
}
int cr,cb,cg,p,m,f[65][21][21],a[65],n,num[65];
bool b[65];
inline int power(int a,int n)
{
    int ans = 1;
    while(n){
        if(n&1) ans = (ans*a) % p;
        a = (a*a)%p;
        n = n>>1;
    }
    return ans;
}
int main()
{
    read(cr);read(cb);read(cg);read(m);read(p);
    int tot = cr + cb + cg,ans = 0; m++;
    for(int t = 1 ;t <=m;t++)
    {
        if(m == t) for(int i = 1;i <= tot;i++) a[i] = i;
        else for(int i = 1;i <= tot; i++) read(a[i]);
        memset(b,false,sizeof(b)); n = 0;
        for(int i = 1;i <= tot;i++) if(!b[i]){
            int j = i,k = 0;
            while(!b[j]){ k++;b[j] = true;j = a[j];}
            num[++n] = k;
        }
        memset(f,0,sizeof(f));
        f[0][0][0] = 1;
        for(int i = 1;i <= n;i++)
            for(int aa = 0;aa <= cr;aa++)
                for(int bb = 0;bb <= cb;bb++)
                {
                    int cc = i - aa - bb;
                    if(cc < 0 || cc > cg) continue;
                    int k = 0;
                    if(aa >= num[i]) k = (k + f[i-1][aa-num[i]][bb])%p;
                    if(bb >= num[i]) k = (k + f[i-1][aa][bb-num[i]])%p;
                    if(cc >= num[i]) k = (k + f[i-1][aa][bb])%p;
                    f[i][aa][bb] = k;
                }
        ans = (ans + f[n][cr][cb])%p;
    }
    cout<<(ans*power(m,p-2))%p;
    return 0;
}
最后安利下我的blog<http://tgotp.science/>