组合+错排
代码:
#include<iostream> #include<cstring> #include<cstdio> #include<string> #include<set> #include<map> #include<cmath> #include<algorithm> #include<vector> #include<cmath> #include<queue> #include<stack> //#define ull unsigned long long #define ll long long using namespace std; const int INF=0x3f3f3f3f; const int MOD=1000000007; const ll LMOD=1000000007; const double eps=1e-6; const int N=1050; ll f[N]; ll c[N][N]; class CarelessSecretary { public: int howMany(int n,int k) { f[1]=0;f[2]=1; for(int i=3;i<N;++i) f[i]=((i-1)*(f[i-1]+f[i-2]))%LMOD; memset(c,0,sizeof(c)); for(int i=0;i<N;++i) for(int j=0;j<=i;++j) { if(i==j||j==0) c[i][j]=1; else c[i][j]=(c[i-1][j]+c[i-1][j-1])%LMOD; } ll sum=0; int w=n-k; for(int i=0;i<=w;++i) { sum=(sum+c[w][i]*f[n-i])%LMOD; //cout<<c[w][i]<<" "<<f[n-i]<<endl; //cout<<sum<<endl; } return (int)sum; } };