LA 6801 Sequence（DP）

LA 6801 Sequence（DP）

題目大意：

給定n個開關（0/1）的初始狀態，執行k次操作，每次可以任意選擇一個，將其狀態反轉（0-1， 1-0）。問使得最終狀態全是0的方法數%1000000007。

解題思路：

動態規劃。用dp[i][j]表示第i次操作後，還有j個1的方案數。

狀態轉移方程： dp[i][j+1] = dp[i-1][j] * (n-j)

dp[i][j-1] = dp[i-1][j] * j

參考代碼：

// Author: Yuan Zhu
#include 
#include 
#include 
#define ll long long
#define mod 1000000007
using namespace std;

int t, n, k;
int a[1100];
ll dp[1100][1100];

int main() {
    scanf("%d", &t);
    for (int ca = 1; ca <= t; ca++) {
        memset(dp, 0, sizeof dp);
        scanf("%d%d", &n, &k);
        int one = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            if(a[i] == 1) one++;
        }
        dp[0][one] = 1;
        for (int i = 0; i < k; i++) {
            for (int j = 0; j <= n; j++) {
                if (j) dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j] * j) % mod;
                if (j < n) dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * (n - j)) % mod;
            }
        }
        printf("Case #%d: %lld\n", ca, (dp[k][0] % mod + mod) % mod);
    }
    return 0;
}