BZOJ1004 Cards （burnside dp 擴充歐幾裡德）

題目大意

有三種顔色的卡片分别sa，sb，sc張，并給出m種相等的置換方式，求所有本質不同的排列方式。

題解：

根據burnside引理，本質不同的排列數（ans）=sigma（Zi）/m。其中Zi表示對于第i種置換，無論怎麼置換，置換幾遍都相同的排列的個數，既不動點的個數。根據Polya定理可知，對于某個置換的某個循環節，循環節内所有的元素都相同的排列可稱為一個不動點。

由于有sa，sb，sc的限制，是以要對每一個置換進行01背包dp。每一個循環節是一個物品，循環節的大小就是物品體積。

最後求平均數的時候要用exgcd求出平均數。

代碼：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

int p;
int add(int a,int b) {
    int c=a+b;
    return c>=p?c-p:c;
}
int mul(int a,int b) {
    int c=a*b;
    return c%p;
}
void exgcd(int a,int b,int &x,int &y) {
    if(b==) {x=,y=; return;}
    exgcd(b,a%b,x,y);
    int tmp=x;
    x=y, y=tmp-a/b*y;
}

const int maxn=;
int sa,sb,sc;
int n,m;
int a[maxn][maxn];
bool vis[maxn];
int sta[maxn],top=;
int f[][][];

int dp(int *to) {
    top=;
    for(int i=;i<=n;i++) if(!vis[i]) {
        int siz=, cur=to[i];
        while(cur!=i) {vis[cur]=true, siz++, cur=to[cur];}
        sta[++top]=siz;
    }
    memset(f,,sizeof f);
    f[][][]=;
    for(int i=;i<=top;i++)
    for(int a=sa;a>=;--a)
    for(int b=sb;b>=;--b)
    for(int c=sc;c>=;--c) {
        int s=sta[i];
        if(a>=s) f[a][b][c]=add(f[a][b][c],f[a-s][b][c]);
        if(b>=s) f[a][b][c]=add(f[a][b][c],f[a][b-s][c]);
        if(c>=s) f[a][b][c]=add(f[a][b][c],f[a][b][c-s]);
    }
    return f[sa][sb][sc];
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif // ONLINE_JUDGE
    scanf("%d%d%d%d%d",&sa,&sb,&sc,&m,&p); m++;
    n=sa+sb+sc;

    for(int i=;i<=n;i++) a[][i]=i;
    for(int i=;i<=m;i++)
        for(int j=;j<=n;j++)
            scanf("%d",&a[i][j]);

    int ans=;
    for(int i=;i<=m;i++) ans=add(ans,dp(a[i]));

    int x,y;
    exgcd(m,p,x,y);
    while(x<) x+=p;
    printf("%d\n",mul(ans,x));

    return ;
}