题解：CF2187D Cool Problem

· · 题解

人类真的可以想到吗？

改写一下条件，变成：

形式很类似了，唯一的不同是右边的正负性，考虑两边平方一下，于是统一起来了，变成：

(c_i-\frac{x+y}{2})^2=(\frac{y-x}{2}-c_{i-1})^2

化简可以得到：

\left(c_i^2-c_{i-1}^2\right)-y \cdot \left(c_i-c_{i-1}\right)+xy=x \cdot \left(c_i+c_{i-1}\right)

很好看的限制，和 r 具体的取值无关，于是就可以直接表示 f(r) 了：

f(r)=\frac{c_n^2+(x-y)\cdot c_n + nxy}{2x}

证明就是两边求 \sum。

考虑用 DP 求出每个 c_n，发现 c_n 可以用 ax+by 来表示，其中 b\in \{0,1\}，设 f_{i,j,k} 表示目前处理到前 i 位，其中 y 的系数位 k，x 的系数位 j 时能否做到。

注意到 f 的取值只有 0,1，用 bitset 优化即可。

具体地：

转移分类讨论即可，是简单的，最后用求出来的 c_n 算答案就好了，注意去重。

:::success[code] 注意！计算过程中会爆 long long，并且 CF 的老年机不能用 int128，要用 int128_t！

#include<bits/stdc++.h>
#define int long long
#define Bs bitset<100007>
using namespace std;
const int N=1e6+7;
const int Mod=998244353;
int n,x,y;
inline int calc(int c)
{
    __int128_t A=(__int128_t)c*c;
    __int128_t B=(__int128_t)(x-y)*c;
    __int128_t C=(__int128_t)n*x*y;
    __int128_t D=(__int128_t)2*x;
    __int128_t res=(A+B+C)/D;
    return (int)res;
}
int top;
int st[N]; 
inline void solve()
{
    cin>>n>>x>>y;
    string s;
    cin>>s;
    Bs f0,f1,g0,g1;
    f0[0]=g0[0]=1;
    for(auto c:s)
    {
        Bs nf0,nf1,ng0,ng1;
        if(c!='1')
        {
            nf0|=f0<<1;
            nf1|=f1<<1;
            ng0|=g0>>1;
            ng1|=g1>>1;
        }
        if(c!='0')
        {
            nf0|=g1;
            nf1|=g0;
            ng0|=f1;
            ng1|=f0;
        }
        nf0[0]=nf0[0]|ng0[0];
        ng0[0]=ng0[0]|nf0[0];
        nf1[0]=nf1[0]|ng1[0];
        ng1[0]=ng1[0]|nf1[0];
        f0=nf0,f1=nf1,g0=ng0,g1=ng1;
    }
    top=0;
    for(int i=0;i<=n;i++)
    {
        if(f0[i])st[++top]=calc(i*x);
        if(f1[i])st[++top]=calc(i*x+y);
    }
    for(int i=1;i<=n;i++)
    {
        if(g0[i])st[++top]=calc(-i*x);
        if(g1[i])st[++top]=calc(-i*x+y);
    }
    sort(st+1,st+1+top);
    int ans=0;
    for(int i=1;i<=top;i++)
        if(i==1||st[i]!=st[i-1])
            ans=(ans+(st[i]%Mod+Mod))%Mod;
    cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
}

:::