打卡信奥刷题（3045）用C++实现信奥题 P6636 「JYLOI Round 1」性状

P6636 「JYLOI Round 1」性状题目描述小郭给你(n1)(n 1)(n1)个非负整数a0∼ana_0 \sim a_na0​∼an​对于任意0≤i≤n0 \leq i \leq n0≤i≤n有ai∈{0,1,2}a_i \in \{0, 1, 2\}ai​∈{0,1,2}其中aia_iai​表示第iii个人的基因中控制双眼皮的显性基因个数在下文中也代表着这个生物。现在对于原序列中的任意一个子序列bc1∼bcmb_{c_1} \sim b_{c_m}bc1​​∼bcm​​其中1≤cici1≤m1 \leq c_i c_{i 1} \leq m1≤ci​ci1​≤m并且1≤im≤n1 \leq i m \leq n1≤im≤n将a0a_0a0​和bc1b_{c_1}bc1​​进行交配得到子一代并将子一代和bc2b_{c_2}bc2​​交配得到子二代以此类推最后将子(m−1)(m - 1)(m−1)代与bcmb_{c_m}bcm​​进行交配得到子mmm代我们定义这个子序列的价值为子mmm代为双眼皮的概率。由于他很忙于是他现在请你帮他求出所有子序列的价值的平均值在模998244353998244353998244353意义下的值。提示把 0、1、2 分别看作aa、Aa、AA三种字符串两个生物进行交配就是选择每个字符串间长度为 1 的子序列进行大写字母在前小写在后的合并其中这样的一个字符串为子代一种可能的基因组成。其中大写字母开头的为显性性状小写字母开头为隐性性状。双眼皮为显性性状单眼皮为隐性性状结果aa、Aa、AA分别再对应回数字 0、1、2。注意在本题中我们认为眼皮的单双由位于常染色体上的一对等位基因A和a控制其中A相对a为完全显性。且该性状的遗传遵循孟德尔的分离定律并不考虑表观遗传、从性遗传、突变、基因表达的相互影响所有基因型的配子和个体均无致死概率所有个体均能产生可育配子。输入格式输入的第 1 行有一个正整数nnn中间用一个空格隔开nnn的含义如题所述。第二行有(n1)(n 1)(n1)个非负整数这一行中的第iii个数表示aia_iai​。输出格式输出只有一行一个非负整数表示答案。输入输出样例 #1输入 #12 2 1 0输出 #1415935148输入输出样例 #2输入 #250 2 1 2 1 0 0 2 2 0 0 1 2 0 0 0 2 0 0 1 2 1 1 1 1 1 0 1 1 1 0 1 2 0 1 1 0 1 1 2 0 1 0 0 1 1 1 0 1 2 1 1输出 #2576313280说明/提示样例 1 解释子序列{1}\{1\}{1}、{0}\{0\}{0}、{1,0}\{1, 0\}{1,0}的价值分别为111、111和34\dfrac{3}{4}43​平均价值为1112\dfrac{11}{12}1211​对998244353998244353998244353取模后的结果为415935148415935148415935148。数据范围对于100%100\%100%的测试数据1≤n≤5×106,ai∈{0,1,2}1 \leq n \leq 5 \times 10^6, a_i \in \{0, 1, 2\}1≤n≤5×106,ai​∈{0,1,2}。对于测试点 1n1n 1n1。对于测试点 2n2n 2n2。对于测试点 3~5n≤5n \leq 5n≤5。对于测试点 6~10n≤7.5×103n \leq 7.5 \times 10^3n≤7.5×103。本题共有 20 个测试点每个测试点 5 分共 100 分。题目来源「JYLOI Round 1」 BIdeaabcdeffa LiuXiangleSolutionLiuXiangleDataLiuXiangleC实现#includebits/stdc.husingnamespacestd;#definerep(i,n)for(inti1;in;i)#definerpt(i,a,n)for(intia;in;i)#definepre(i,n)for(intin;i;--i)#defineintlonglong#defineswap(x,y)(x^y^x^y)#definedebugcerrHelp!\nconstexprintN5e65,mod998244353,inv499122177;//inv 是 2 的逆元intf[N][3],a[N],n;inlineintqpow(inta,intb){//直接用快速幂求逆元intres1;while(b){if(b1)resres*a%mod;aa*a%mod,b1;}returnres;}signedmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinna[0],f[0][a[0]]1;//初始化到第 0 个人基因是 a[0] 的概率是 100%rep(i,n){cina[i];rpt(j,0,2)f[i][j]f[i-1][j];//暴力分讨if(!a[i]){f[i][0](f[i][0]f[i-1][0]f[i-1][1]*inv)%mod;f[i][1](f[i][1]f[i-1][2]f[i-1][1]*inv)%mod;}elseif(a[i]1){f[i][0](f[i][0]f[i-1][0]*invf[i-1][1]*inv%mod*inv)%mod;f[i][1](f[i][1]f[i-1][0]*invf[i-1][1]*invf[i-1][2]*inv)%mod;f[i][2](f[i][2]f[i-1][2]*invf[i-1][1]*inv%mod*inv)%mod;}else{f[i][2](f[i][2]f[i-1][2]f[i-1][1]*inv)%mod;f[i][1](f[i][1]f[i-1][0]f[i-1][1]*inv)%mod;}}f[n][a[0]](f[n][a[0]]-1mod)%mod;cout(f[n][1]f[n][2])*qpow(qpow(2,n)-1,mod-2)%mod;cerr\n1.0*clock()/CLOCKS_PER_SEC;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容