『JLOI2016』成绩比较

『JLOI2016』成绩比较 [* easy]

给定 (N) 个变量，每个变量有 (M) 个属性，属性 (i) 的值在 ([1,U_i]) 中随机。

第 (1) 个变量的所有属性的排名以及给出，然后我们知道恰好有 (K) 个变量满足所有属性都严格小于等于 (1)

求所有可能的合法情况。答案对 (10^9+7) 取模。

(N,Mle 100,U_ile 10^9)

Solution

方便起见，令 (Nleftarrow N-1)，同时令 (R_jleftarrow N+1-R_j) 表示有 (R_j) 名同学分数小于等于他。

容斥，设 (g_i) 表示至少有 (i) 个变量严格小于等于他。

那么我们可以直接使用 Dp 来计算 (g_i)，那么基础方案数为 (inom{N}{i})，假设属性 (j) 的取值为 (x)，那么这 (i) 个变量的取值范围均为 (x)，那么对于每个属性对答案的贡献均可以独立乘起来，具体来说形如此：

[egin{aligned} &inom{N-i}{R_j-i}sum_{x=1}^{U_j}x^{R_j}(U_j-x)^{N-R_j} end{aligned}]

设 (o=R_j)，不难得到：

[egin{aligned} &inom{N-i}{o-i}sum_{x=1}^{U_j}x^{o}(U_j-x)^{N-o} \&Rightarrow inom{N-i}{o-i}sum_{x=1}^{U_j}x^{o}sum_j inom{N-o}{j}(-1)^j x^jU_j^{N-o-j} \&Rightarrow inom{N-i}{o-i}sum_j inom{N-o}{j}(-1)^j U_j^{N-o-j}sum_{x=1}^{U_j}x^{o+j} end{aligned}]

设 (f(k,x)=sum_{i=1}^x i^k)

那么不难得到维度 (i) 对答案的贡献为：

[egin{aligned} &inom{N-i}{o-i}sum_j inom{N-o}{j}(-1)^j U_j^{N-o-j}f(o+j,U_j) end{aligned}]

显然 (o+j) 的取值范围为 (1sim N)，同时不难发现后面的式子与枚举的 (i) 无关，所以可以考虑预处理后式，对于 (j=1,2...M) 均预处理后式称为 (t_j)，那么枚举 (i) 之后就可以 (mathcal O(NM)) 的计算答案了。

我们的瓶颈在于希望得到正整数幂多项式，此时有两种选择：

拉格朗日插值。
伯努利数。

由于我想要复习伯努利数，所以这里又重新进行了推导：

设 (S_k(n)=sum_{j=1}^n j^k)

[egin{aligned} &sum_{k=0} S_k(n)frac{x^k}{k!} \&Rightarrowsum_{k=0}sum_{j=1}^n frac{j^kx^k}{k!} \&Rightarrowsum_{j=1}^n e^{jx} \&Rightarrowfrac{e^{(n+1)x}-e^x}{e^x-1} \&Rightarrowfrac{xe^x}{e^x-1} imes frac{e^{nx}-1}{x} end{aligned}]

我们设前者的 EGF 序列为 ({B_0,B_1...B_k})，后者为 ({frac{n}{1},frac{n^2}{2}...frac{n^{i+1}}{i+1}})

于是有 (S_k(n)) 即为：

[egin{aligned} &sum_{i+j=k}B_iinom{k}{i}frac{n^{k-i+1}}{k-i+1} \&Rightarrow frac{1}{k+1}sum_{i+j=k}B_iinom{k+1}{i}n^{k-i+1} end{aligned}]

计算 (B_i)，然后直接得到多项式。

接下来，注意到：

[frac{xe^x}{e^x-1} imes frac{e^x-1}{x}=e^x ]

所以有 ({B_0,B_1...B_k}) 与 ({frac{1}{1},frac{1}{2}...frac{1}{i+1}}) 的二项卷积结果为 ({1,1,1...1})

不难注意到 (B_0=1)，所以我们有：

[B_k=1-sum_{i<k}inom{k}{i}B_ifrac{1}{k-i+1} ]

[B_k=1-frac{1}{k+1}sum_{i<k}inom{k+1}{i}B_i ]

复杂度为 (mathcal O(N^2M))

(Code:)

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 100 + 5 ; 
const int P = 1e9 + 7 ;  
int fpow(int x, int k) {
	int ans = 1, base = x ;
	while(k) {
		if(k & 1) ans = 1ll * ans * base % P ;
		base = 1ll * base * base % P, k >>= 1 ;
	} return ans ;
}
int n, m, lim, K, U[N], R[N], g[N], h[N], B[N] ;
int f[N], iv[N], fac[N], inv[N], C[N][N], A[N][N] ; 
int Get(int x, int k) {
	int ans = 0, d = 1 ;
	for(re int i = 0; i <= k + 1; ++ i)
		ans = (ans + d * A[k][i]) % P, d = d * x % P ;
	return ans ; 
}
signed main()
{
	n = gi() - 1, m = gi(), K = gi() ; lim = n + 5 ; 
	rep( i, 1, m ) U[i] = gi() ; 
	rep( i, 1, m ) R[i] = gi(), R[i] = n - R[i] + 1 ; 
	fac[0] = inv[0] = C[0][0] = 1 ; 
	rep( i, 1, lim ) rep( j, 0, lim ) 
	C[i][j] = (!j) ? 1 : (C[i - 1][j - 1] + C[i - 1][j]) % P ; 
	rep( i, 1, lim ) 
		fac[i] = fac[i - 1] * i % P, inv[i] = fpow(fac[i], P - 2), 
		iv[i] = fpow( i, P - 2 ) ; 
	B[0] = 1 ; 
	rep( i, 1, n ) {
		int d = 0 ;
		rep( j, 0, i - 1 ) d = (d + C[i + 1][j] * B[j]) % P ; 
		d = d * iv[i + 1] % P, B[i] = (1 - d + P) % P ; 
	}
	rep( k, 0, n ) rep( i, 0, k ) 
		A[k][k - i + 1] = C[k + 1][i] * B[i] % P * iv[k + 1] % P ;
	rep( i, 1, m ) {
		int o = R[i], ans = 0 ; f[0] = 1 ; 
		rep( j, 1, n ) f[j] = f[j - 1] * U[i] % P ; 
		for(re int j = 0; j <= n - o; ++ j) {
			if(j & 1) ans = (ans - C[n - o][j] * f[n - o - j] % P * Get(U[i], o + j) % P + P) % P ; 
			else ans = (ans + C[n - o][j] * f[n - o - j] % P * Get(U[i], o + j) % P ) % P ;
		} h[i] = ans ; 
	}
	rep( i, 1, n ) {
		int ans = C[n][i] ; 
		rep( j, 1, m ) 
			if( R[j] < i ) ans = 0 ;
			else ans = ans * C[n - i][R[j] - i] % P * h[j] % P ; 
		g[i] = ans ; 
	}
	int Ans = 0 ; 
	rep( i, K, n ) {
		if((i - K) & 1) Ans = (Ans - g[i] * C[i][K] % P + P) % P ; 
		else Ans = (Ans + g[i] * C[i][K] % P + P) % P ; 
	}
	cout << Ans << endl ; 
	return 0 ;
}