[ZJ] a812. 2013高雄市能力競賽高中組 3. 動物排隊

#include<stdio.h>
#include<algorithm>
using namespace std;
long long int dp[61][61][3601]={0};
int main(){
    int n,m,p,i,j,k;
    scanf("%d%d%d",&n,&m,&p);
    dp[0][0][0]=1;
    for(i=0;i<=n;i++){
        for(j=0;j<=min(m,i);j++){
            if(i || j){
                //printf("%d..",i);
                for(k=0;k<p;k++){
                    dp[i][j][(k*2)%p]+=dp[i-1][j][k];
                    if(j)
                    dp[i][j][(k*2+1)%p]+=dp[i][j-1][k];
                }
            }
        }
    }
    long long int ans=0;
    for(i=0;i<p;i++)
        ans+=dp[n][m][i]*i;
    printf("%lld\n",ans);
}