题解 P6636 【「JYLOI Round 1」性状】
zumgze
·
·
题解
前置知识： 有理数取余、高中生物
另外吐槽一下，我太菜了，没看懂比赛的题解，只好瞎搞了一个做法（算是前缀和吧）
首先令p(i,j)为以1...i为结尾的序列中含有j个双眼皮基因的概率和。
所有子序列双眼皮的概率和即为 p(n,1)+p(n,2)
。
那么我们的问题就是如何从 p(i-1,j) 求得 p(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取模。
```cpp
#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;
}
```