TopCoder SRM 661 Div2 ColorfulLineGraphsDiv2

題目鏈接:http://community.topcoder.com/stat?c=problem_statement&pm=13842&rd=16464

題意

有n個節點排成一排,有K種顏色,隨意染色
染色完成後選擇顏色不同的點i和j而且j<i,連一條邊,也可以不連
問最後形成的圖有多少種不同的形態

解法

動態規劃
f[i][j]表示前i個節點染色連邊完成且第i個點的顏色爲j的結果

• 當第i個點不和其前面的點連邊: f[i][j] += f[i-1][j]
• 當第i個點和其前面的某個點連邊: f[i][col] += f[i-1][col] * (K - 1) * (i - 1)

class ColorfulLineGraphsDiv2 {
public:
    static const int mod = 1e9 + 7;
    static const int N = 105;
    long long f[N][N];
    int countWays(int N, int K) {
        memset(f,0,sizeof(f));
        for(int i = 0; i < K; i++) {
            f[1][i]=1;
        }
        for(int i = 2; i <= N; i++) {
            for(int col = 0; col < K; col++) {
                //not to add edges
                f[i][col] += f[i-1][col] * K % mod;
                f[i][col] %= mod;
                //add edges
                f[i][col] += (f[i-1][col] * (K - 1)) % mod * (i-1) % mod;
                f[i][col] %= mod;
            }
        }
        int res=0;
        for(int i = 0; i < K; i++) {
             res += f[N][i];
             res %= mod;
        }
        return res;
    }
};