【HDU6143】【多校】Killer Names
记fi表示使用i个不同字母(每个字母至少出现一次)的长度为n的名字有多少个。
枚举左右两边各由多少种不同的字母组成,那么答案为∑i=1min
容易发现如果我们能求出{f_i}的话就能O(n^2)求解了。
f_i用容斥也能很容易地做出来,{f_k} = {m^k} - \sum\limits_{i = 1}^{k - 1} {C_k^i{f_i}}
PS:刚开始本题并没有说要取模,刚开始看题面想了想高精度过不去,以至于我在三个半小时之后才发现题目的变动才做出来......拼命想优化的我重新看过一遍题面后只想说mmp。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #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; } |
2017年9月03日 19:40
排版奇丑...求大佬教教我怎么排版QWQ