【题解】JLOI2016 - 成绩比较
是我会的题，所以感觉难度不如 noip T3T4。
设 \(f_{i,j}\) 表示考虑到前 \(i\) 门课，有 \(j\) 人被 B 碾压。
转移，设这轮中有 \(k\) 个原本被碾压的人不再被碾压，则相当于从 \(f_{i-1,j+k}\) 转移到 \(f_{i,j}\)。考虑转移系数，首先是 \(j+k\) 人中选 \(k\) 人，现在排名在 B 前面的位置还有 \(r_i-1-k\) 位，所以从 \(n-1-j-k\) 中选 \(r_i-1-k\) 个。最后是每个人有一个分数，易得要乘上 \(\sum_{j=1}^{u_i}j^{n-r_i}(u_i-j)^{r_i-1}\)。所以转移方程为：
\[f_{i,j} = \sum_{k=0}^{\min(n-j-1,r_i-1)}f_{i-1,j+k}\dbinom{j+k}k\dbinom{n-1-j-k}{r_i-1-k}T_i
\]
其中：
\[T_i = \sum_{j=1}^{u_i}j^{n-r_i}(u_i-j)^{r_i-1}
\]
边界是 \(f_{0,n-1}=1\)，答案取 \(f_{m,k}\)。
容易发现瓶颈在于 \(T_i\) 的计算，看到这个式子我们想到了 CF622F，于是直接拉格朗日插值就能求出来了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110;
const ll P = 1e9 + 7;
int n, m, k, u[N], r[N];
ll f[N][N], y[N*2], t[N], C[N][N];
ll qp(ll x, ll y){
ll ans = 1;
while(y){
if(y & 1){
ans = ans * x % P;
}
x = x * x % P;
y >>= 1;
}
return ans;
}
ll lglr(int xk){
ll res = 0;
for(int i = 1; i <= n + n; ++ i){
ll mul = y[i];
for(int j = 1; j <= n + n; ++ j){
if(j != i){
mul = mul * (xk - j + P) % P * qp(i-j+P, P-2) % P;
}
}
res = (res + mul) % P;
}
return res;
}
int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m; ++ i){
scanf("%d", &u[i]);
}
for(int i = 1; i <= m; ++ i){
scanf("%d", &r[i]);
}
C[0][0] = 1;
for(int i = 1; i <= n; ++ i){
C[i][0] = C[i][i] = 1;
for(int j = 1; j < i; ++ j){
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % P;
}
}
f[0][n-1] = 1;
for(int i = 1; i <= m; ++ i){
for(int j = 1; j <= n + n; ++ j){
y[j] = (y[j-1] + qp(j, n-r[i]) * qp(u[i]-j, r[i]-1)) % P;
}
t[i] = lglr(u[i]);
for(int j = 0; j <= n-1; ++ j){
for(int k = 0; k <= min(n-j-1, r[i]-1); ++ k){
f[i][j] = (f[i][j] + f[i-1][j+k] * C[j+k][k] % P * C[n-1-j-k][r[i]-1-k] % P * t[i] % P) % P;
}
}
}
printf("%lld\n", f[m][k]);
return 0;
}