题目大意: 有 n 个灯泡, m 个按钮,(1 <= n, m <= 50), 每个按钮和 ki 个灯泡相关, 按下后, 转换这些灯泡的状态, 问你所有 2^m 的按下按钮的
组合中亮着的灯泡的数量的三次方的和.
思路: 要是将所有灯泡混在一起算很难算, 我们先考虑 所有 2^m 的按下按钮的 组合中亮着的灯泡的数量的和, 我们可以枚举每个灯泡然后, 计算出
有多少中情况这个灯泡是亮着的, 然后全部求和.
现在是三次方的和, 所以要变形一下, 我们设 xi 为第 i 个灯泡的状态 (1 开, 0 关) 那么对于每一种情况我们求的是
(x1 + x2 + x3 + ... + xn) * (x1 + x2 + x3 + ... + xn) * (x1 + x2 + x3 + ... + xn) = sigma(xi * xj * xk), 然后枚举 i,j,k 用 dp 进行计算.
- #include<bits/stdc++.h>
- #define LL long long
- #define fi first
- #define se second
- #define mk make_pair
- #define pii pair<int, int>
- using namespace std;
- const int N = 50 + 7;
- const int M = 1e4 + 7;
- const int inf = 0x3f3f3f3f;
- const LL INF = 0x3f3f3f3f3f3f3f3f;
- const int mod = 1e9 +7;
- const double eps=1e-6;
- const double pi=acos(-1);
- int n, m;
- int dp[N][8];
- bool Map[N][N];
- void add(int &a, LL b) {
- a += b; if(a>= mod) a -= mod;
- }
- int cal(int a, int b, int c) {
- memset(dp, 0, sizeof(dp));
- dp[0][0] = 1;
- for(int i = 1; i <= m; i++) {
- int state = 0;
- if(Map[i][a]) state |= 1;
- if(Map[i][b]) state |= 2;
- if(Map[i][c]) state |= 4;
- for(int s = 0; s < 8; s++) {
- add(dp[i][s], dp[i - 1][s]);
- add(dp[i][s], dp[i - 1][s ^ state]);
- }
- }
- return dp[m][7];
- }
- int main() {
- int T; scanf("%d", &T);
- for(int cas = 1; cas <= T; cas++) {
- memset(Map, false, sizeof(Map));
- scanf("%d%d", &n, &m);
- for(int i = 1; i <= m; i++) {
- int k; scanf("%d", &k);
- while(k--) {
- int x; scanf("%d", &x);
- Map[i][x] = true;
- }
- }
- int ans = 0;
- for(int i = 1; i <= n; i++) {
- for(int j = 1; j <= n; j++) {
- for(int k = 1; k <= n; k++) {
- add(ans, cal(i, j, k));
- }
- }
- }
- printf("Case #%d: %d\n", cas, ans);
- }
- return 0;
- }
- /*
- */
来源: http://www.bubuko.com/infodetail-2684760.html