Loading... ## 题意 给出两个长度均为 $n(n\leq 10^6)$ 的 01 串 $S$ 和 $T$ 每次随机将 $S$ 中的某一位取反 问：第一次 $S = T$ 时操作次数的期望 ## 题解 发现剩余操作次数只取决于不同字符数，与字符串形态无关。设 $dp_i$ 表示还有 $i$ 个不同，剩余操作次数期望。 $$ \begin{align} dp_i=1+\frac{i}{n}dp_{i-1}+\frac{n-i}{n}dp_{i+1}\\ \frac{n-i}{n}dp_{i+1}dp_{i+1}=dp_i-1-\frac{i}{n}dp_{i-1} \end{align} $$ 已知 $dp_0=0$，设 $dp_1=x$，最后根据 $dp_{n}=1+dp_{n-1}$ 解出方程即可。 ```cpp #include<bits/stdc++.h> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE int #define OUTPUT_DATA_TYPE int INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;} #define MODINT_TYPE long long namespace MODINT{ unsigned long long d; __uint128_t m; const unsigned int barK=64; void init(long long mod){ m=(((__uint128_t)1)<<barK)/(d=mod); return; } inline unsigned long long mod(register unsigned long long x){ register unsigned long long w=(m*x)>>barK; w=x-w*d; return w>=d?w-d:w; } MODINT_TYPE exgcd(MODINT_TYPE a,MODINT_TYPE b,MODINT_TYPE &x,MODINT_TYPE &y){ if(!b){ x=1; y=0; return a; } MODINT_TYPE d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } MODINT_TYPE inv(MODINT_TYPE n,MODINT_TYPE p){ MODINT_TYPE x,y; exgcd(n,p,x,y); x%=p; return x>=0?x:x+p; } struct MODNUM{ MODINT_TYPE val; MODNUM(MODINT_TYPE x){ if(x<0){ val=d-mod(-x); if(val>=d) val-=d; }else val=mod(x); return; } MODNUM(){val=0;} inline MODNUM operator + (const MODNUM& o) const{return (MODNUM){(val+o.val>=d)?(val+o.val-d):(val+o.val)};} inline MODNUM operator + (const MODINT_TYPE& o) const{return *this+MODNUM(o);} inline MODNUM operator - (const MODNUM& o) const{return (MODNUM){(val-o.val<0)?(val-o.val+d):(val-o.val)};} inline MODNUM operator - (const MODINT_TYPE& o) const{return *this-MODNUM(o);} inline MODNUM operator * (const MODNUM& o) const{return (MODNUM){mod(val*o.val)};} inline MODNUM operator * (const MODINT_TYPE& o) const{return *this*MODNUM(o);} inline MODNUM operator / (const MODNUM& o) const{return (MODNUM){mod(val*inv(o.val,d))};} inline MODNUM operator / (const MODINT_TYPE& o) const{return *this/MODNUM(o);} inline MODNUM operator ++(){ ++val; if(val>=d) val-=d; return *this; } inline MODNUM operator ++(const int){ MODNUM tmp=*this; ++val; if(val>=d) val-=d; return tmp; } inline MODNUM operator --(){ --val; if(val<0) val+=d; return *this; } inline MODNUM operator --(const int){ MODNUM tmp=*this; --val; if(val<0) val+=d; return tmp; } inline MODNUM& operator += (const MODNUM& o) {return *this=*this+o;} inline MODNUM& operator += (const MODINT_TYPE& o) {return *this=*this+o;} inline MODNUM& operator -= (const MODNUM& o) {return *this=*this-o;} inline MODNUM& operator -= (const MODINT_TYPE& o) {return *this=*this-o;} inline MODNUM& operator *= (const MODNUM& o) {return *this=*this*o;} inline MODNUM& operator *= (const MODINT_TYPE& o) {return *this=*this*o;} inline MODNUM& operator /= (const MODNUM& o) {return *this=*this/o;} inline MODNUM& operator /= (const MODINT_TYPE& o) {return *this=*this/o;} operator MODINT_TYPE(){ return val; } }; }; const long long mod=998244353; MODINT::MODNUM dpB[1000010],dpX[1000010]; char s1[1000010],s2[1000010]; void solve(){ register int i,cnt=0; register MODINT::MODNUM X; int n=read(); scanf("%s%s",s1,s2); for(i=0;i<n;++i) cnt+=(s1[i]!=s2[i]); dpX[1]=1; for(i=1;i<n;++i){ dpB[i+1]=(dpB[i]-1-dpB[i-1]*i/n)*n/(n-i); dpX[i+1]=(dpX[i]-dpX[i-1]*i/n)*n/(n-i); } X=(dpB[n-1]+1-dpB[n])/(dpX[n]-dpX[n-1]); print(dpX[cnt]*X+dpB[cnt]),putchar('\n'); } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif MODINT::init(998244353); register int i; int T=read(); while(T--) solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }/////////// ``` 最后修改：2024 年 03 月 15 日 © 允许规范转载 赞 如果觉得我的文章对你有用，使用点这里使用虚拟货币进行赞赏