hdu6143[思维,排列组合]

发表于 | 分类于 ， ， | 阅读数 次

链接:hdu6143[思维,排列组合]

题解

  • 一开始想的方程是
  • 之后发现会有重复
  • dp[i]表示m种字母中选i个出来放在姓上的情况(全部用完)
  • 显然
  • 最后答案就是
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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rint register int
#define rep(i,x,y) for(rint i=x;i<=y;++i)
#define repd(i,x,y) for(rint i=x;i>=y;--i)
#define ll long long
using namespace std;
const ll p=1e9+7;
const int N=2000+7;
ll a[N],b[N][N],c[N],dp[N],n,m,T;
inline void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){x=1;y=0;return ;}
	exgcd(b,a%b,x,y);
	ll t=x;x=y;y=t-a/b*y;
}
inline ll inv(ll d){ll x,y;exgcd(d,p,x,y);return x>0?x:x+p;}
inline void init(){
	a[0]=1;
	rep(i,1,N-7)a[i]=i*a[i-1]%p,c[i]=inv(a[i]);
	rep(i,1,N-7)b[i][1]=i;
	rep(i,1,N-7)rep(j,2,N-7)b[i][j]=b[i][j-1]*i%p;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>T;
	init();
		while(T--){
		ll ans=0;
		cin>>n>>m;
		rep(i,1,m){dp[i]=b[i][n];rep(j,1,i-1)dp[i]=(dp[i]-a[i]*c[i-j]%p*c[j]%p*dp[j]%p+p)%p;}
		rep(i,1,m)ans=(ans+a[m]*c[m-i]%p*c[i]%p*dp[i]%p*b[m-i][n])%p;
		cout<<ans<<endl;
	}
}