题解归档 - cf2234D

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

• 本地编号：cf2234D
• 本地来源：problems/cf2234D/idea.md
• 题目链接：https://codeforces.com/contest/2234/problem/D
• 原始标题：cf2234D 思路

思路

cf2234D 思路

dpk 递归（用户）

1-bit 计数 dp[k][s,e]，s,e∈{0,1} → 00,01,10,11 四态。

• mid = s^e
• left = dp[k-1][s,mid]，right = dp[k-1][mid,e]
• 合并：left+right，中点下标减一次（两端子段共享中点）

explore_dp.py 已验证 cnt01。

n 位答案递推（验证通过）

M = S xor Z（逐位）

ans[k][S,Z] = ans[k-1][S,M] + ans[k-1][M,Z] - pop(M)*(n-pop(M))

k=0 只有两个端点。

瓶颈

• 1-bit 的 x*y 恒 0，不能单 bit 答案直接加
• n 位 state 是 (S,Z) 向量，不是 4 态；不能 O(1) memo
• 需 O(n) 压成可算形式（如 pop 与交叉项）

代码

来源：problems/cf2234D/solution.cpp

/* Author: likely
 * Time: 2026-06-07 23:15:59
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string st,zt,ss[4];
ll pc[4],n,k;
char vis[31][4][4];
__int128 sp[31][4][4],sp2[31][4][4];
void dfs(ll kk,ll a,ll b,__int128 &cur,__int128 &cur2){
    ll zc;
    if(vis[kk][a][b]){
        cur=sp[kk][a][b];
        cur2=sp2[kk][a][b];
        return;
    }
    if(kk==0){
        cur=pc[a]+pc[b];
        cur2=(__int128)pc[a]*pc[a]+(__int128)pc[b]*pc[b];
        vis[kk][a][b]=1;
        sp[kk][a][b]=cur;
        sp2[kk][a][b]=cur2;
        return;
    }
    zc=a^b;
    __int128 sl,sr,spl,spr;
    dfs(kk-1,a,zc,sl,spl);
    dfs(kk-1,zc,b,sr,spr);
    cur=sl+sr-pc[zc];
    cur2=spl+spr-(__int128)pc[zc]*pc[zc];
    vis[kk][a][b]=1;
    sp[kk][a][b]=cur;
    sp2[kk][a][b]=cur2;
}
int main(){
    ll t,i,j,kk;
    __int128 cur,cur2,ans;
    cin>>t;
    while(t--){
        cin>>n>>k;
        cin>>st>>zt;
        ss[0].assign(n,'0');
        ss[1]=st;
        ss[2]=zt;
        ss[3].assign(n,'0');
        for(i=0;i<n;i++) ss[3][i]=(char)((st[i]-'0')^(zt[i]-'0')+'0');
        for(i=0;i<4;i++){
            pc[i]=0;
            for(j=0;j<n;j++) pc[i]+=ss[i][j]-'0';
        }
        for(i=0;i<=k;i++) for(j=0;j<4;j++) for(kk=0;kk<4;kk++) vis[i][j][kk]=0;
        dfs(k,1,2,cur,cur2);
        ans=(__int128)n*cur-cur2;
        cout<<(ll)ans<<"\n";
    }
    return 0;
}