?contest=0&problem=441
441. Set Division
Time limit per test: 0.25 second(s)Memory limit: 262144 kilobytes
input: standardoutput: standard
Ruslan hasKfriends. And all of them have birthday tomorrow. He has boughtNdifferent photo albums yesterday, and wants to present these photo albums to his friends. Of course, he can’t give less than 1 photo album to anybody. Your task is to calculate how many possible ways is there to do it.All photo albums are different. Two distributions are considered the same if they differ only by order of albums in the gifts or by the persons receiving gifts.
Input
In the only line of the input there are two numbers separated by a space —.
Output
Output should contain one number — the number of possible ways to distribute the albums modulo 2007.
Example(s)
sample inputsample output
3 2 3
题意：将n件不同礼物分给k个人，每个人至少一件，问有多少种分发。
思路：f[i][j]表示把前i件礼物分给j个人的种类数f[i][j]=f[i-1][j]*j+f[i-1][j-1]
但是此题的n特别大，而k最大只有10，一般的dp肯定会超时/空间,但是可以用矩阵加速。
这里所有的f[i]为一个状态，，行向量为[ f[1][0], f[1][1], f[1][2]…f[1][k] ] ,构造矩阵k+1行k+1列
1 1 0 0 0……0
0 1 1 0 0……0
0 0 2 1 0……0
0 0 0 3 1……0
最后的结果就是第二行第k列。
/** * @author neko01 *///#pragma comment(linker, "/STACK:102400000,102400000")#include <bits/stdc++.h>using namespace std;typedef long long LL;#define min3(a,b,c) min(a,min(b,c))#define max3(a,b,c) max(a,max(b,c))#define pb push_back#define mp(a,b) make_pair(a,b)#define clr(a) memset(a,0,sizeof a)#define clr1(a) memset(a,-1,sizeof a)#define dbg(a) printf("%d\n",a)typedef pair<int,int> pp;const double eps=1e-9;const double pi=acos(-1.0);const int INF=0x3f3f3f3f;const LL inf=(((LL)1)<<61)+5;const int N=11;const int mod=2007;struct Matrix{int a[N][N];int sz;Matrix(int x,int n){sz=n;for(int i=0;i<N;i++)for(int j=0;j<N;j++)a[i][j]=(i==j)?x:0;}Matrix operator*(Matrix &b){Matrix tmp(0,sz);for(int i=0;i<sz;i++)for(int j=0;j<sz;j++)for(int k=0;k<sz;k++)tmp.a[i][j]+=a[i][k]*b.a[k][j],tmp.a[i][j]%=mod;return tmp;}Matrix operator^(int k){Matrix cur=*this,res(1,sz);while(k){if(k&1) res=res*cur;cur=cur*cur;k>>=1;}return res;}};//f[i][j]=f[i-1][j]*j+f[i-1][j-1]int main(){int n,k;scanf("%d%d",&n,&k);Matrix t=Matrix(0,k+1);t.a[0][0]=1;for(int i=1;i<=k;i++)t.a[i-1][i]=1,t.a[i][i]=i;t=t^(n-1);printf("%d\n",t.a[1][k]);return 0;}
找寻隐藏在山间的纯净和那“鸟鸣山更幽”的飞鸟。
