HDU 5117 Fluorescent

题目链接：HDU-5117

题意为有n盏灯，m个开关，每个开关控制着\( k_{i} \)灯。X为最后亮着的灯的个数，要求出\( E(X^{3} ) * 2^{M} mod (10^9 + 7) \)。

可以看出\( E(X^{3} ) * 2^{M} = \sum (X^{3} * (\frac{1}{2})^{m}) * 2^{m} = \sum X^{3} \)

然后将 \( \sum X^{3} \) 分解为\( \sum X^{3} = \sum_{i,j,k = 1}^{n} x_{i} * x_{j} * x_{k} \)

于是问题就转化成了求对于所有的i，j，k，有多少种情况i，j，k都亮着。

于是我们可以写出状态转移方程f[i][j][k][state][ii] = f[i][j][k][state][ii-1] + f[i][j][k][state ^ \( switch_{ii}\)][ii-1];

其中f[i][j][k][state][ii]表示使用前ii个开关使i，j，k的状态为state的方案数。

我们发现i，j，k其实没有必要记录。所以进一步，我们可以把方程优化为f[state][ii] = f[state][ii-1] + f[state ^ switch[ii]][ii-1];

另外还有一个需要注意的小细节是注意使用1LL。

代码如下：

 #include<cstdio>

 #include<set>

 #include<map>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<iostream>

 using namespace std;

 typedef long long LL;

 const LL MOD = 1e9 + ;

 const LL MAXN = ;

 LL d[MAXN];

 int main()

 {

 #ifdef LOCAL

     freopen("in.txt","r",stdin);

 #endif

     LL t;

     scanf("%lld",&t);

     for(LL tt = ; tt <= t; tt++)

     {

         memset(d,,sizeof(d));

         LL n,m;

         scanf("%lld%lld", &n, &m);

         for(LL i = ; i <= m; i++)

         {

             LL k;

             scanf("%lld", &k);

             for(LL j = ; j <= k; j++)

             {

                 LL tmp;

                 scanf("%lld", &tmp);

                 d[i] += (1LL << (tmp-));

             }

         }

         LL ans=;

         for(LL i = ; i <= n; i++)

             for(LL j = ; j <= n; j++)

                 for(LL k = ; k <= n; k++)

                 {

                     LL f[][MAXN];

                     memset(f,,sizeof(f));

                     f[][]=;

                     for(LL ii = ; ii <= m; ii++)

                     {

                         LL ss=;

                         if(d[ii] & (1LL << (i-))) ss ^= ;

                         if(d[ii] & (1LL << (j-))) ss ^= ;

                         if(d[ii] & (1LL << (k-))) ss ^= ;

                         for(LL jj=;jj<=;jj++)

                         {

                             f[jj][ii] += f[jj][ii-];

                             f[jj][ii] += f[jj ^ ss][ii - ];

                         }

                     }

                     ans = (ans + f[][m]) % MOD;

                     //printf("%lld %lld %lld %lld\n", i, j, k, ans);

                 }

         printf("Case #%lld: %lld\n", tt, ans);

     }

     return ;

 }

巴特西

HDU 5117 Fluorescent

最新文章

热门文章