[LOJ 6374]「SDWC2018 Day1」网格

Posted on | In , | Views:

题目链接

LOJ 6374

做法

先考虑$k=0$的部分分。
发现$x,y$这两维有一定的独立性，先分开考虑。
我们以$calc(x,y,z)$表示跳$z$步，每步不超过$y$格，总共跳了$x$格的方案数，直接dp复杂度为$O(10^6)$不能接受，考虑容斥。
先以$g_i$表示至少有i步超过了$y$格的方案数。
我们从$z$步中选择$i$步先跳$y+1$格，剩下的话插板法解决。

用$f_i$表示恰好有$i$步超过了$y$格的方案数，二项式反演即可。
$calc(x,y,z)$所求答案即为$f_0$

但是两维并不完全独立，因为题目规定了不能两维上同时在一步上跳$0$格。
$g_i$表示至多走了$i$步的方案(两维上都跳0格不算一步)。
$g_i=calc(tx,mx,z)*calc(ty,my,z)$
$f_i$表示恰好走了$i$步的方案。
再次二项式反演

这样我们就解决了$k=0$的部分分
再考虑有k的限制。
温馨提示：先把k去重
$g_i$表示至少有$i$步违反限制的方案数
先$dp$出$f_{i,j}$表示$i$步违反限制，总格数为$G*j$的方案数，$j$最大只有100，可以轻松dp出。
那么计算$g_i$的时候，先枚举这$i$步总共跳了多少格，剩下的步数可以转化成一个$k=0$的问题。
有了$g$后，剩下的反演就和第一步一模一样了。
复杂度为$O(1000*1000*100*100)$，发现前面calc需要计算的值不多，记忆化后可以去掉一个1000，就解决了此题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (1000005)
using namespace std;
int tx,ty,mx,my,R,G,size,k,x,ans,d;
int fac[N],inv[N],A[N],f[105][105],gx[105][1005],gy[105][1005],q[N];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
const int P=1000000007;
inline int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
inline int C(int a,int b){
    if (a<0||b<0||b>a) return 0;
    return 1ll*fac[a]*inv[b]%P*inv[a-b]%P; 
}
inline int calcx(int x,int y,int z){
    if (gx[(tx-x)/G][z]>=0) return gx[(tx-x)/G][z];
    int ret=0,d=1;
    for (int i=0;i<=z;i++){
        ret=Inc(ret,1ll*C(z,i)*C(x-(y+1)*i+z-1,z-1)%P*d);
        ret=Inc(ret,P);
        d=-d;
    }
    gx[(tx-x)/G][z]=ret;
    return ret;
}
inline int calcy(int x,int y,int z){
    if (gy[(ty-x)/G][z]>=0) return gy[(ty-x)/G][z];
    int ret=0,d=1;
    for (int i=0;i<=z;i++){
        ret=Inc(ret,1ll*C(z,i)*C(x-(y+1)*i+z-1,z-1)%P*d);
        ret=Inc(ret,P);
        d=-d;
    }
    gy[(ty-x)/G][z]=ret;
    return ret;
}
inline void init(){
    size=1e6;
    fac[0]=1;
    for (int i=1;i<=size;i++) fac[i]=1ll*fac[i-1]*i%P;
    A[0]=A[1]=1;
    for (int i=2;i<=size;i++) A[i]=Inc(1ll*-P/i*A[P%i]%P,P);
    inv[0]=1;
    for (int i=1;i<=size;i++) inv[i]=1ll*inv[i-1]*A[i]%P;
}
inline int get(int tx,int ty,int mx,int my,int R){
    if (tx<0||ty<0) return 0;
    int d=1,ans=0;
    for (int i=R;i>=0;i--){
        ans=Inc(ans,1ll*C(R,i)*calcx(tx,mx,i)%P*calcy(ty,my,i)%P*d);
        ans=Inc(ans,P);
        d=-d;
    }
    return ans;
} 
int main(){
    read(tx),read(ty),read(mx),read(my);
    read(R),read(G);
    init();
    read(k);
    for (int i=1;i<=k;i++){
        read(x);
        q[i]=x/G;
    }
    sort(q+1,q+k+1);
    k=unique(q+1,q+k+1)-q-1;
    f[0][0]=1;
    for (int i=1;i<=100;i++){
        for (int j=0;j<=100;j++){
            for (int t=1;t<=k;t++){
                if (q[t]<=j) f[i][j]=Inc(f[i][j],f[i-1][j-q[t]]);
            }
        }
    }
    ans=0;
    d=1;
    memset(gx,-1,sizeof(gx));
    memset(gy,-1,sizeof(gy));
    for (int i=0;i<=min(R,100);i++){
        int tt=0;
        for (int j=0;j<=100;j++) tt=Inc(tt,1ll*f[i][j]*get(tx-j*G,ty-j*G,mx,my,R-i)%P);
        ans=Inc(ans,1ll*tt*C(R,i)%P*d);
        ans=Inc(ans,P);
        d=-d;
    }
    printf("%d",ans);
    return 0;
}