题解归档 - cf2187D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2187D
• 本地来源：problems/cf2187D/idea.md
• 题目链接：https://codeforces.com/contest/2187/problem/D
• 原始标题：cf2187D Cool Problem

思路

cf2187D Cool Problem

Let a_i=1 for 0, a_i=-1 for 1, and p_i=a_1...a_i, p_0=1.

For a fixed completion:

c_i = x*p_i*(p_0+...+p_{i-1}) + (x+y)/2*(1-p_i)

So after telescoping,

f = (x*S^2 - (x+y)*S + y*(n+1))/2, where S=p_0+...+p_n.

Thus only possible final S values matter.

A ? makes the next prefix sign arbitrary. Between two question marks, all fixed bits only multiply that arbitrary sign by known +/-1, so the block contributes either +w or -w to S. The fixed prefix before the first question contributes a constant C.

Therefore:

S = C + sum eps_i*w_i, eps_i in {-1,+1}.

Use subset-sum bitset on abs(w_i):

S = C - A + 2*subset_sum, where A=sum abs(w_i).

Distinctness:

The quadratic has equal values only when S1+S2=(x+y)/x. This can happen only if x|y; otherwise all reachable S give distinct f. When x|y, use canonical key min(S,K-S), K=1+y/x.

Verification:

• Sample.
• Random small strings against exhaustive enumeration of all ? completions.

代码

来源：problems/cf2187D/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
const ll mod=998244353;
const ll inv2=499122177;
char s[maxn+5];
ll a[maxn+5];
vector<unsigned long long>bit;
unordered_set<ll>mp;
ll val(ll x,ll y,ll n,ll S){
    ll z;
    z=((x%mod)*((S%mod+mod)%mod)%mod*((S%mod+mod)%mod)%mod-((x+y)%mod)*((S%mod+mod)%mod)%mod+(y%mod)*((n+1)%mod)%mod)%mod;
    if(z<0) z+=mod;
    return z*inv2%mod;
}
void addbit(ll w,ll A){
    ll i,wd,of,lst;
    unsigned long long v;
    wd=w/64;
    of=w%64;
    lst=A/64;
    for(i=lst;i>=wd;i--){
        v=bit[i-wd]<<of;
        if(of and i-wd-1>=0) v|=bit[i-wd-1]>>(64-of);
        bit[i]|=v;
    }
}
ll getbit(ll x){
    return (bit[x/64]>>(x%64))&1;
}
int main(){
    ll t,n,x,y,i,j,k,zc,pd,cur,dq,cnt,ans,A,C,p,rel,w,S,K,can;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&x,&y);
        scanf("%s",s+1);
        cnt=0;
        C=1;
        p=1;
        i=1;
        while(i<=n and s[i]!='?'){
            if(s[i]=='1') p=-p;
            C+=p;
            i++;
        }
        while(i<=n){
            w=1;
            rel=1;
            i++;
            while(i<=n and s[i]!='?'){
                if(s[i]=='1') rel=-rel;
                w+=rel;
                i++;
            }
            if(w<0) w=-w;
            a[++cnt]=w;
        }
        A=0;
        for(i=1;i<=cnt;i++) A+=a[i];
        bit.assign(A/64+2,0);
        bit[0]=1;
        for(i=1;i<=cnt;i++) if(a[i]) addbit(a[i],A);
        mp.clear();
        ans=0;
        pd=(y%x==0);
        K=1+y/x;
        for(i=0;i<=A;i++){
            if(!getbit(i)) continue;
            S=C-A+2*i;
            if(pd) can=min(S,K-S);
            else can=S;
            if(mp.find(can)!=mp.end()) continue;
            mp.insert(can);
            ans+=val(x,y,n,S);
            ans%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}