Game

Bob wants to play a game with Alice.

At the beginning of the game, Bob will write down two binary strings $s,t$ ( $1$ -indexed) and show these two strings to Alice.

During the game, Alice can bribe Bob with some coins in order to ask him to change a single letter on $t$ .Alice needs to give $v_i$ coins to Bob if he prepares to change the $i$ -th letter on $t$ .Alice can bribe Bob as many times(including zero) as she wants.

Denotes $t'$ as the string changed from $t$ .Bob will give Alice $(f(s,t'))^2$ coins after changing the string $t$ ,where $f(s_1,s_2)$ represents the length of longest prefix of $s_2$ (could be empty) such that this prefix is a substring of $s_1$ .

Being a successful businessman, Alice has so many coins that its number can be considered infinity. Obviously, it is Alice's nature to earn as many coins as possible. The number of coins that Alice earns is defined by $(f(s,t'))^2$ minus the sum of the coins Alice gave to Bob.

Please find out the maximum number of coins that Alice can earn.

小A和小B在玩一个有趣的游戏。
游戏开始时，小B会给小A写下两个从 $1$ 开始编号的只由 $0,1$ 组成的字符串 $s,t$ 。

在玩游戏的过程中，小A可以给小B $v_i$ 个金币，这样他就可以改变字符串 $t$ 的第 $i$ 个字符了。小A可以执行这个操作任意次，也可以一次也不执行。

设 $t'$ 为 $t$ 在小A执行完所有操作后的字符串。小B会给小A $(f(s,t'))^2$ 个金币作为奖励。其中， $f(s_1,s_2)$ 表示 $s_2$ 最长合法前缀的长度，合法指该前缀为 $s_1$ 中的子串。

作为一个成功的商人，小A的金币数量可视作无穷。显然，小A想要获得最多的金币。小A获得的金币数量定义为 $(f(s,t'))^2$ 减去小A交给小B的金币数量之和。

请你求出小A最多能获得多少金币。

The first line contains a single integer $T$ - the number of test cases.

Then the description of $T$ test cases follows. For each test case:

The first line contains two integers $n,m$ - the length of string $s$ and the length of string $t$ .

The second line contains a binary string $s$ .

The third line contains a binary string $t$ .

The forth line contains $m$ integers $v_1,v_2,\cdots,v_m$ ,where $v_i$ represents the number of coins Alice should give to Bob if he wants to change the $i$ -th letter on $t$ .

It is guaranteed that $1\le T\le 10^5,1\le n,m\le 2\times 10^5,\sum n,\sum m\le 10^6,0\le val_i \le 50$ .

第一行，一个正整数 $T$ ，表示数据组数。

接下来，对于每组数据：

第一行两个正整数 $n,m$ ，分别表示字符串 $s,t$ 的长度。

第二行一个长度为 $n$ 的01字符串 $s$ 。

第三行一个长度为 $m$ 的01字符串 $t$ 。

第三行 $m$ 个非负整数 $v_1,v_2,\cdots,v_m$ ，其中 $v_i$ 表示当小A改变 $t_i$ 时，要交给小B的金币数量。

#include<bits/stdc++.h> using namespace std; #define ll long long const ll mod=998244353,G=3; namespace NTT{ ll f[2097160],g[2097160]; int tr[2097160]; ll quickpow(ll a,ll p){ ll res=1; while(p){ if(p&1)res=res*a%mod; p>>=1; a=a*a%mod; } return res; } void NTT(ll *f,int n,int flag){ for(int i=0;i<n;i++)if(i<tr[i])swap(f[i],f[tr[i]]); for(int p=2;p<=n;p<<=1){ int len=p>>1; ll Ur=quickpow(flag?G:quickpow(G,mod-2),(mod-1)/p); for(int k=0;k<n;k+=p){ ll now=1; for(int i=k;i<=k+len-1;i++){ ll num=now*f[i+len]%mod; f[i+len]=(f[i]-num+mod)%mod; f[i]=(f[i]+num)%mod; now=now*Ur%mod; } } } } void solve(int n,int m){ m+=n; n=1; while(n<=m)n<<=1; for(int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?(n>>1):0); NTT(f,n,1);NTT(g,n,1); for(int i=0;i<n;i++)f[i]=f[i]*g[i]; NTT(f,n,0); for(int i=0;i<=m;i++)f[i]=f[i]*quickpow(n,mod-2)%mod; } } int n,m; char s[200005],t[200005]; int val[200005]; int sum[200005]; int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); scanf("%s",s+1);scanf("%s",t+1); for(int i=1;i<=m;i++)scanf("%d",&val[i]); if(m<=50){ int ans=0; for(int i=1;i<=n;i++){ int mx=0,sum=0; for(int j=0;j<min(m,n-i+1);j++){ mx=max(mx,j*j-sum); if(t[j+1]!=s[i+j])sum+=val[j+1]; } mx=max(mx,min(m,n-i+1)*min(m,n-i+1)-sum); ans=max(ans,mx); } printf("%d\n",ans); }else{ m=min(n,m); ll ans=0; for(int i=max(1,n-50+1);i<=n;i++){ ll mx=0,sum=0; for(int j=0;j<min(m,n-i+1);j++){ mx=max(mx,1ll*j*j-sum); if(t[j+1]!=s[i+j])sum+=val[j+1]; } mx=max(mx,1ll*min(m,n-i+1)*min(m,n-i+1)-sum); ans=max(ans,mx); } for(int i=0;i<=(n+m)*4;i++)NTT::f[i]=NTT::g[i]=0; for(int i=0;i<n;i++)NTT::f[i]=s[n-i]-'0'; for(int j=1;j<=m;j++)NTT::g[j]=(2*(t[j]-'0')*val[j]-val[j]+mod)%mod; NTT::solve(n,m); for(int i=1;i<=m;i++)sum[i]=sum[i-1]+(t[i]-'0')*val[i]; for(int i=1;i<=n;i++){ int len=min(m,n-i+1); ll v=NTT::f[n-i+1]; if(v+1e7>=mod)v-=mod; ans=max(ans,1ll*len*len-sum[len]+v); } printf("%lld\n",ans); } } return 0; }

详情