这题和一次的 atcoder 很像。题意给一个序列可以交换奇偶不同的相邻数字求有几种排列方法。思路奇数和奇数不能交换偶数和偶数不能交换。就是奇数可以在偶数之间移动但是不能穿过奇数。所以可以计算组合方式C c n t n C_{cnt}^nCcntn​其中cnt是奇数的个数。组合数的计算方式C m n n ! m ! × ( n − m ) ! C_m^n\frac{n!}{m!\times(n-m)!}Cmn​m!×(n−m)!n!​可以先预处理阶乘。由于模数是质数所以不会出现无解情况要用快速幂求逆元公式为a ÷ x m o d m o d a × x m o d − 2 m o d m o d a\div x\bmod moda\times x^{mod-2}\bmod moda÷xmodmoda×xmod−2modmod。代码#includebits/stdc.husingnamespacestd;usinglllonglong;ll n,cnt,jc[100001];llpw(ll a,ll b,ll mod){//快速幂求逆元ll res1;while(b){if(b1)resres*a%mod;aa*a%mod,b1;}returnres;}intmain(){cinn;jc[0]1;//预处理阶乘for(ll i1;in;i)jc[i]jc[i-1]*i%998244353;for(ll i1,x;in;i)cinx,cntx1;//计算奇数数量//计算组合数cout(jc[n]*pw(jc[cnt],998244351,998244353)%998244353)*pw(jc[n-cnt],998244351,998244353)%998244353;return0;//完结散花}原文链接