[HDOJ6143] Killer Names（dp，组合数学）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6143

题意：给m个字符，要求分配m个字符给许多二元组，每个二元组包含两个字符串，长度为n。要求两个字符串中不能出现相同的字符，问有多少种二元组。

考虑给二元组中第一个字符串i个字符，那么有C(m,i)种选法。希望把这i个字符都用上。那么就用dp来处理。

dp(i,j)表示字符串长为i，用j个字符凑成，有多少种凑法。考虑当前字符用完后下次还用或者不用，一共有j种选法，就是dp(i,j)=j*(dp(i-1,j)+dp(i-1,j-1))。记搜下就行，注意j>i的时候返回0。

右边的字符串就不用管，字符可以有不用上的，就是(m-i)^n种排列方式。

  1 /*
  2 ━━━━━┒ギリギリ♂ eye！
  3 ┓┏┓┏┓┃キリキリ♂ mind！
  4 ┛┗┛┗┛┃＼○／
  5 ┓┏┓┏┓┃ /
  6 ┛┗┛┗┛┃ノ)
  7 ┓┏┓┏┓┃
  8 ┛┗┛┗┛┃
  9 ┓┏┓┏┓┃
 10 ┛┗┛┗┛┃
 11 ┓┏┓┏┓┃
 12 ┛┗┛┗┛┃
 13 ┓┏┓┏┓┃
 14 ┃┃┃┃┃┃
 15 ┻┻┻┻┻┻
 16 */
 17 #include <bits/stdc++.h>
 18 using namespace std;
 19 #define fr first
 20 #define sc second
 21 #define cl clear
 22 #define BUG puts("here!!!")
 23 #define W(a) while(a--)
 24 #define pb(a) push_back(a)
 25 #define Rint(a) scanf("%d", &a)
 26 #define Rll(a) scanf("%I64d", &a)
 27 #define Rs(a) scanf("%s", a)
 28 #define Cin(a) cin >> a
 29 #define FRead() freopen("in", "r", stdin)
 30 #define FWrite() freopen("out", "w", stdout)
 31 #define Rep(i, len) for(int i = 0; i < (len); i++)
 32 #define For(i, a, len) for(int i = (a); i < (len); i++)
 33 #define Cls(a) memset((a), 0, sizeof(a))
 34 #define Clr(a, x) memset((a), (x), sizeof(a))
 35 #define Full(a) memset((a), 0x7f7f7f, sizeof(a))
 36 #define lrt rt << 1
 37 #define rrt rt << 1 | 1
 38 #define pi 3.14159265359
 39 #define RT return
 40 #define lowbit(x) x & (-x)
 41 #define onenum(x) __builtin_popcount(x)
 42 typedef long long LL;
 43 typedef long double LD;
 44 typedef unsigned long long ULL;
 45 typedef pair<int, int> pii;
 46 typedef pair<string, int> psi;
 47 typedef pair<LL, LL> pll;
 48 typedef map<string, int> msi;
 49 typedef vector<int> vi;
 50 typedef vector<LL> vl;
 51 typedef vector<vl> vvl;
 52 typedef vector<bool> vb;
 53 
 54 const LL mod =(LL) 1e9+7;
 55 const int maxn = 2100001;
 56 LL f[maxn], dp[2020][2020];
 57 int n, m;
 58 
 59 void init() {
 60     memset(dp, -1, sizeof(dp));
 61   f[0] = f[1] = 1;
 62   for(int i = 2; i < maxn; i++) f[i] = (f[i-1] * i) % mod;
 63 }
 64 LL mul(LL x, LL n) {
 65   LL ret = 1;
 66   while(n) {
 67     if(n & 1) ret = (ret * x) % mod;
 68     n >>= 1;
 69     x = (x * x) % mod;
 70   }
 71   return ret;
 72 }
 73 LL exgcd(LL a, LL b, LL &x, LL &y) {
 74   if(b == 0) {
 75     x = 1;
 76     y = 0;
 77     return a;
 78   }
 79   else {
 80     LL ret = exgcd(b, a%b, x, y);
 81     LL tmp = x;
 82     x = y;
 83     y = tmp - a / b * y;
 84     return ret;
 85   }
 86 }
 87 LL inv(LL a) {
 88   LL x, y;
 89   exgcd(a, mod, x, y);
 90   return (x % mod + mod) % mod;
 91 }
 92 LL C(LL x, LL y) {
 93   return f[x] * inv(f[x-y]) % mod * inv(f[y]) % mod;
 94 }
 95 
 96 LL DP(int n, int m) {
 97     if(m > n) return 0;
 98     if(dp[n][m] != -1) return dp[n][m];
 99     if(n == m) return dp[n][m] = f[n];
100     if(m == 1) return dp[n][m] = 1;
101     return dp[n][m] = m * (DP(n-1, m) + DP(n-1, m-1) % mod) % mod;
102 }
103 
104 signed main() {
105     // FRead();
106     int T;
107     Rint(T);
108     init();
109     W(T) {
110         Rint(n); Rint(m);
111         LL ret = 0;
112         For(i, 1, m) {
113             LL left = 0, right = 0;
114             ret += C(m, i) * DP(n, i) % mod * mul(m-i, n) % mod;
115             ret %= mod;
116         }
117         printf("%I64d
", ret);
118     }
119     RT 0;
120 }