SRM 572 div2 1000

[cpp]  
/* 
注意dp的for循环，状态之间的重复计算 
dp[i][j]表示i种不同的余数的和为j的方法树 
 
  */  
#include<stdio.h>  
#include<string.h>  
  
typedef long long  lld;  
const int mod=1000000007;  
lld dp[52][1300];  
lld fac[52];  
  
class DistinctRemainders{  
public:  
    lld Bin(lld a,lld b){  
        lld ret=1;  
        while(b){  
            if(b&1)ret=ret*a%mod;  
            b>>=1;  
            a=a*a%mod;  
        }  
        return ret;  
    }  
    void init(int M){  
        memset(fac,0,sizeof(fac));  
        fac[0]=1;  
        for(int i=1;i<=M;i++)  
            fac[i]=fac[i-1]*i%mod;  
    }  
    lld Kao(lld x,lld y){  
        lld ret=1;  
        for(lld i=1;i<=y;i++){  
            ret=ret*x%mod;  
            x--;  
        }  
        return ret;  
    }  
    lld Gao(lld x,lld y){  
        return Kao(y,x)*Bin(Kao(x,x),mod-2)%mod;  
    }  
    int howMany(lld N, int M){  
        int i,j,k;  
        init(M);  
        memset(dp,0,sizeof(dp));  
        dp[0][0]=1;  
        for(i=0;i<M;i++){  
            for(j=M;j>0;j--){  
                for(k=M*M/2;k>=i;k--){  
                    if(!dp[j-1][k-i])continue;  
                    dp[j][k]=(dp[j-1][k-i]+dp[j][k])%mod;  
                //  printf("dp[%d][%d]=%lld \n",i,j,dp[i][j]);  
                }  
            }  
        }  
        lld ans=0;  
        for(i=1;i<=M;i++){  
            for(j=0;j<=M*M/2;j++){  
                if(!dp[i][j])continue;  
                if(j>N || (N-j)%M!=0)continue;  
                ans=(ans+(dp[i][j]*fac[i]%mod)*Gao(i-1,(N-j)/M%mod+i-1))%mod;  
                printf("i==%d j==%d %lld \n",i,j,ans);  
            }  
        }  
        return (int)ans;  
    }  
};  
 

补充：软件开发 , C++ ,

上一个：外观模式
下一个：消息模式