 |
6801 - Sequence |
题目大意：
给定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; }