1
7
2018
0

斯特林数

TCO2014_Wildcard_750

g[i]表示n行i列的答案然后直接容斥即可。

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;
const int MO=1e9+7;
int n,m,c;
LL S[4010][4010],f[4010],g[4010];
class CountTables{
	public:
	int howMany(int N, int M, int C){
		n=N,m=M,c=C;
		S[0][0]=1;
		FOR(i,1,m){
			S[i][0]=0;
			FOR(j,1,i) S[i][j]=(S[i-1][j-1]+S[i-1][j]*j)%MO;
		}
		LL x=1;
		FOR(i,1,m){
			x=x*c%MO;
			f[i]=1;
			FORD(j,x,x-n+1) f[i]=f[i]*j%MO;
			g[i]=f[i];
			FOR(j,1,i-1) (g[i]-=S[i][j]*g[j]%MO)%=MO;
		}
		(g[m]+=MO)%=MO;
		return (int)g[m];
	}
}cwy;
Category: 板子 | Tags: | Read Count: 50

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com