题目
多组询问长度为 \(n\) 的排列中恰好有 \(m\) 个数对号入座的排列数
分析
首先 \(n\) 个数中选择 \(m\) 个数放入那 \(m\) 个位置显然是 \(C(n,m)\)
剩下就是错排 \(D(n)=(n-1)(D(n-1)+D(n-2))\), 也很好理解
预处理阶乘逆元错排,\(O(1)\) 求解
代码
- #include <cstdio>
- #include <cctype>
- #define rr register
- using namespace std;
- const int mod=1000000007;
- const int N=1000000;
- int d[N+1],fac[N+1],inv[N+1];
- inline signed iut(){
- rr int ans=0; rr char c=getchar();
- while (!isdigit(c)) c=getchar();
- while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
- return ans;
- }
- inline void print(int ans){
- if (ans>9) print(ans/10);
- putchar(ans%10+48);
- }
- signed main(){
- fac[0]=fac[1]=inv[0]=inv[1]=1,d[0]=1,d[1]=0;
- for (rr int i=2;i<=N;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod,d[i]=1ll*(i-1)*(d[i-2]+d[i-1])%mod;
- for (rr int i=2;i<=N;++i) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*inv[i-1]*inv[i]%mod;
- for (rr int T=iut(),Cnm;T;--T){
- rr int n=iut(),m=iut();
- Cnm=1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
- print(1ll*Cnm*d[n-m]%mod),putchar(10);
- }
- return 0;
- }
- # 错排, 组合计数 #洛谷 4071 [SDOI2016] 排列计数
来源: http://www.bubuko.com/infodetail-3433901.html