Petya and Coloring

[cpp] 
/*
  
題目簡化為求i個塊磚中從k種顏色中選j種，每種顏色至少塗1次的方案數
程序1
dp[i][j]表示前i塊磚在k種不同的顏色中用了j種顏色的方案數
dp[i][j]=(dp[i][j]+dp[i-1][j-1]*(k-j+1))%mod;
dp[i][j]=(dp[i][j]+dp[i-1][j]*j)%mod;
程序2
dp[i][j]表示前i塊磚用j種顏色的方案數,不考慮具體顏色.只看重種數
相當於是一種模式
dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;
dp[i][j]=(dp[i][j]+dp[i-1][j]*j)%mod;
 
 (dp[i][j]*fac[j]%mod)*Cal(k,j)%mod(程序2的dp)=dp[i][j](程序1的dp)
  */ 
 
#include<stdio.h> 
#include<string.h> 
 
typedef __int64 lld; 
const int mod=1000000007; 
const int maxn=1005; 
lld C[maxn][maxn]; 
lld dp[maxn][maxn]; 
lld fac[1000005]; 
int n,m,k; 
 
void init(){ 
    int i,j; 
    fac[0]=1; 
    for(i=1;i<1000005;i++) 
        fac[i]=(fac[i-1]*i)%mod; 
} 
 
lld Mul(lld a,lld b){ 
    lld ret=1; 
    while(b){ 
        if(b&1)ret=ret*a%mod;  
        b>>=1; 
        a=a*a%mod; 
    } 
    return ret; 
} 
 
lld Cal(int x,int y){ 
    lld tmp=fac[x]*Mul(fac[x-y]*fac[y]%mod,mod-2)%mod; 
    return tmp;  
} 
 
int main(){ 
    int i,j; 
    init(); 
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){ 
        memset(dp,0,sizeof(dp)); 
 
        dp[0][0]=1; 
        for(i=1;i<=n;i++){ 
            for(j=1;j<=i;j++){ 
                if(k>=j-1) 
                dp[i][j]=(dp[i][j]+dp[i-1][j-1]*(k-j+1))%mod; 
                dp[i][j]=(dp[i][j]+dp[i-1][j]*j)%mod; 
            } 
        } 
        /*
        for(i=1;i<=15;i++){
            for(j=1;j<=i;j++){
                printf("%I64d ",dp[i][j]);
            }
            puts("");
        }*/ 
        lld ans=0; 
        if(m==1){ 
            printf("%I64d\n",Mul(k,n)); 
        }else{ 
            for(i=1;i<=n && i<=k;i++){//最左最右個有i 
                for(j=(m!=2);j<=i;j++)//中間m-2的部分用j種 
                    if(k>=2*i-j){ 
                    lld tp=Cal(i,j)*Mul(j,n*(m-2))%mod; 
                    lld tg=dp[n][i]*dp[n][i]%mod; 
                    lld tf=Cal(k-i,i-j)*Mul(Cal(k,i),mod-2)%mod; 
                    ans=(ans+((tp*tf%mod)*tg%mod))%mod; 
                }    
            } 
            printf("%I64d\n",ans); 
        } 
     
    } 
    return 0; 
} 
 
 
/*
 
#include<stdio.h>
#include<string.h>
 
typedef __int64 lld;
const int mod=1000000007;
const int maxn=1005;
lld C[maxn][maxn];
lld dp[maxn][maxn];
lld fac[1000005];
int n,m,k;
 
void init(){
    int i,j;
    fac[0]=1;
    for(i=1;i<1000005;i++)
        fac[i]=fac[i-1]*i%mod;
}
 
lld Mul(lld a,lld b){
    lld ret=1;
    while(b){
        if(b&1)ret=ret*a%mod; 
        b>>=1;
        a=a*a%mod;
    }
    return ret;
}
 
lld Cal(int x,int y){
    lld tmp=fac[x]*Mul(fac[x-y]*fac[y]%mod,mod-2)%mod;
    return tmp; 
}
 
int main(){
    int i,j;
    init();
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        memset(dp,0,sizeof(dp));
 
        dp[0][0]=1;
        for(i=1;i<=n;i++){
            for(j=1;j<=i;j++){
                dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;
                dp[i][j]=(dp[i][j]+dp[i-1][j]*j)%mod;
            }
        }
    ***************
        for(i=1;i<=15;i++){
            for(j=1;j<=i;j++){
                if(k>=j)
                printf("%I64d ",(dp[i][j]*fac[j]%mod)*Cal(k,j)%mod);
                else
                printf("0 ");
            }
            puts("");
        }
    ***************
        lld ans=0;
        if(m==1){
            printf("%I64d\n",Mul(k,n));
        }else{
            for(i=1;i<=n && i<=k;i++){//最左最右個有i
                for(j=(m!=2);j<=i;j++)//都有的j
                    if(k>=2*i-j){
                    lld tp=Cal(k,j)*Mul(j,n*(m-2))%mod;
                    lld tf=Cal(k-j,i-j)*Cal(k-i,i-j)%mod;
                    lld tg=((dp[n][i]*dp[n][i]%mod)*(fac[i]*fac[i]%mod))%mod;
                    ans=(ans+((tp*tf%mod)*tg%mod))%mod;
                }   
            }
            printf("%I64d\n",ans);
        }
    }
    return 0;
}
 
*/