【HDU6143】【多校】Killer Names

    记\({f_i}\)表示使用i个不同字母（每个字母至少出现一次）的长度为n的名字有多少个。

    枚举左右两边各由多少种不同的字母组成，那么答案为\(\sum\limits_{i = 1}^{\min \{ m - 1,n\} } {\sum\limits_{j = 1}^{\min \{ m - i,n\} } {{f_i}C_n^i*{f_j}C_{n - i}^j} } \)

    容易发现如果我们能求出\({f_i}\)的话就能\(O(n^2)\)求解了。

    \(f_i\)用容斥也能很容易地做出来，\({f_k} = {m^k} - \sum\limits_{i = 1}^{k - 1} {C_k^i{f_i}} \)

    PS：刚开始本题并没有说要取模，刚开始看题面想了想高精度过不去，以至于我在三个半小时之后才发现题目的变动才做出来......拼命想优化的我重新看过一遍题面后只想说mmp。

#include <bits/stdc++.h>
using namespace std;
const int mo=1e9+7;
const int maxn=2010;

long long c[maxn][maxn];
int f[maxn];
int n,m;

int Pow(int x,int p)
{
	int res=1;
	while (p)
	{
		if (p&1) res=(long long)res*x%mo;
		p>>=1;
		x=(long long)x*x%mo;
	}
	return res;
}

void getf()
{
	f[1]=1;
	for (int i=2;i<=m-1;i++)
	{
		f[i]=Pow(i,n);
		for (int j=1;j<i;j++)
		{
			f[i]-=c[i][j]*f[j]%mo;
			if (f[i]<0) f[i]+=mo;
		}
	}
}

void Solve()
{
	int res=0;
	for (int i=1;i<=min(m-1,n);i++)
	{
		int temp=0;
		for (int j=1;j<=min(m-i,n);j++) temp=(temp+c[m-i][j]*f[j]%mo)%mo;
		temp=((long long)temp*f[i]%mo)*c[m][i]%mo;
		res=(res+temp)%mo;
	}
	printf("%d\n",res);
}

int main()
{
	c[0][0]=1;
	for (int i=1;i<=2000;i++)
	{
		c[i][0]=1;
		for (int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mo;
	}
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		getf();
		Solve();
	}
	return 0;
}