题意

给出n个灯，m个开关，每个开关控制一些灯，如果打开这个开关，这个开关控制的灯如果本来灭的就会亮，如果本来亮的就会灭。问在每个开关按下与否的一共2^m情况下，每种状态下亮灯的个数的立方的和。

思路

对于枚举2^m种情况是不实际的。题目要求的求立方和暗含玄机。

设每个灯的状态为X。

ans = X^3 = (X1 + X2 + X3 + ... + Xn) * (X1 + X2 + X3 + ... + Xn) * (X1 + X2 + X3 + ... + Xn)
= X1 * X1 * X1 + X1 * X1 * X2 + X1 * X1 * X3 + ... + Xn * Xn * Xn

意味着只有当前枚举的三个灯同时亮，才会对最后的答案有贡献。

可以枚举三个灯，然后状态压缩三个灯的情况，然后累加求解。

dp[x][st] 代表使用前 x 个开关得到状态为 st 的情况有多少种。

dp[x][st] += dp[x-1][st] （不使用开关的情况）。

dp[x][now] += dp[x-1][st] （使用开关的情况，now为状态为 st 的情况打开了第 x 个开关后的状态）。

ans += dp[m][7] （因为只有三个灯一起亮才对结果有贡献，7就是三个灯状压后全亮的情况）。

复杂度O（n^3 * m * 7）。

···C++

include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 50 + 11;
const int MOD = 1e9 + 7;
LL op[N];
int dp[N][11];
int main() {
int t; scanf("%d", &t);
for(int cas = 1; cas <= t; cas++) {
printf("Case #%d: ", cas);
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
int x; scanf("%d", &x); op[i] = 0;
for(int j = 0; j < x; j++) {
int y; scanf("%d", &y); y--;
op[i] |= (1LL << y);
}
}
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int x = 0; x < m; x++) {
for(int st = 0; st < 8; st++) {
int now = st;
if(op[x] & (1LL << i)) now ^= 1;
if(op[x] & (1LL << j)) now ^= 2;
if(op[x] & (1LL << k)) now ^= 4;
dp[x+1][st] = (dp[x+1][st] + dp[x][st]) % MOD; // off
dp[x+1][now] = (dp[x+1][now] + dp[x][st]) % MOD; // On
}
}
ans = (ans + dp[m][7]) % MOD;
}
}
}
printf("%d\n", ans);
}
return 0;
}
```

巴特西

HDU 5117：Fluorescent（状压DP + 思维）***

题意

思路

include <bits/stdc++.h>

最新文章

热门文章