P6561 [SBCOI2020] 人 考虑把 2i−1, 2i (0i≤m)2i-1,\ 2i\ (0 放在一起看，那么每组一共有三种情况： A：2i−12i-1 选，2i2i 不选。 B： 不选，2i2i 选。 C：都不选。 且有一个限制，就是不允许相邻两个组别组成 BA 的形式，因为这样前一组的第二个和后一组的第一个成为了相邻的数，此时不符合题意。 所以我们把问题转化一下，就变成了：有多少种不出现 BA 形式的 A、B、C 组合？ 设 A、B 情况分别有 a,ba,b 个，那么 C 情况就有 m−a−bm-a-b 个。 考虑放好 C 以后往相邻的两个 C 之间填 A、B，因为不能出现 BA 形式，所以只能把所有的 A 放在前面，把所有的 B 放在后面。也就是说，A、B 的数量确定时，方案数只有一个。 现在问题就变成了往相邻的两个 C 之间填 A、B 的方案数，由于放 A 与放 B 相互独立，所以可以使用乘法原理。 先考虑往 m−a−bm-a-b 个 C 中填 aa 个 A，一共 m−a−b+1m-a-b+1 个空，每个空可以不填，考虑插板法： 0，\sum^{n}{i=1} x_i =k">xi>0，∑i=1nxi=kx_i>0，\sum^{n}{i=1} x_i =k 的整数解有 (k−1n−1) \begin{pmatrix} k-1\n-1 \end{pmatrix} 组。 xi≥0，∑i=1nxi=kx_i\ge 0，\sum^{n}{i=1} x_i =k 的整数解有 (k+n−1n−1) \begin{pmatrix} k+n-1\n-1 \end{pmatrix} 组。 解释：将原式转化为 0，\sum^{n}{i=1} (x_i+1) =k+n">(xi+1)>0，∑i=1n(xi+1)=k+n (x_i+1) > 0，\sum^{n}_{i=1} (x_i+1) =k+n，再使用上面的结论即可。 所以对于 m−a−b+1m-a-b+1 个空填 aa 个，根据第二个结论，有 (m−bm−a−b) \begin{pmatrix} m-b\m-a-b \end{pmatrix} 种答案。 同理对于 B，有 (m−am−a−b) \begin{pmatrix} m-a\m-a-b \end{pmatrix} 种答案。 最后根据乘法原理，答案数为 (m−bm−a−b)⋅(m−am−a−b)\begin{pmatrix} m-b\m-a-b \end{pmatrix} \cdot \begin{pmatrix} m-a\m-a-b \end{pmatrix}。 对于组合数的计算，发现模数要大于 m,a,bm,a,b 且为质数，所以预处理阶乘与阶乘的逆元即可。 代码： #include using namespace std; #define int long long const int N=1e6+5; const int mod=998244353; int T; int m,a,b; int inv[N],ninv[N]; int mi(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; y>>=1,(x*=x)%=mod; } return res; } int c(int x,int y){ return inv[x]*ninv[y]%mod*ninv[x-y]%mod; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>T; inv[0]=ninv[0]=1; for(int i=1;i>m>>a>>b; cout `#include using namespace std; #define int long long const int N=1e6+5; const int mod=998244353; int T; int m,a,b; int inv[N],ninv[N]; int mi(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; y>>=1,(x*=x)%=mod; } return res; } int c(int x,int y){ return inv[x]*ninv[y]%mod*ninv[x-y]%mod; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>T; inv[0]=ninv[0]=1; for(int i=1;i inv[i]=(i*inv[i-1])%mod; ninv[i]=(mi(i,mod-2)*ninv[i-1])%mod; } while(T--){ cin>>m>>a>>b; coutc(m-a,m-a-b)*c(m-b,m-a-b)%mod"\n"; } return 0; }`
P6561 [SBCOI2020] 人
笔记