首页 > 其他分享 >[ARC132E] Paw

[ARC132E] Paw

时间:2023-12-12 12:55:06浏览次数:37  
标签:ARC132E Paw int 圆点 区间 2n

题目链接

考虑最后形态,一定是有某一个区间 \([l,r]\) 保持初始的样子, \(l\) 前面都是 <,\(r\) 后面都是 >

这个区间一定是某两个相邻圆点的位置。设 \(f_i\) 为前 \(i\) 个数全部被覆盖成 < 的概率。设 \(x\) 为 \(l\) 前面圆点的数量,\(y\) 为 \(r\) 后面圆点的数量,那么区间 \([l,r]\) 的概率就是 \(f_{x}\times f_{y}\)(\(y\) 那里是对称的)。同时区间的 < 数量我们也是好求的。

考虑如何求出 \(f_i\),从 \(f_{i-1}\) 转移。此时 \(i\) 这个圆点有 \(2n\) 种选择(方向两种,时间 \(n\) 种)。唯一不合法的是在第一次就往右走。所以 \(f_{i}=f_{i-1}\times \frac{2n-1}{2n}\)

// LUOGU_RID: 139275577
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,P=998244353;
char s[N];
int inv[N],n,f[N],c,g[N],ans,nx[N];
int main()
{
	inv[1]=1;
	for(int i=2;i<N;i++)
		inv[i]=1LL*(P-P/i)*inv[P%i]%P;
	scanf("%d%s",&n,s+1);
	for(int i=f[0]=1;i<=n;i++)
		c+=s[i]=='.',g[i]=g[i-1]+(s[i]=='<'),f[i]=1LL*f[i-1]*(P+1-inv[2*i])%P;
	s[0]='.',s[n+1]='.';
	for(int i=n;~i;i--)
	{
		nx[i]=nx[i+1];
		if(s[i+1]=='.')
			nx[i]=i+1;
	}
	for(int i=0,p=0;i<=n;i++)
	{
		if(s[i]=='.'&&nx[i])
		{
			(ans+=1LL*f[p]*f[c-p]%P*(i+g[nx[i]-1]-g[i])%P)%=P;
//			printf("%d %d %d %d %d %d\n",i,nx[i],p,c-p,i+g[nx[i]-1]-g[i]);
			++p;
		}
	}
	printf("%d",ans);
}

标签:ARC132E,Paw,int,圆点,区间,2n
From: https://www.cnblogs.com/mekoszc/p/17896537.html

相关文章

  • 无涯教程-Erlang - spawn函数
    这用于创建新进程并对其进行初始化。spawn-语法spawn(Function)Function - 需要产生的功能。spawn-返回值此方法返回一个进程ID。-module(helloLearnfk).-export([start/0]).start()->spawn(fun()->server("Hello")end).server(Message)->io:f......
  • 【DevEco Studio】报错Error: spawn cmd.exe ENOENT怎么解决?
    ​【关键字】hvigor报错、Error:spawncmd.exeENOENT 【问题背景】编译的时候报Error:spawncmd.exeENOENT该怎么解决?预览的时候报Error:spawncmd.exeENOENT该怎么解决?具体报错截图如下:​​ 【解决方案】这种是环境变量缺少了C:\Windows\System32导致的,在Path......
  • 【DevEco Studio】报错Error: spawn cmd.exe ENOENT怎么解决?
    【关键字】hvigor报错、Error:spawncmd.exeENOENT【问题背景】编译的时候报Error:spawncmd.exeENOENT该怎么解决?预览的时候报Error:spawncmd.exeENOENT该怎么解决?具体报错截图如下:【解决方案】这种是环境变量缺少了C:\Windows\System32导致的,在Path里面新建一个把值复制进......
  • [Mac软件]HitPaw Video Converter 功能强大的视频格式转换编辑软件激活版
    软件介绍:以令人难以置信的速度将无损视频和音乐转换为1000多种格式:MP4、MOV、AVI、VOB、MKV等。不仅适用于普通编解码器,也适用于高级VP9、ProRes和Opus编码器。这解决了您不支持格式的所有问题,并允许您在任何平台和设备上播放视频。从10,000多个网站下载和保存视频,包括YouTube、Bil......
  • Unreal入门,通过蓝图自定义Pawn移动
    1.自定义Pawn新建Pawn添加相机和网格体网格体设置(新建项目自带资源里随便挑一个)相机设置(主要是旋转和位移,随便设置下,大概能达到俯视效果就行,其它效果也可以,只要能看到自己的Pawn,不然不知道怎么动的)2.应用自定义Pawn(默认GameMode不可编辑,不能直接替换Default......
  • python多进程:fork模式和spawn模式
    python多进程:fork模式和spawn模式fork模式1.仅unix系统支持,并且是unix系统的默认模式.2.使用该模式创建子进程的时候,会复制父进程的全部变量,支持传参(任意类型)给子进程,但是不会复制父进程的线程.3.该模式相当于将父进程的内存复制一份用于创建子进程.但是由于不复制线程......
  • Nodejs 命令行调用 exec 与 spawn 差异
    Nodejs命令行调用exec与spawn差异比如在前端工程项目中Nodejs要调用命令行命令如:yarnelectron:buildexec调用yarn命令,为了能使命令行能实时打印输出正在编译的命令以异步形式调用exec使用stdout.on方式监听标准输出,并打印//打包electronconstbuildEl......
  • Node.js child_process spawn All In One
    Node.jschild_processspawnAllInOneNode.js多线程//const{spawn}=require('child_process');const{spawn}=require('node:child_process');//$ls-al/usr等价于constls=spawn('ls',['-lh','/usr�......
  • nodejs 使用exec ,execFile,spawn运行子进程区别,以及如何正确的的关闭子进程
    exec,execFile,spawn都是运行一个子进程,但是在不同的操作系统上用法和表现有很大差异。linux/unixexec运行子进程需要创建一个终端环境(命令行窗口),然后在其中运行命令,execFile则不需要,因此在linux/unix上,execFile的效率更高。windows在windows平台上,运行脚本程序(如批处理.bat)必须有......
  • [AGC044E] Random Pawn
    AGC044E首先列出基本的转移式,设\(f_i\)为从i出发期望的最大收益。则\(f_i=\max(a_i,\frac{f_{i-1}+f_{i+1}}{2}-b_i)\)。不难看出a最大的点的期望值一定是a,因为不可能花费b去获得a更小的值。把这个点记为\(a_0\)。考虑如何去掉常数。我们设\(g_i=f_i+d_i\),......