题目描述
太长了 不会描述。
接下来假定 (m) 和 (n) 同阶。
题解
我们设 (f_n) 表示恰好有 (n) 个人被碾压的方案数，显然 (f_k) 即为所求。
发现这个恰好不是很好限定 如果直接组合数选我们不太好强制规定哪些人不被碾压 于是我们考虑设 (g_n) 表示至少有 (n) 个人被碾压的方案数，一种计算方法就是枚举真实被碾压的方案数，然后选出来我们认为的被碾压的人是谁即可。二项式反演可以得到想要的答案。
[egin{aligned}
g_k = sum_{i=k}^N inom i k f_i\
Rightarrow f_k = sum_{i=k}^N (-1)^{N-i} inom i k g_i
end{aligned}
]
任务转化为求 (g)。
先列出朴素的式子：
[egin{aligned}
g_k = inom {N-1} {k} prod_{i=1}^M inom{N-k-1}{N-r_i-k}sum_{j=1}^{U_i} j^{N-r_i}(U_i-j)^{r_i-1}
end{aligned}
]
就是首先选出来被钦定碾压的那些人 然后考虑处理剩下的每一门课的情况 每课都会有 (N-r_i-k) 个剩下的比 B 神得分少的 所以需要从没有被钦定碾压的 (N-k-1) 个人中选出来。最后需要去枚举 B 神得了多少分 分别计算即可。
不妨发现后面的式子只和 (i) 有关 我们设其为 (h_i) 并进行化简：
[egin{aligned}
h_i &= sum_{j=1}^{U_i}j^{N-r_i}(U_i-j)^{r_i-1}\&= sum_{j=1}^{U_i}j^{N-r_i}sum_{k=0}^{r_i-1}U_i^{k}j^{r_i-1-k}(-1)^{r_i-1-k}\&= sum_{k=0}^{r_i-1}(-1)^{r_i-k-1}U_i^ksum_{j=1}^{U_i}j^{N-k-1}
end{aligned}
]
我们发现后面的式子是 (sum_{i=1}^n i^m) 的形式 可以用拉格朗日插值做到 (O(n))
于是我们去枚举计算所有的 (h) 时间复杂度是 (O(n^3))
接下来去枚举计算所有的 (g) 时间复杂度是 (O(n^2))
计算单个 (f) 就只需要 (O(n)) 了。所以总复杂度是 (O(n^3))。
#include<bits/stdc++.h>
#define fi first
#define se second
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int ha = 1e9 + 7;
const int MAXN = 1e5 + 5;
int fac[MAXN],inv[MAXN],n,m,k,U[MAXN];
inline int qpow(int a,int n=ha-2){
int res = 1;
while(n){
if(n & 1) res = 1ll*res*a%ha;
a = 1ll*a*a%ha;
n >>= 1;
}
return res;
}
inline void prework(){
fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
inv[MAXN-1] = qpow(fac[MAXN-1]);
ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}
int y[MAXN];
inline int cha(int n,int m){// [1..n]^m
int up = 1,ans = 0;
FOR(i,1,m+1) y[i] = (y[i-1]+qpow(i,m))%ha;
if(n <= m+1) return y[n];
FOR(i,0,m+1) up = 1ll*up*(n-i+ha)%ha;
FOR(i,0,m+1){
int t = 1ll*up*qpow((n-i+ha)%ha)%ha;
t = 1ll*t*inv[i]%ha*inv[m+1-i]%ha;
if((m+1-i)&1) t = (ha-t);
(ans += 1ll*t*y[i]%ha) %= ha;
}
return ans;
}
inline int C(int n,int m){
if(n < m) return 0;
if(m < 0) return 0;
return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}
int h[MAXN],r[MAXN],g[MAXN];
int main(){
prework();
scanf("%d%d%d",&n,&m,&k);
FOR(i,1,m) scanf("%d",U+i);
FOR(i,1,m) scanf("%d",r+i);
FOR(i,1,m){
// int chk = 0;
// FOR(j,1,U[i]){
// (chk += 1ll*qpow(j,n-r[i])*qpow(U[i]-j,r[i]-1)%ha) %= ha;
// }
FOR(k,0,r[i]-1){
int t = 1ll*C(r[i]-1,k)*qpow(U[i],k)%ha*cha(U[i],n-k-1)%ha;
if((r[i]-k-1)&1) t = ha-t;
(h[i] += t) %= ha;
}
// DEBUG(h[i]);DEBUG(chk);
// assert(h[i]==chk);
}
FOR(i,1,n){
g[i] = C(n-1,i);
FOR(j,1,m){
g[i] = 1ll*g[i]*h[j]%ha*C(n-i-1,n-i-r[j])%ha;
}
}
int ans = 0;
FOR(i,k,n){
int t = 1ll*C(i,k)*g[i]%ha;
if((i-k)&1) t = ha-t;
(ans += t) %= ha;
}
printf("%d
",ans);
return 0;
}