这题和一次的 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 mod=a\times x^{mod-2}\bmod moda÷xmodmod=a×xmod−2modmod。
代码
#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;ll n,cnt,jc[100001];llpw(ll a,ll b,ll mod){//快速幂求逆元ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod,b>>=1;}returnres;}intmain(){cin>>n;jc[0]=1;//预处理阶乘for(ll i=1;i<=n;i++)jc[i]=jc[i-1]*i%998244353;for(ll i=1,x;i<=n;i++)cin>>x,cnt+=x&1;//计算奇数数量//计算组合数cout<<(jc[n]*pw(jc[cnt],998244351,998244353)%998244353)*pw(jc[n-cnt],998244351,998244353)%998244353;return0;//完结散花}原文链接
