2017-多校-8-1011
[ans = sum_{k=1}^{min{n,m}}C_m^k\,f_n(k) imes\,(m-k)^n
]
[f_n(k) = k^n - sum_{i=1}^{k-1}C_k^i\,f_n(i)
]
其中(f_n(k))表示在姓中选择使用k中字符的总共的数量
限制姓使用k个字符，名不能使用这k个字符。答案就是枚举所有的k。
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <math.h>
#include <bitset>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-9;
const int N = 2500 + 5;
const int mod = 1e9 + 7;
LL inv[N];
LL c[N][N];
LL F[N];
LL quick_exp(LL a, int n, int mod)
{
LL ans = 1;
while(n)
{
if(n & 1 ) ans = (ans*a)%mod;
a = (a*a)%mod;
n >>= 1;
}
return ans;
}
void init()
{
for(int i = 1; i < N; i++)
inv[i] = quick_exp(i, mod-2, mod);
memset(c, 0, sizeof(c));
for(int i = 0; i < N; i++)
c[i][0] = 1;
for(int i = 1; i <= 2000; i++)
{
for(int j = 1; j <= i; j++)
c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod;
}
}
LL getf(int n, int k, int mod)
{
LL ans = quick_exp(k, n, mod);
for(int i = 1; i <= k-1; i++)
{
ans = (ans - (c[k][i]*F[i])%mod + mod)%mod;
}
return F[k] = ans;
}
int t,n,m;
int main()
{
init();
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n,&m);
int up = min(n,m);
LL ans = 0;
F[1] = 1;
for(int k = 1; k <= up; k++)
{
ans = ans + ((getf(n, k, mod) * c[m][k] )%mod) * quick_exp(m-k, n, mod) % mod;
ans = ans % mod;
}
printf("%lld
", ans);
}
return 0;
}