[ZJ] a812 動物排隊

聽學長解說才會的
dp[i][j][k]表示當雞i隻 鴨j隻時整齊度為k的組合數

設原先整齊度k
若放雞整齊度會變成(k*2)%m (k在二進制往左進一位)
放鴨整齊度會變成(k*2+1)%m 

組合數乘上該整齊度的總和即為所求

#include<cstdio>
#define LL long long
LL dp[65][65][3605],cnt;
int x,y,m;
int min(int a,int b){
    return a<b? a:b;
}
int main(){
    scanf("%d%d%d",&x,&y,&m);
    dp[0][0][0]=1;
    for(int i=0;i<=x;i++){
        for(int j=0;j<=min(y,i);j++){
            for(int k=0;k<m;k++){
                if(i)dp[i][j][(k*2)%m]+=dp[i-1][j][k];
                if(j)dp[i][j][(k*2+1)%m]+=dp[i][j-1][k];
            }
        }
    }
    for(int i=0;i<m;i++)
        cnt+=dp[x][y][i]*i;
    printf("%lld\n",cnt);
}