Passwords are widely used in our lives: for ATMs, online forum logins, mobile device unlock and door access. Everyone cares about password security. However, attackers always find ways to steal our passwords. Here is one possible situation:
Assume that Eve, the attacker, wants to steal a password from the victim Alice. Eve cleans up the keyboard beforehand. After Alice types the password and leaves, Eve collects the fingerprints on the keyboard. Now she knows which keys are used in the password.
However, Eve won't know how many times each key has been pressed or the order of the keystroke sequence.
To simplify the problem, let's assume that Eve finds Alice's fingerprints only occurs on Mkeys. And she knows, by another method, that Alice's password contains N characters. Furthermore, every keystroke on the keyboard
only generates a single, unique character. Also, Alice won't press other irrelevant keys like 'left', 'home', 'backspace' and etc.
Here's an example. Assume that Eve finds Alice's fingerprints on M=3 key '3', '7' and '5', and she knows that Alice's password is N=4-digit in length. So all the following passwords are possible: 3577, 3557, 7353 and 5735.
(And, in fact, there are 32 more possible passwords.)
However, these passwords are not possible:
1357 // There is no fingerprint on key '1'
3355 // There is fingerprint on key '7',
so '7' must occur at least once.
357 // Eve knows the password must be a 4-digit number.
With the information, please count that how many possible passwords satisfy the statements above. Since the result could be large, please output the answer modulo 1000000007(109+7).
Input
The first line of the input gives the number of test cases, T.
For the next T lines, each contains two space-separated numbers M and N, indicating a test case.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the total number of possible passwords modulo 1000000007(109+7).
Limits
Small dataset
T = 15.
1 ≤ M ≤ N ≤ 7.
Large dataset
T = 100.
1 ≤ M ≤ N ≤ 100.
Sample
排列组合：抽象n个数，填充到m个空格里，每个数至少出现一次，且可以出现无限次。
这道题可以用鸽巢原理（抽屉原理 n^m-c(n,1)*(n-1)^m+c(n,2)*(n-2)^m....c(n,n-1)*1^m ）
#include <iostream>
#include <vector>
using namespace std;
#define MOD 1000000007 //error as 10000000007, which is bigger than int and cause int-overflow to negative
typedef long long int ll;
// n<=m
//int a[n+1][m+1]=a[n][m]*(N-n)+a[n][m+1]*n
int dp(int N,int M){//N objects fill M lots
if(N==0||M==0) return 0;
vector<vector<ll> > a(N+1,vector<ll>(M+1,0));//@warning: int shoule be ll???
//for(int i=0;i<=M;i++) a[0][i]=1;//@error: should be below
a[0][0]=1;
for(int i=1;i<=N;i++){
for(int j=i;j<=M;j++){
//a[i][j]=((N-i+1)*a[i-1][j-1]%MOD+(i-1)*a[i][j-1]%MOD)%MOD; @error should be i*xx not i-1*xx
a[i][j]=((N-i+1)*a[i-1][j-1]%MOD+i*a[i][j-1]%MOD+MOD)%MOD;
//cout<<"a["<<i<<"]["<<j<<"]="<<a[i][j]<<endl;
}
}
return a[N][M];
}
int main(){
int n;cin>>n;
for(int i=0;i<n;i++){
int N,M;cin>>N>>M;
cout<<"Case #"<<i+1<<": "<<dp(N,M)<<endl;
}
return 0;
}