官方题解——完美的战役

完美的战役

http://www.nowcoder.com/questionTerminal/9bc0563ac1134cee8d08194f7d40e0a8

F - 完美的战役

首先我们计算每个分支的战力值，考虑每个人对分支战力的贡献，可以得到如下公式： $p[i][j] * \sum_{i = 0}^{n - 1} (i+1) * C_{n-1}^{i}$

将每个人的贡献加起来我们可以得到分支的战力值为： $sum * \sum_{i = 0}^{n - 1} (i+1) * C_{n-1}^{i}$ ，其中 $sum$ 为该分支所有人的战力和。

我们记 $a_n = \sum_{i = 0}^{n} (i + 1) * C_{n}^{i}$ 其中 $a_1 = 3$

$a_n = \sum_{i = 0}^{n} i * C_{n}^{i} + \sum_{i = 0}^{n} C_{n}^{i}$

$= \sum_{i = 1}^{n} i * C_{n}^{i} + 2^n$

由组合数公式 $C_{n+1}^i=C_{n}^i+C_n^{i-1}(i = 1,2,...,n)$ 得

$i*C_{n+1}^i=i*C_{n}^i+i*C_n^{i-1}(i = 1,2,...,n)$

$=i*C_{n}^i+(i - 1)*C_n^{i-1} + C_n^{i - 1}(i = 1,2,...,n)$

累加得

$\sum_{i=1}^ni*C_{n+1}^i=\sum_{i=1}^ni*C_{n}^i+\sum_{i=1}^n(i - 1)*C_n^{i-1} +\sum_{i=1}^n C_n^{i - 1}$

$=\sum_{i=0}^ni*C_{n}^i - 0*C_n^0+\sum_{i=1}^{n + 1}(i - 1)*C_n^{i-1} - n * C_n^n +\sum_{i=1}^{n+1} C_n^{i - 1} - C_n^n$

$=2 * \sum_{i=1}^ni*C_{n}^i + 2^n - n - 1$

代入 $a_{n+1} = \sum_{i = 1}^{n+1} i* C_{n+1}^{i}+2^{n + 1}$ 得

$a_{n+1}= \sum_{i = 1}^{n} i* C_{n+1}^{i} + C_{n+1}^{n + 1}+2^{n + 1}$

$= 2 * \sum_{i=1}^ni*C_{n}^i + 2^n + 2^{n + 1}$

$=2 * a_n + 2^n$

两边同时除以 $2^n$

$\frac{a_{n+1}}{2^n} - \frac{a_{n+1}}{2^{n - 1}}= 1$

又因为 $a_1=3$ ，故 $a_n = (n+2) * 2 ^{n-1}$

所以分支战力计算公式为 $sum*（n + 1） * 2 ^ {n-1}$ ，

由题目可知一个分支训练之后的战力值为该分支原来的战力值转换为二进制后所有为 $1$ 的位。

由数据范围可知 $sum * (n + 1) \le 1e11$ ，而 $2^{n-1}$ 相当于二进制左移了 $n-1$ 位，所以一个分支能够获得战力值为 $sum*(n+1)$ 含有的二进制位左移 $n-1$ ，统计一下每个分支，如果A中含有的二进制位B中都能含有，则输出 $YES$ ，否则 $NO$ 。

#include <bits/stdc++.h>
#include <cstring>
#define MAXN 100003
using namespace std;

int a[MAXN],b[MAXN],sum1[MAXN],sum2[MAXN];
map <int,bool> vis;
using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        vis.clear();
        memset(sum1,0,sizeof(sum1));
        memset(sum2,0,sizeof(sum2));
        int n,m,x;
        scanf("%d%d",&m,&n);
        for(int i = 1;i <= m;i++)
            scanf("%d",&a[i]);
        for(int i = 1;i <= m;i++)
            for(int j = 1;j <= a[i];j++)
            {
                scanf("%d",&x);
                sum1[i] += x;
            }
        for(int i = 1;i <= n;i++)
            scanf("%d",&b[i]);
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= b[i];j++)
            {
                scanf("%d",&x);
                sum2[i] += x;
            }
        //printf("T\n");
        for(int i = 1;i <= n;i++)
        {
            //vis[b[i] - 2] = true;
            long long temp = (long long)(b[i] + 1) * sum2[i];
            int cnt = 0;
            //printf("%d %d %d\n",b[i] - 2,sum2[i],temp);
            while(temp)
            {
                if(temp & 1)
                {
                    vis[cnt + b[i] - 2] = true;
                    //printf("%d\n",cnt + b[i] - 2);
                }
                temp >>= 1;
                ++cnt;

            }
        }
        bool suc = true;
        for(int i = 1;i <= n;i++)
        {
            long long temp = (long long)(a[i] + 1) * sum1[i];
            int cnt = 0;
            while(temp)
            {
                if(temp & 1)
                {
                    if(!vis[cnt + a[i] - 2])
                    {
                        suc = false;
                        break;
                    }
                }
                temp >>= 1;
                ++cnt;
            }
            if(!suc)
                break;
        }
        if(suc)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}