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

打卡信奥刷题（3104）用C++实现信奥题 PP7263 Something Comforting

news 2026/6/2 0:23:59

P7263 Something Comforting

题目背景

Cause getting made you want more
And hoping made you hurt more
Someone tell me
Something comforting

题目描述

Porter Robinson 花了五年的时间制作了 Something Comforting 这首歌，Mivik 花了五天时间造出了一道和括号序列相关的题。但 Mivik 并不开心，因为他发现他不会造数据了！

Mivik 需要随机生成一个合法的括号序列，于是 Mivik 想了一会，写出了下面的算法：

#include<algorithm>#include<string>std::stringgenerate(intn){// 生成一个长度为 n * 2 的括号序列constintlen=n*2;boolarr[len];// 0 代表左括号，1 代表右括号for(inti=0;i<n;++i)arr[i]=0;for(inti=n;i<len;++i)arr[i]=1;std::random_shuffle(arr,arr+len);// 随机打乱这个数组for(inti=0,j,sum=0;i<len;){sum+=arr[i]?-1:1;if(sum<0){// 出现了不合法的位置for(j=i+1;j<len;++j){sum+=arr[j]?-1:1;if(sum==0)break;}// 现在 i 是第一个不合法的位置，j 是 i 后面第一个合法的位置// ( ( ) ) ) ) ( ( ( ) ( )// i jfor(intk=i;k<=j;++k)arr[k]^=1;// 把这段区间全部反转i=j+1;}else++i;}std::string ret;for(inti=0;i<len;++i)ret+=arr[i]?')':'(';returnret;}

P.S. 为了给其它语言用户带来做题体验，这里提供了多种语言对该算法的描述。

Mivik 十分开心，因为这个算法总能生成合法的括号序列。但不一会儿他就发现这个算法生成的括号序列并不均匀，也就是说，当n nn固定时，所有合法的括号序列出现的概率并不均等。例如，Mivik 发现当n = 3 n=3n=3时，()()()被生成的概率要远大于((()))。

现在 Mivik 给了你一个n nn和一个长度为2 n 2n2n的合法括号序列，假设std::random_shuffle（对于其它语言来说，shuffle）能够均匀随机地打乱一个数组，他想问问你这个括号序列通过上文的算法被生成的概率是多少。由于 Mivik 不喜欢小数，你需要输出这个概率对998244353 998244353998244353取模的结果。如果你不知道如何将一个有理数对质数取模，可以参考有理数取模。

输入格式

第一行一个整数n nn，意义同题面。

接下来输入一个长度为2 n 2n2n的合法括号序列，意义同题面。

输出格式

输出一行一个整数，代表这个概率对998244353 998244353998244353取模的结果。

输入输出样例 #1

输入 #1

1 ()

输出 #1

输入输出样例 #2

输入 #2

3 ()(())

输出 #2

598946612

说明/提示

样例解释

样例一：n nn为 1 时，无论怎样都只可能会生成()这一种合法的括号序列，因此概率为 1。

数据范围

对于全部数据，有1 ≤ n ≤ 5 ⋅ 10 5 1\le n\le 5\cdot 10^51≤n≤5⋅105，且输入的括号序列合法。

Subtask 1（20 pts）：保证1 ≤ n ≤ 5 1\le n\le 51≤n≤5。

Subtask 2（30 pts）：保证1 ≤ n ≤ 1000 1\le n\le 10001≤n≤1000。

Subtask 3（50 pts）：无特殊限制。

C++实现

#include<cstdio>usingnamespacestd;constintmod=998244353;chars[1000002];longlongksm(longlongk,longlongb)//有理数取模{longlongs=1;while(b){if(b&1)s=s*k%mod;b>>=1;k=k*k%mod;}returns;}intmain(){intn,sum=0;scanf("%d%s",&n,s+1);longlongans=1;for(inti=1;i<=2*n;i++){if(s[i]=='(')sum++;elsesum--;if(sum==0)//新的一段{ans=ans*2%mod;}}longlongnum=1;//组合数for(inti=n+1;i<=2*n;i++){num=num*i%mod;}for(inti=1;i<=n;i++){num=num*ksm(i,mod-2)%mod;}printf("%lld",ans*ksm(num,mod-2)%mod);return0;}