Killer Names（HDU 6143）

Killer Names（HDU 6143）

【传送门】

//题意：给克隆人取名字，每个人有名和姓（the first name and the last name），且名和姓里不能有重复的字，名和姓都有n个字，每个字只能在m种里面取。问最多可以取几个名字。

//思路：

推出的公式：

answer=C(1,m)*f(1)*(m-1)^n + C(2,m)*f(2)*(m-2)^n + C(3,m)*f(3)*(m-3)^n +......+C(x,m)*f(x)*(m-x)^n.

如果m<=n，x=m-1；如果m>n，x=n 。

f(x)表示n个长度的名字里，放且必须放x个字。

例：

— — —     放2个字（假设是1、2）

情况有：112、121、211、122、212、221 。（6种）

如果理解了f(x)的意思，那就来算f(x)的值：

易得：f(1)=1 。

那么f(2)怎么算？每个位置是不是只能在2种颜色里选，那么每个位置都有2种选择，就是2^n，但这里面包括了只有1种颜色的情况，所以要减掉C(1,2)*f(1)，因为有2中颜色，2^n里包含了只有每种颜色的情况，所以要乘C(1,2)，所以f(2)=2^n-C(1,2)*f(1) 。

同理：f(3)=3^n - ( C(1,3)*f(1)+C(2,3)*f(2) ) 。

=> f(x) = x^n - ( C(1,x)*f(1)+C(2,x)*f(2)+...+C(x-1,x)*f(x-1) ) 。

C(x,m)*f(x)*(m-x)^n ： answer里的这个通项解释：

C(x,m)表示从m个可选的字里面选x个，“名”里只能用也必须用到这x个，"名"里共有C(x,m)*f(x)种情况。那么“姓”里只能用(m-x)个字，可以用这些字中的一部分，也可以全部用到，因为这不可能跟“名”里重复，所以每个位置都有(m-x)种情况，所以共有(m-x)^n种情况。那么总的情况就是两者的乘积。

所以，把“名”中可用的字从1个遍历到x个即可。

PS：组合数C(x,y)是先打表预处理的，利用杨辉三角打表。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;typedef long long ll;
const int MOD = 1e9 + 7;
const int MAX = 2000 + 100;ll f[3000];
ll map[MAX][MAX];//快速幂
ll fastm(ll a, ll b)
{ll ans = 1;while (b){if (b & 1){ans = ((ans%MOD)*(a%MOD)) % MOD;}b /= 2;a = ((a%MOD)*(a%MOD)) % MOD;}return ans;
}int main()
{int T;scanf("%d", &T);//预处理组合数C，打表for (int i = 0; i < MAX; i++){map[i][0] = 1;map[0][i] = 1;}for (int i = 1; i < MAX; i++){for (int j = 1; j < MAX; j++){map[i][j] = (map[i - 1][j] + map[i][j - 1]) % MOD;}}while (T--){ll n, m;scanf("%lld%lld", &n, &m);ll sum = 0;ll x = 1, y, z;//“名”里最多可用的字ll tt = min(n, m);if (tt == m)tt = m - 1;//算f(x)f[1] = 1;for (ll i = 2; i <= tt; i++){f[i] = fastm(i, n);ll ans = 0;for (ll j = 1; j < i; j++){ans = (ans + map[i - j][j] * f[j]) % MOD;}f[i] = (f[i] - ans + MOD) % MOD;}//“名”里可用的字从 1 遍历到 ttfor (ll i = 1; i <= tt; i++){x = f[i] % MOD;y = map[m - i][i] % MOD;z = fastm(m - i, n);sum = (sum + ((x*y) % MOD)*z%MOD) % MOD;}printf("%lldn", sum%MOD);}return 0;
}