【HDU6143】【多校】Killer Names

Zarxdy34 posted @ 2017年8月18日 10:28 in HDU with tags 计数 , 43 阅读

    记\({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;
}
Avatar_small
Zarxdy34 说:
2017年9月03日 19:40

排版奇丑...求大佬教教我怎么排版QWQ


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1