标签：博弈 int sum long jcinv jc mod
- 统筹全局，类比今年校赛的E题，博弈双方的地位是平等的。这样，我们只需要求出平局的概率，就可以解出本题了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
int h[30];
long long jc[10000005],jcinv[10000005];
int power(int n,int p)
{
if(p==0)
{
return 1;
}
long long tmp=power(n,p/2);
if(p%2==1)
{
return tmp*tmp%mod*n%mod;
}
return tmp*tmp%mod;
}
void pre()
{
jc[0]=1;
for(int i=1;i<=10000000;i++)
{
jc[i]=jc[i-1]*i%mod;;
}
jcinv[10000000]=power(jc[10000000],998244351);
for(int i=10000000-1;i>=0;i--)
{
jcinv[i]=jcinv[i+1]*(i+1)%mod;
}
}
int main()
{
pre();
int T;
cin>>T;
for(int tt=1;tt<=T;tt++)
{
int n;
cin>>n;
int sum=0,opt=0;
for(int i=1;i<=n;i++)
{
char c;
cin>>c>>h[i];
sum+=h[i];
opt+=(h[i]%2==1);
}
if(sum%2==0)
{
if(opt!=0)
{
printf("%d\n",power(2,998244351));
}
else
{
long long p=1,q=jc[sum]*jcinv[sum/2]%mod;
for(int i=1;i<=n;i++)
{
p=p*jc[h[i]]%mod*jcinv[h[i]/2]%mod;
}
int ans=(q-p+mod)*power(2*q,998244351)%mod;
printf("%d\n",ans);
}
}
else
{
if(opt>1||opt==0)
{
printf("%d\n",power(2,998244351));
}
else
{
long long p=1,q=jc[sum-1]*jcinv[sum/2]%mod*sum%mod;
for(int i=1;i<=n;i++)
{
p=p*jc[h[i]-h[i]%2]%mod*jcinv[h[i]/2]%mod;
if(h[i]%2==1)
{
p=p*h[i]%mod;
}
}
int ans=(q+p)*power(2*q,998244351)%mod;
printf("%d\n",ans);
}
}
}
return 0;
}
标签：博弈,
int,
sum,
long,
jcinv,
jc,
mod
From： https://www.cnblogs.com/watersail/p/18322511