就是把p个东西分成k个非空的部分，顺序不同的比如1234和4321视为一种。让你求出答案mod 2007
总所周知这是传说中的第二类Stirling数，它的公式是S(p,k)=S(p-1,k-1)+k*S(p-1,k)
那么似乎好像就可以直接上了，但是p的范围是1到10亿，k的范围是10以下。。
怎么办捏，我一开始想起来这个函数有一个公式，Wiki上有，但是我发现这个公式要除一个数的囧，就没办法mod了。。
我想啊想啊。。最后发现由于k比较小，直接矩阵乘法来计算就可以了额。。
是O(logp*k^3)。。
矩阵乘法是解决这类递推问题的良方啊！
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
const int mod=2007;
const int maxn=11;
typedef int data[maxn][maxn];
int p,c;
struct mat
{
data o;
mat(){memset(o,0,sizeof(o));}
int& operator() (int i,int j)
{return o[i][j];}
int operator() (int i,int j) const
{return o[i][j];}
void operator=(const mat&x)
{memmove(o,x.o,sizeof(o));}
void print()
{
rep(i,c)
{
rep(j,c)
cout<<o[i][j]<<" ";
cout<<endl;
}
}
}o;
mat operator*(const mat&a,const mat&b)
{
mat r;
rep(i,c) rep(j,c) rep(k,c)
r(i,j)+=a(i,k)*b(k,j),r(i,j)%=mod;
return r;
}
mat power(int p)
{
if(p==1) return o;
mat tmp=power(p/2);
tmp=tmp*tmp;
if(p&1) tmp=tmp*o;
return tmp;
}
int main()
{
//freopen("in","r",stdin);
cin>>p>>c;c++;
rep(i,c) o(i,i)=i;
for(int i=1;i<c;i++) o(i,i-1)=1;
mat now=power(p);
//now.print();
int ans=0;
cout<<now(c-1,0)<<endl;
}
本高亮代码使用codeHl生成，