CF1778D Flexible String Revisit

题目大意

给出两个长度均为nnn的01序列SSS和TTT，每次随机将SSS中的某一位取反，求第一次S=TS=TS=T时期望的操作次数。

有多组数据。

题解

因为是随机取反的，所以我们只需要知道SSS和TTT中相等的位的数量和不相等的位的数量。

设fif_ifi​表示未匹配的位的数量为iii，翻转序列SSS中不匹配的位置的期望操作次数。

考虑转移。每次有in\dfrac inni​的概率旋转一个不匹配的字符，有n−in\dfrac{n-i}{n}nn−i​的概率翻转一个已匹配的字符。翻转已匹配的字符后需要fi+1f_{i+1}fi+1​的期望操作次数才能回到当前状态，然后还需要fif_ifi​的期望操作次数才能再翻转一个未匹配字符，那么

fi=in×1+n−in×(1+fi+1+fi)f_i=\dfrac in\times 1+\dfrac{n-i}{n}\times (1+f_{i+1}+f_i)fi​=ni​×1+nn−i​×(1+fi+1​+fi​)

化简得

fi=n+(n−i)fi+1if_i=\dfrac{n+(n-i)f_{i+1}}{i}fi​=in+(n−i)fi+1​​

当然，fn=1f_n=1fn​=1，因为在这种情况下无论怎么翻转，都会翻转一个未匹配字符。

设当前有kkk个字符未匹配，那么答案为fk+fk−1+⋯+f1f_k+f_{k-1}+\cdots+f_{1}fk​+fk−1​+⋯+f1​。

时间复杂度为O(∑n)O(\sum n)O(∑n)。当然，如果提前处理fff数组，那么时间复杂度可以达到O(mxn+t)O(mxn+t)O(mxn+t)，mxn表示输入中最大的nnn。

code

#include
using namespace std;
int t,n,v;
char a[1000005],b[1000005];
long long ans,f[1000005];
long long mod=998244353;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);scanf("%s%s",a,b);v=0;for(int i=0;i<=n;i++) f[i]=0;for(int i=0;iif(a[i]!=b[i]) ++v;}f[n]=1;for(int i=n-1;i>=1;i--){f[i]=(n+(n-i)*f[i+1])%mod*mi(i,mod-2)%mod;}ans=0;for(int i=v;i>=1;i--){ans=(ans+f[i])%mod;}printf("%lld\n",ans);}return 0;
}