题目当中有三条限制，我们来逐一考虑。对于第一条限制，每次走动的增加量 (x_i le M_x, y_i le M_y)，可以发现一共走的步数是确定的，那么就相当于解这样两个方程组：
其中 (x_i le M_x, y_i le M_y)，其实是两个独立的方程，最终解的数量实际上是上下两个方程解的数量相乘的结果，于是我们已第一个方程的解为例来思考。可以发现直接计算解的数量是不好算的，但钦定一些位置超过限制其他位置随意的方案是很好算的，于是我们可以令 (f_i) 表示钦定有 (i) 个位置不合法其他位置随意的方案，令 (g_i) 表示恰好有 (i) 个位置不合法的方案，那么有：
根据二项式反演：
再来考虑第二个条件，不能出现任意一个位置使得 (x_i = 0, y_i = 0)，同样我们发现还是可以使用二项式定理，令 (f_i) 表示钦定有 (i) 个位置 (x_i = 0, y_i = 0)，其他位置随意且满足第一条限制的方案，(g_i) 为恰好的方案，那么有：
根据二项式反演可得：
再来考虑第三条限制，同样可以使用二项式反演，只不过这里钦定的方案可能不是那么好算了。但是我们能发现钦定第三类不合法后这个位置将会被占用，那么我们可以一次考虑每条限制，那么一个 (dp) 就可以统计出这些方案，令 (dp_{i, j, k}) 表示当前考虑完前 (i) 种限制，当前已经钦定了 (j) 个位置，当前钦定位置上的增量之和为 (k) 的方案，那么同样我们枚举当前新哪增那些位置非法，有（令 (a_i = k_i)）：
但是这个 (dp) 的复杂度很高，因为第三维涉及到枚举走过的步数之和，但题目当中给了一个条件，所有限制的步数都是 (G) 的倍数，那么实际上我们只需要存储 (k = frac{k}{G}) 即可，于是就可以将上面哪个 (dp) 的状态改写一下，转移基本没有变。可以发现这个 (dp) 第一维枚举的复杂度为 (K)（下面称其为 (n)），第二维的复杂度为 (min{R, frac{min{T_x, T_y}}{G}})，第三维的枚举上限为 (frac{min{T_x, T_y}}{G}) 转移的复杂度也最多为 (frac{min{T_x, T_y}}{G}) 因此这个 (dp) 的复杂度是 (O(nmin{R, frac{min{T_x, T_y}}{G}}(frac{min{T_x, T_y}}{G}) ^ 2) le 50 imes 100 ^ 3 = 5 imes 10 ^ 7)。
但是需要注意的是，我们最后二项式反演的时候，不能直接做两维的二项式反演，因为我们并不能保证那些恰好选择了 (j) 个位置非法的情况下有 (i) 个位置的增量之和为 (k)。因此，我们需要将所有钦定 (i) 个位置非法的方案相加再进行容斥。令 (F_i) 为钦定有 (i) 个位置非法的方案，那么有：
其中 (g_{i, j}) 表示走 (i) 步，已经使用了 (j imes G) 步的满足前两条限制的方案。再令 (f_{i, j}) 表示走 (i) 步，已经使用了 (j imes G) 步的满足第一条限制的方案，则：
可以发现有用的 (f_{i, j}) 只有 (R imes frac{min{T_x, T_y}}{G}) 个，每次计算需要 (R) 次，因此计算出所有可用的 (f) 总共的复杂度为 (O(R ^ 2 imes frac{min{T_x, T_y}}{G})) 还能承受。而可用的 (g) 也只有 (R imes frac{min{T_x, T_y}}{G}) 个，预处理出 (f) 后复杂度也可以做到 (O(R ^ 2 imes frac{min{T_x, T_y}}{G}))。最后总复杂度 (O(R ^ 2 imes frac{min{T_x, T_y}}{G} + n imes (frac{min{T_x, T_y}}{G}) ^ 3)) 可以通过本题。
一些坑点
-
每次二项式反演一定要认真推式子，不然容易出错
-
(f_0, g_0) 的情况需要特判
-
组合数的取值范围到 (2 imes 10 ^ 6)
-
注意枚举 (dp) 时第二维和第三维的上限不同
#include<bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = l; i <= r; ++i)
const int N = 1000000 + 5;
const int M = 100 + 5;
const int K = 1000 + 5;
const int Mod = 1000000000 + 7;
int n, R, G, L1, L2, tx, ty, Tx, Ty, Mx, My, ans;
int a[M], k[M], F[M], fac[N * 2], inv[N * 2], f[K][M], g[K][M], dp[M][M][M];
int read(){
char c; int x = 0, f = 1;
c = getchar();
while(c > '9' || c < '0'){ if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int Inc(int a, int b){
return (a += b) >= Mod ? a - Mod : a;
}
int Dec(int a, int b){
return (a -= b) < 0 ? a + Mod : a;
}
int Mul(int a, int b){
return 1ll * a * b % Mod;
}
int Qpow(int a, int b){
int ans = 1;
while(b){
if(b & 1) ans = Mul(ans, a);
a = Mul(a, a), b >>= 1;
}
return ans;
}
int C(int n, int m){
if(n < m) return 0;
return Mul(fac[n], Mul(inv[m], inv[n - m]));
}
int main(){
tx = read(), ty = read(), Mx = read(), My = read(), R = read(), G = read();
fac[0] = inv[0] = 1;
rep(i, 1, max(tx, ty) + R) fac[i] = Mul(fac[i - 1], i), inv[i] = Qpow(fac[i], Mod - 2);
n = read();
rep(i, 1, n) a[i] = read();
sort(a + 1, a + n + 1);
n = unique(a + 1, a + n + 1) - a - 1;
L2 = min(tx, ty) / G, L1 = min(R, L2);
if(tx == ty && (tx % G == 0)) f[0][tx / G] = 1;
rep(i, 1, R) rep(j, 0, L2){
int S1 = 0, S2 = 0; Tx = tx - j * G, Ty = ty - j * G; if(Tx < 0 || Ty < 0) continue;
rep(k, 0, i){
if(k & 1) S1 = Dec(S1, Mul(C(i, k), C(Tx - (Mx + 1) * k + i - 1, i - 1)));
else S1 = Inc(S1, Mul(C(i, k), C(Tx - (Mx + 1) * k + i - 1, i - 1)));
if(k & 1) S2 = Dec(S2, Mul(C(i, k), C(Ty - (My + 1) * k + i - 1, i - 1)));
else S2 = Inc(S2, Mul(C(i, k), C(Ty - (My + 1) * k + i - 1, i - 1)));
}
f[i][j] = Mul(S1, S2);
}
if(tx == ty && (tx % G == 0)) g[0][tx / G] = 1;
rep(i, 1, R) rep(j, 0, L2){
rep(k, 0, i){
if(k & 1) g[i][j] = Dec(g[i][j], Mul(C(i, k), f[i - k][j]));
else g[i][j] = Inc(g[i][j], Mul(C(i, k), f[i - k][j]));
}
}
dp[0][0][0] = 1;
rep(i, 1, n) rep(j, 0, L1) rep(k, j, L2) rep(l, 0, min(j, k * G / a[i])){
dp[i][j][k] = Inc(dp[i][j][k], Mul(C(R - j + l, l), dp[i - 1][j - l][k - l * (a[i] / G)]));
}
rep(i, 0, L1) rep(j, i, L2) F[i] = Inc(F[i], Mul(dp[n][i][j], g[R - i][j]));
rep(i, 0, L1) ans = ((i & 1) ? Dec(ans, F[i]) : Inc(ans, F[i]));
printf("%d", ans);
return 0;
}