【LOJ】#2026. 「JLOI / SHOI2016」成绩比较

时间:2022-09-19 09:04:50

题解

用\(f[i][j]\)表示考虑了前i个排名有j个人被碾压

\(f[i][j] = f[i - 1][k] \* C[k][j] \* C[N - k - 1][N - r[i] - j] \* P[i]\)

P[i]是成绩排列的方式,意义是在前面k个人里选了j个来碾压,并将人数空缺用上一次没有碾压的来填补

\(P[i]\)怎么求,对于一个i,考虑枚举B君的成绩,也就是

\(\sum_{j = 1}^{u_{i}} j^{N - r[i]}(u_{i} - j)^{r[i] - 1}\)

观察一下把\(u_{i}\)当成一个变量,这是一个n次多项式,插值就能做了,暴力插值即可

复杂度\(O(n^3)\)

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#define pii pair<int,int>
#define fi first
#define se second
#define mo 974711
//#define ivorysi
using namespace std;
typedef long long int64;
const int MOD = 1000000007;
int N,M,K,r[105],u[105];
int64 f[105],P[105],inv[105];
int64 fpow(int64 x,int c) {
int64 res = 1,t = x;
while(c) {
if(c & 1) res = res * t % MOD;
t = t * t % MOD;
c >>= 1;
}
return res;
} void Solve() {
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]);
for(int T = 1 ; T <= M ; ++i) {
for(int i = 1 ; i <= r[T] ; ++i) {
f[i] = 0;
for(int j = 1 ; j < i ; ++j) {
f[i] += fpow(j,n - r[T] + 1) * fpow(i - j,r[T] - 1) % MOD;
f[i] %= MOD;
}
}
for(int i = 1 ; i <= r[T] ; ++i) {
for(int j = 1 ; j <= r[T] ; ++j) {
if(i == j) continue; }
}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}