HDU 6360 2018HDU多校賽第五場 kaleidoscope（Polya計數+dp）

大緻題意：一個菱形六面體，有60個面，然後每個面進行染色，然後要求是第i種顔色不少于c[i]個，問有多少個本質不同的染色方案。

看到這個菱形六面體，60個面，不要自閉……其實仔細想想這個圖形也很簡單。我們把每一個凸出來的菱形頂點相連，我們發現會變成一個十二面體。正如題目種所說，菱形六面體是十二面體的每個面中點往中間收縮形成的。是以，這個60面看起來吓人，但其實就是一個十二面體。

是以對于十二面體，我們同樣考慮用polya計數。根據套路，首先計算定理和置換數，然後計算每一個置換的循環節，還有每一類置換群對應的循環個數。對于同一個循環裡面的東西，我們要讓它顔色相同，那麼相當于對每種置換群求有多少個循環，用循環個數對應不考慮旋轉的答案。把所有置換群的答案計算求和之後，除以總置換數就是最後的結果。

現在，我們來考慮一下正十二面體有多少種置換。在腦海裡想(bai)象(du)一下十二面體的圖形。

很顯然，以相對面面的中心連線為軸進行旋轉，分别轉108度、216度、324度和432度，對應有12/2*4=24種置換。

以相對的兩個頂點的連線為軸進行旋轉，分别轉120度和240度，對應有20/2*2=20種置換。

以相對的兩條棱的中點連線為軸，旋轉180度，對應有30/2*1=15種置換。

靜止不動總共有1種置換。

綜上，總的置換數目是24+20+15+1=60種，有四個置換群，對應的循環節長度分别是5、3、2、1，對應的循環個數就是12、20、30和60。然後就是在不考慮旋轉的情況下，12、20、30和60個面，在滿足限制的條件下有多少種塗色方案。這個我們考慮用dp。令dp[i][j]表示用前i個顔色塗前j個面的方案數，那麼有轉移方程：

#include<bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define LL long long
#define N 100010
using namespace std;

const LL BLEN=25,BMSK=(1<<25)-1;
LL t[4]={1,15,20,24},len[4]={1,2,3,5},c[61][61];
LL dp[100][100],a[100],s[4],mod;

LL multiply(LL x,LL y,LL mo)
{
    LL x1=x>>BLEN,y1=y>>BLEN;
    LL x2=x&BMSK,y2=y&BMSK;
    LL res=x1&&y1?(((x1*y1%mo)<<BLEN)%mo<<BLEN)%mo:0;
    res=(res+(x1?((x1*y2%mo)<<BLEN)%mo:0))%mo;
    res=(res+(y1?((x2*y1%mo)<<BLEN)%mo:0))%mo;
    return (res+y2*x2%mo)%mo;
}

int main()
{
    file(1011);
    IO;
    int T,n; cin>>T;
    for(int i=0;i<=60;i++) c[i][0]=1;
    while(T--)
    {
        cin>>n>>mod;
        LL ans=0,mo=mod*60;
        memset(s,0,sizeof(s));
        for(int i=1;i<=60;i++)
            for(int j=0;j<=i;j++)
                c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            for(int j=0;j<4;j++)
                s[j]+=a[i]?(a[i]-1)/len[j]+1:0;
        }
        for(int i=0;i<4;i++)
        {
            int up=60/len[i];
            if (up<s[i]) continue;
            memset(dp,0,sizeof(dp));
            dp[0][0]=1;
            for(int j=1;j<=n;j++)
            {
                int down=a[j]?(a[j]-1)/len[i]+1:0;
                for(int k=down;k<=up;k++)
                    for(int l=down;l<=k;l++)
                        dp[j][k]=(dp[j][k]+multiply(dp[j-1][k-l],c[k][l],mo))%mo;
            }
            ans=(ans+multiply(t[i],dp[n][up],mo))%mo;
        }
        assert(ans%60==0);
        cout<<ans/60<<endl;
    }
    return 0;
}