Description：

$n$ 位同学 $m$ 门课。第 $i$ 门课的分数区间为 $[1,U_i]$ ，已知第一个人每一科的排名，有 $k$ 个人每科成绩都小于第一个人，求每个人得分的方案数。

$1\leqslant n\leqslant 100$

Solution：

看数据范围像一个 $O(n^3)$ 的 $DP$ ，不难想到设 $f[i][j]$ 表示前 $i$ 科有 $j$ 个人每科成绩都小于第一个人，先列转移方程： $$ f[i][j]=\sum_{k=j}^{n-1}f[i-1][k]\times C_k^j\times C_{n-1-k}^{r[i]-1-(k-j)}\sum_{c=1}^{u[i]}(u[i] - c)^{r[i]-1}c^{n-r[i]} $$ 这样是 $O(n^2m\max(u))$ 的，显然无法通过。

最后那个 $\sum$ 可以对每一个 $i$ 单独只计算一次，但是 $u[i]$ 最大为 $10^9$ ，发现最后面那个是一个关于 $u[i]$ 的 $n$ 次多项式，因为我们可以把它看成 $u[i]$ 个多项式的和，每个多项式的次数都不超过 $n-1$ ，所以他们的和是 $n$ 次的。而单点的值比较容易计算，于是可以用拉格朗日插值法 $O(n^2)$ 获得单点的值。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll n,m,k;

#define MAXN 110

ll u[MAXN],r[MAXN];

#define MOD 1000000007

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

ll f[MAXN][MAXN];

ll fac[MAXN],inv[MAXN];

ll C(ll n,ll m)

{

	if(n < m || n < 0 || m < 0)return 0;

	return fac[n] * inv[m] % MOD * inv[n - m] % MOD;

}

ll x[MAXN],y[MAXN];

ll calc(ll n,ll u,ll r)

{

	ll ans = 0;

	for(ll i = 1;i <= n + 1;++i)

	{

		x[i] = i;y[i] = 0;

		for(ll c = 1;c <= i;++c)

		{

			y[i] = (y[i] + power(i - c,r - 1) * power(c,n - r) % MOD) % MOD;

		}

	}

	for(ll i = 1;i <= n + 1;++i)

	{

		ll res = y[i];

		for(ll j = 1;j <= n + 1;++j)

		{

			if(i == j)continue;

			res = res * (u - x[j] + MOD) % MOD;

			res = res * power((x[i] - x[j] + MOD) % MOD,MOD - 2) % MOD;

		}

		ans = (ans + res) % MOD;

	}

	return ans;

}

int main()

{

	scanf("%lld%lld%lld",&n,&m,&k);

	fac[0] = 1;

	for(ll i = 1;i <= n;++i)fac[i] = fac[i - 1] * i % MOD;

	inv[n] = power(fac[n],MOD - 2);

	for(ll i = n - 1;i >= 0;--i)inv[i] = inv[i + 1] * (i + 1) % MOD;

	for(ll i = 1;i <= m;++i)scanf("%lld",&u[i]);

	for(ll i = 1;i <= m;++i)scanf("%lld",&r[i]);

	f[0][n - 1] = 1;

	for(ll i = 1;i <= m;++i)

	{

		ll res = calc(n,u[i],r[i]);

		for(ll j = k;j <= n - 1;++j)

		{

			for(ll l = j;l <= n - 1;++l)

			{

				f[i][j] = (f[i][j] + f[i - 1][l] * C(l,j) % MOD * C(n - 1 - l,r[i] - 1 - (l - j)) % MOD * res % MOD) % MOD;

			}

		}

	}

	cout << f[m][k] << endl;

	return 0;

}