自动搬运

查看原文

来自洛谷，原作者为

	zumgze 这个家伙很懒，什么都留下

搬运于2025-08-24 22:22:38，当前版本为作者最后更新于2020-07-02 10:23:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识： 有理数取余、高中生物

另外吐槽一下，我太菜了，没看懂比赛的题解，只好瞎搞了一个做法（算是前缀和吧）

首先令$p(i,j)$为以$1...i$为结尾的序列中含有$j$个双眼皮基因的概率和。

所有子序列双眼皮的概率和即为 $p(n,1)+p(n,2)$ 。

那么我们的问题就是如何从 $p(i-1,j)$ 求得 $p(i,j)$。

$p(i,j)=p(i-1,j)+$ 以$i$为结尾的序列中含有$j$个双眼皮基因的概率和。

以下分为两种情况： $a_0$直接和$a_i$交配，$a_0$先和$a_{1...i-1}$交配之后才和$a_i$交配。

$a_0$直接和$a_i$交配：直接根据两者基因计算，共九种情况。

$a_0$先和$a_{1...i-1}$交配之后才和$a_i$交配：我们发现，和$a_{1...i-1}$交配的概率就是$p(i-1,j)$，共三种情况，也可以直接计算。

$a_1$~$a_n$的子序列共有$2^n-1$个，统计好答案之后再除以这个数。

注意：以上计算过程中需要时时刻刻对mod取模。

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long a[6000000];
long long p[3];//发现p(i,j)仅与p(i-1,j)有关，所以第一维可省去
long long ksm(long long a,long long n)//用来求逆元
{
	long long ans=1;
	while(n)
	{
		if(n&1)ans=ans*a%mod;
		a=a*a%mod;
		n/=2;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	long long n;
	cin>>n;
	for(long long i=0;i<=n;i++)cin>>a[i];
	long long ans=0;
	long long er=ksm(2,mod-2),si=ksm(4,mod-2);//这两个数用得太多了，就预处理一下
	for(long long i=1;i<=n;i++)
	{
		long long help[3];//储存以i为结尾的序列中含有个双眼皮基因的概率和
		if(a[i]==0)//a0先和a1...ai-1交配之后才和ai交配，分三种情况讨论
		{
			help[0]=(p[0]+p[1]*er%mod)%mod;
			help[1]=(p[2]+p[1]*er%mod)%mod;
			help[2]=0;
		}
		else if(a[i]==1)
		{
			help[0]=(p[0]*er%mod+p[1]*si%mod)%mod;
			help[1]=(p[0]*er%mod+p[1]*er%mod+p[2]*er%mod)%mod;
			help[2]=(p[2]*er%mod+p[1]*si%mod)%mod;
		}
		else if(a[i]==2)
		{
			help[0]=0;
			help[1]=(p[0]+p[1]*er%mod)%mod;
			help[2]=(p[2]+p[1]*er%mod)%mod;
		}
		if(a[0]==0&&a[i]==0)//a0直接和ai交配，分九中情况讨论
		{
			help[0]+=1;
			help[1]+=0;
			help[2]+=0;
		}
		else if(a[0]==0&&a[i]==1)
		{
			help[0]+=er;
			help[1]+=er;
			help[2]+=0;
		}
		else if(a[0]==0&&a[i]==2)
		{
			help[0]+=0;
			help[1]+=1;
			help[2]+=0;
		}
		else if(a[0]==1&&a[i]==0)
		{
			help[0]+=er;
			help[1]+=er;
			help[2]+=0;
		}
		else if(a[0]==1&&a[i]==1)
		{
			help[0]+=si;
			help[1]+=er;
			help[2]+=si;
		}
		else if(a[0]==1&&a[i]==2)
		{
			help[0]+=0;
			help[1]+=er;
			help[2]+=er;
		}
		else if(a[0]==2&&a[i]==0)
		{
			help[0]+=0;
			help[1]+=1;
			help[2]+=0;
		}
		else if(a[0]==2&&a[i]==1)
		{
			help[0]+=0;
			help[1]+=er;
			help[2]+=er;
		}
		else if(a[0]==2&&a[i]==2)
		{
			help[0]+=0;
			help[1]+=0;
			help[2]+=1;
		}
		p[0]=(p[0]+help[0])%mod;
		p[1]=(p[1]+help[1])%mod;
		p[2]=(p[2]+help[2])%mod;
	}
   ans=(p[1]+p[2])%mod;
	cout<<ans*ksm((ksm(2,n)+mod-1)%mod,mod-2)%mod;//最后别忘了要除以子序列的个数
	return 0;
}