2024年第二个周一，不值得纪念一下吗。
错排板子题
对于每个\(n\),\(m\)都有
\(ans=\dbinom nm\times f_{n-m}\)，\(f_i\) 是错排数列第 \(i\) 个方案数
因为多组数据，所以每次询问都求一遍显然是超时的，直接预处理出 \(n\) 以内所有的数组，然后直接 \(\text O(1)\) 求出答案
不会分析复杂度，别 D 了 QAQ
比较有趣的是此题如果不用快读会 T，只能拿 60。
\(n\) 最大 5000000（
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
const int N=1e7;
int t,n,m,f[N],inv[N],js[N];
inline int read()
{
int s = 0,w = 1;char ch = getchar();
while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}
while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}
return s*w;
}
inline int qpow(int a,int b)
{
int ans=1,k=a;
while(b>0)
{
if(b&1) ans=(ans*k)%p;
k=(k*k)%p;
b>>=1;
}
return ans;
}
inline int C(int n,int m)
{
return(((js[n]*inv[m])%p)*inv[n-m])%p;
}
signed main()
{
js[0]=1;
n=1000000;
for(register int i=1;i<=n;++i)
js[i]=js[i-1]*i%p;
inv[n]=qpow(js[n],p-2);
inv[0]=1;
for(register int i=n-1;i>=1;--i)
inv[i]=(inv[i+1]*(i+1))%p;
f[0]=1,f[1]=0,f[2]=1;
for(register int i=3;i<=n;++i)
f[i]=((i-1)*((f[i-1]+f[i-2])%p))%p;
t=read();
while(t--)
{
n=read(),m=read();
cout<<(C(n,m)*f[n-m]%p)<<"\n";
}
}
托帕 ++
闲话内容日渐单调。
诶，K8 是不是发现了 WC 讲题人是学长啊，好强。
诶 LuoTianyi_Official 怎么似了？
想要一个图源，原原不断的那种。