专栏文章

题解：AT_arc191_e [ARC191E] Unfair Game

__abcd_
AT_arc191_e题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqd49i9
此快照首次捕获于
2025/12/04 02:50
3 个月前
此快照最后确认于
2025/12/04 02:50
3 个月前
查看原文

[ARC191E] Unfair Game

先考虑只有一个背包怎么做。
为了方便起见，我们将 XX 和 YY 都 +1+1，这样他们的含义就为：一个金币等价于多少个银币。
显然，如果 a=0a=0，则先手必胜当且仅当 bb 为奇数。可以发现获胜条件仅和 bb 的奇偶性有关，和其具体数值无关，因此我们可以将其看作 0101 变量。对于 X,YX,Y 同理。
如果 X=YX = Y，那么不论是谁去选金币都一样，因此可以直接看 aX+ba X + b 的奇偶性。
否则，如果 X=1X=1，那么先手可以在第一步就根据 bb 来判断选的是金币还是银币，使得在第一步后留给后手的 b=0b = 0，此后只要一直选银币就行了。因此只要 a>0a > 0，则先手必胜。若 a=0a = 0，那么直接看 bb 就行了。
若 Y=1Y=1，那么就有一点不同了。如果 a>1a > 1，是后手必胜。但是如果 a=1a=1，那么先手可以选择在第一步直接把金币拿掉，因此要特判这种情况。
现在扩展到多个背包，但是每个背包一开始分别在谁手里已经固定了的情况。如果一个背包是先手必败的，那么这个背包就是一个废包，我们不去管他。对于先手必胜的包，我们可以看作使用掉一个包，让对方变成先手。因此假设 Takahashi 有 xx 个先手必胜的包，Aoki 有 yy 个，那么 Takahashi 能够获胜当且仅当 x>yx>y。
那么对于每个背包，我们都可以表示成一个 0101 数对 (a,b)(a,b)，表示这个背包分别对 Takahashi 和 Aoki 来说是否是先手必胜的。如果是 (0,0)(0,0)，那么这个包给谁都一样。如果这个背包是 (1,1)(1,1)，那么我们可以先让给 Aoki 一个包，然后将这个包转化成 (2,0)(2,0)。如果是 (0,1)(0,1)，那么就让给 Aoki 一个包，然后将这个包转化成 (1,0)(1,0)。
最后会变成 ∑2i+j>z(xi)(yj)\sum\limits_{2i + j > z} \binom{x}{i} \binom{y}{j} 的形式，由于 x,y,zx,y,z 的大小都不超过 nn，因此可以枚举 ii，然后对 jj 处理后缀和。复杂度 O(n)O(n)。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...