题解：AT_arc191_e [ARC191E] Unfair Game

· · 题解

[ARC191E] Unfair Game

先考虑只有一个背包怎么做。

为了方便起见，我们将 X 和 Y 都 +1 ，这样他们的含义就为：一个金币等价于多少个银币。

显然，如果 a=0 ，则先手必胜当且仅当 b 为奇数。可以发现获胜条件仅和 b 的奇偶性有关，和其具体数值无关，因此我们可以将其看作 01 变量。对于 X,Y 同理。

如果 X = Y ，那么不论是谁去选金币都一样，因此可以直接看 a X + b 的奇偶性。

否则，如果 X=1 ，那么先手可以在第一步就根据 b 来判断选的是金币还是银币，使得在第一步后留给后手的 b = 0 ，此后只要一直选银币就行了。因此只要 a > 0 ，则先手必胜。若 a = 0 ，那么直接看 b 就行了。

若 Y=1 ，那么就有一点不同了。如果 a > 1 ，是后手必胜。但是如果 a=1 ，那么先手可以选择在第一步直接把金币拿掉，因此要特判这种情况。

现在扩展到多个背包，但是每个背包一开始分别在谁手里已经固定了的情况。如果一个背包是先手必败的，那么这个背包就是一个废包，我们不去管他。对于先手必胜的包，我们可以看作使用掉一个包，让对方变成先手。因此假设 Takahashi 有 x 个先手必胜的包，Aoki 有 y 个，那么 Takahashi 能够获胜当且仅当 x>y 。

那么对于每个背包，我们都可以表示成一个 01 数对 (a,b) ，表示这个背包分别对 Takahashi 和 Aoki 来说是否是先手必胜的。如果是 (0,0) ，那么这个包给谁都一样。如果这个背包是 (1,1) ，那么我们可以先让给 Aoki 一个包，然后将这个包转化成 (2,0) 。如果是 (0,1) ，那么就让给 Aoki 一个包，然后将这个包转化成 (1,0) 。

最后会变成 \sum\limits_{2i + j > z} \binom{x}{i} \binom{y}{j} 的形式，由于 x,y,z 的大小都不超过 n ，因此可以枚举 i ，然后对 j 处理后缀和。复杂度 O(n) 。

#include<bits/stdc++.h>
#define ll long long
#define pn putchar('\n')
#define mset(a,x) memset(a,x,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof a)
#define all(a) a.begin(),a.end()
#define fls() fflush(stdout)
#define int ll
using namespace std;
int re()
{
    int x=0;
    bool t=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
        t=ch=='-'?0:t,ch=getchar();
    while(ch>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return t?x:-x;
}
const int maxn=2e5+5,mod=998244353;
int ksm(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=ret*x%mod;
        x=x*x%mod,y>>=1;
    }
    return ret;
}
void dq(int &x)
{
    if(x>=mod)
        x-=mod;
}
int n;
bool A,B;
int c1,c2,tot,mul=1;
int ans;
int jc[maxn],inv[maxn];
void zh_init()
{
    jc[0]=1;
    for(int i=1;i<=n;i++)
        jc[i]=jc[i-1]*i%mod;
    inv[n]=ksm(jc[n],mod-2);
    for(int i=n;i;i--)
        inv[i-1]=inv[i]*i%mod;
}
int C(int x,int y)
{
    return jc[x]*inv[x-y]%mod*inv[y]%mod;
}
signed main()
{
    n=re(),A=re()+1&1,B=re()+1&1;
    zh_init();
    while(n--)
    {
        int x=re(),y=re();
        bool t1=A==B?A*x+y&1:A&1?x||y&1:x<=1&&y&1;
        bool t2=A==B?A*x+y&1:B&1?x||y&1:x<=1&&y&1;
        if(t2)
            tot++;
        if(t1&&t2)
            c1++;
        if(t1!=t2)
            c2++;
        if(!t1&&!t2)
            dq(mul*=2);
    }
    for(int i=0,j=c2,cur=0;i<=c1;i++)
    {
        while(~j&&2*i+j>tot)
        {
            dq(cur+=C(c2,j));
            j--;
        }
        (ans+=C(c1,i)*cur)%=mod;
    }
    printf("%lld\n",ans*mul%mod);
    return 0;
}