题意简化
将1~n
划分到k
个圆排列中,就圆排列的方案数
算法一 ----stirling_1
思路
我们将它们划分两种情况,然后开始递推。
- n放到一个新的圆中
其方案数为:$$ [ _{k-1}^{n-1} ]$$
- n放已有的圆中
其方案数为:$$ (n-1)\times [_{k}^{n-1}] $$
代码
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1010;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qmi(ll m,ll k, ll p=mod){int res=1%p,t=m;while(k){if(k&1)res=res*t%p;t=t*t%p;k>>=1;}return res;}
ll inv(ll a){return qmi(a,mod-2);}
int n,m,f[N][N];
int main(){
cin>>n>>m;
f[0][0]=1; //s(0,0)=1 特殊情况
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=(f[i-1][j-1]+(ll)(i-1)*f[i-1][j])%mod;
cout<<f[n][m]<<endl;
return 0;
}
怎么用中括号表示$s(n, k)$呀。
矩阵