当前位置: 首页 > news >正文

Codeforces Round #848 (Div. 2) D - Flexible String Revisit

Codeforces Round #848 (Div. 2) D - Flexible String Revisit

题意:给定两个 题意:给定两个 题意:给定两个 01 01 01 字符串 字符串 字符串 a a a 和 和 b b b 每次操作可选择字符串 每次操作可选择字符串 每次操作可选择字符串 a a a 上的数字反转 上的数字反转 上的数字反转 即: 0 即:0 即:0 − > 1 ->1 >1 或者 1 1 1 − > 0 。 -> 0。 >0 每个位上操作的 每个位上操作的 每个位上操作的 概率相同 即每个位上操作的概率都是 1 / n 即每个位上操作的概率都是1/n 即每个位上操作的概率都是1/n 现问将字符串 a 翻转成 b 的期望步数是多少。 现问将字符串a翻转成b的期望步数是多少。 现问将字符串a翻转成b的期望步数是多少。

公式推导: 公式推导: 公式推导:
在这里插入图片描述
参考代码: 参考代码: 参考代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#pragma GCC optimize(3)
typedef pair<int,int>PII;
#define pb push_back
const int N = 1e6+10;
const int mod = 998244353;
int inv[N];
int c[N],d[N];//kx+b
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void cf(){
    int sum=0;
    int n;
    cin>>n;
    string a,b;
    cin>>a>>b;
    for(int i=0;i<a.size();i++){
        if(a[i]!=b[i])sum++;
    }
    c[0]=d[0]=d[1]=0;
    c[1]=1;
    for(int i=2;i<=n;i++){
        c[i] = (c[i-1]*n-c[i-2]*(i-1))%mod*inv[n-i+1]%mod;
        d[i] = (d[i-1]*n-d[i-2]*(i-1)-n)%mod*inv[n-i+1]%mod;
    }
    int dp1=(1+d[n-1]-d[n])*qmi(c[n]-c[n-1],mod-2)%mod;
    int ans=(c[sum]*dp1+d[sum])%mod;
    if(ans<0)ans+=mod;
    cout<<ans<<endl;
    return ;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    inv[1]=1;
    for(int i=2;i<N;i++){//O(n)线性求区间逆元
        inv[i]=mod-mod/i*inv[mod%i]%mod;
    }
    int _=1;
    cin>>_;
    while(_--){
        cf();
    }
    return 0;
}

相关文章:

  • 「题解」字符串中的所有单词进行倒排
  • 关于符合车规的高精度定位产品
  • 【Linux】基础网络编程
  • torch_geometric--Convolutional Layers
  • Java——OpenJDK和JDK的区别
  • Windows实时运动控制软核(六):LOCAL高速接口测试之Matlab
  • 下一代编解码技术Ali266在视频超高清领域的应用展望
  • 【K8S之调度器流程和扩展】如何给 scheduler 添加扩展插件、关闭默认插件、创建多个 scheduler?
  • kob配置git环境与项目创建
  • moment.js根据时间戳计算与当前时间相差多少天
  • VS2017编译gsf/surf/mbio —E0020 未定义标识符 “F_OK“
  • 【完美解决】Github action报错remote: Write access to repository not granted.
  • vulnhub之PRIME (2021): 2
  • 【C++修炼之路】C++入门(下)
  • 【Android Studio】【Flutter】Android Studio下Flutter环境搭建记录
  • Vue3 中使用组合式API替换mixins,达到代码复用并解决隐患
  • 规则引擎-drools-3.3-drl文件构成-rule部分-条件Condition
  • 企业怎么能上百度百科词条,创建百科方法
  • 3-1多线程-线程池
  • Linux-远程管理命令
  • 电加热油锅炉工作原理_电加热导油
  • 大型电蒸汽锅炉_工业电阻炉
  • 燃气蒸汽锅炉的分类_大连生物质蒸汽锅炉
  • 天津市维修锅炉_锅炉汽化处理方法
  • 蒸汽汽锅炉厂家_延安锅炉厂家
  • 山西热水锅炉厂家_酒店热水 锅炉
  • 蒸汽锅炉生产厂家_燃油蒸汽发生器
  • 燃煤锅炉烧热水_张家口 淘汰取缔燃煤锅炉
  • 生物质锅炉_炉
  • 锅炉天然气_天燃气热风炉