递推公式f(n)=(n-1)*(f(n-2)+f(n-1));
错排公式为 f(n) = n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!]
这是n个里面全那错的公式
这题还有可能n个里面拿错m个
所以先算出n个里面拿对的可能是c（n，n-m）；
即最后结果为c（n，n-m）*D(m)；
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #define ll long long using namespace std; ll c(ll n,ll m) { ll ans=1; for(ll i=n;i>=n-m+1;i--) { ans*=i; } for(ll i=1;i<=m;i++) ans/=i; return ans; } ll cc(ll n) { ll ans=1; for(ll i=2;i<=n;i++) ans*=i; return ans; } int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); int k=n-m; ll sum1=c(n,k); ll a=cc(m); ll sum=0; for(ll i=2;i<=n;i++) { if(i%2==0) { sum+=a/cc(i); } else sum-=a/cc(i); } printf("%lld\n",sum*sum1); } }