【LOJ6374】[SDWC2018 Day1]网格
题面
题解
先考虑一下没有限制而且可以同时不走的，那么显然行列是独立的。
设( ext{f}(R,T,M))表示某一维走出步数(R)，走(T)格，每步不超过(M)，令生成函数( ext{F}(x)=1+x+x^2+cdots +x^M=frac {1-x^{M+1}}{1-x})，那么我们想求的就是([x^T] ext{F}(x)^R)。
其中
(
egin{aligned}
ext{[}x^T ext{]} ext{F}(x)^R
&=[x^T](frac {1-x^{M+1}}{1-x})^R\
&=[x^T](1-x^{M+1})^R(1+x+x^2+cdots)^R\
&=[x^T](1-x^{M+1})^Rsum_{i=0}^{infty}{i+R-1choose R-1}x^i\
&=sum_{i=0}^{lfloorfrac {T}{M+1}
floor}(-1)^i{Rchoose i}{R-1+T-i(M+1)choose R-1}
end{aligned}
)
然后再考虑可以有((0,0))限制的：
可以发现( ext f(R,T_x,M_x) imes ext f(R,T_y,M_y))没有考虑((0,0))，那也就是至多走了(R)步的方案数，而非恰好。
设( ext g(R,T_x,T_y,M_x,M_y))表示恰好(R)步，然后里面参数自己看的答案，二项式反演得：
( ext g(R,T_x,T_y,M_x,M_y)=sum_{i=0}^R (-1)^{R-i}{Rchoose i} ext f(i,T_x,M_x) imes ext f(i,T_y,M_y))
现在再考虑有那(K)条限制的：
可以背包出( ext h(i,j))表示从(K)中选了(i)步走，走了(j imes G)格的方案数，那么放到总步数(R)中，方案数就有({R choose i} ext h(i,j))种。
最后就可以求出答案了：
考虑容斥，首先枚举至少踩了(i)条限制，再枚举限制走了(j imes G)步，那么答案为(不妨令(T_x<T_y))
计算的复杂度为(O(R^2lfloor frac TG floor))，可以通过。
代码
#include <bits/stdc++.h>
using namespace std;
int gi() {
int res = 0, w = 1;
char ch = getchar();
while (ch != '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar();
return res * w;
}
const int Mod = 1e9 + 7;
int fpow(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = 1ll * res * x % Mod;
x = 1ll * x * x % Mod;
y >>= 1;
}
return res;
}
const int MAX_N = 1.2e6 + 5;
int N = 1.2e6, Tx, Ty, Mx, My;
int R, G, K, a[55];
int fac[MAX_N], ifc[MAX_N];
int C(int n, int m) {
if (n < m || n < 0 || m < 0) return 0;
else return 1ll * fac[n] * ifc[m] % Mod * ifc[n - m] % Mod;
}
int f(int R, int T, int M) {
int n = T / (M + 1), res = 0;
for (int i = 0; i <= n; i++) {
int now = 1ll * C(R - 1 + T - i * (M + 1), R - 1) * C(R, i) % Mod;
if (i & 1) res = (res - now + Mod) % Mod;
else res = (res + now) % Mod;
}
return res;
}
int g(int R, int Tx, int Ty, int Mx, int My) {
int res = 0;
for (int i = 0; i <= R; i++) {
int now = 1ll * C(R, i) * f(i, Tx, Mx) % Mod * f(i, Ty, My) % Mod;
if ((R - i) & 1) res = (res - now + Mod) % Mod;
else res = (res + now) % Mod;
}
return res;
}
int h[1005][1005];
int main () {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
for (int i = fac[0] = 1; i <= N; i++) fac[i] = 1ll * fac[i - 1] * i % Mod;
ifc[N] = fpow(fac[N], Mod - 2);
for (int i = N - 1; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % Mod;
Tx = gi(), Ty = gi(), Mx = gi(), My = gi();
R = gi(), G = gi(), K = gi();
for (int i = 1; i <= K; i++) a[i] = gi() / G;
sort(&a[1], &a[K + 1]); K = unique(&a[1], &a[K + 1]) - a - 1;
h[0][0] = 1;
int mx = max(Tx, Ty) / G;
for (int i = 1; i <= min(mx, R); i++)
for (int j = 1; j <= K; j++)
for (int k = a[j]; k <= mx; k++) h[i][k] = (h[i][k] + h[i - 1][k - a[j]]) % Mod;
int ans = 0;
for (int i = 0; i <= R; i++) {
int res = 0;
for (int j = 0; j <= mx; j++)
res = (res + 1ll * h[i][j] * g(R - i, Tx - j * G, Ty - j * G, Mx, My)) % Mod;
res = 1ll * res * C(R, i) % Mod;
if (i & 1) ans = (ans - res + Mod) % Mod;
else ans = (ans + res) % Mod;
}
printf("%d
", ans);
return 0;
}