【SDWC2018 Day1】网格

反演。

这题真的有意思。用了三次容斥就出来了,真好玩。

一看这道题,发现有好多限制,比如上界限制,比如非法限制,感觉就很麻烦。

那我们一个个弄过来。

先考虑上界限制。

考虑容斥。

发现$x$与$y$是独立的,那就先考虑$x$。

$f[i]$表示至少有$i$步超过上界限制的方案数。转移就很容易了,$f[i]=C(R,i)\ast C(Tx-i\ast (Mx+1)+R-1,R-1)$。其中就是考虑至少选出$i$步,然后这$i$步都至少为$Mx+1$,那么隔板一下就可以了。

那么$x$的答案就出来了,就是$\sum_{i=0}^{R} (-1)^i \ast f[i]$。

然而虽然$x$与$y$看似独立,但因为不能原地踏步,所以直接相乘是错的。

所以再次考虑容斥。

设$g[i]$表示至多有$i$步超过上界限制的方案数,$dp[i]$表示恰好有$i$步超过上界限制的方案数。

那么$g[i]$有两种转移。

一方面,$g[i]=ansx\ast ansy$,即$x$与$y$的乘积。

另一方面,$g[i]=\sum_{i=0}^R C(R,i)\ast dp[i]$。

而另一条式子显然可以二项式反演,于是$dp[i]=\sum_{i=0}^R (-1)^{R-i}\ast C(R,i)\ast g[i]$。

于是上界限制就处理好了。

考虑非法限制。

这里就不阐述非法限制了,两者其实差不多的,写出式子后你会惊讶地发现还是可以二项式反演,于是就做完了。

稍微提示一下,所有的非法情况都被$G$整除哦,而且可能有非法情况重复哦。

至于复杂度呢,是$O(R^2\ast (\frac {min(Tx,Ty)}{G})^2)$。

说白了,根本就是玄学,只是出题人没有卡而已。

code:

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
107
108
109
110
111
112
113
//2019.2.3 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
res s=0;
bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return w?-s:s;
}
inline void _swap(res &x,res &y){
x^=y^=x^=y;
}
inline int _abs(const res &x){
return x>0?x:-x;
}
inline int _max(const res &x,const res &y){
return x>y?x:y;
}
inline int _min(const res &x,const res &y){
return x<y?x:y;
}
const int N=1e6+1e3+10;
const int kcz=1e9+7;
const int K=50+10;
namespace MAIN{
int Tx,Ty,Mx,My,R,G,k;
int fac[N],inv[N];
inline int qpow(res x,res y){
res ret=1;
while(y){
if(y&1)ret=1LL*x*ret%kcz;
x=1LL*x*x%kcz,y>>=1;
}
return ret;
}
inline void pre(){
res Lim=_max(Tx,Ty)+R-1;
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(res i=2;i<=Lim;i++)fac[i]=1LL*fac[i-1]*i%kcz;
inv[Lim]=qpow(fac[Lim],kcz-2);
for(res i=Lim;i>=1;i--)inv[i-1]=1LL*inv[i]*i%kcz;
}
inline int C(const res &x,const res &y){
if(x<0||y<0||x<y)return 0;
return 1LL*fac[x]*inv[y]%kcz*inv[x-y]%kcz;
}
inline void add(res &x,const res &y){
x+=y,x>=kcz?x-=kcz:1,x<0?x+=kcz:1;
}
inline int Add(const res &x,const res &y){
return x+y>=kcz?x+y-kcz:(x+y<0?x+y+kcz:x+y);
}
namespace subtask0{
int f[N],g[N],dp[N];
inline void MAIN(){
for(res i=0;i<=R;i++)
for(res j=0;j<=i;j++)add(f[i],1LL*(j&1?-1:1)*C(i,j)*C(Tx-j*(Mx+1)+i-1,i-1)%kcz);
for(res i=0;i<=R;i++)
for(res j=0;j<=i;j++)add(g[i],1LL*(j&1?-1:1)*C(i,j)*C(Ty-j*(My+1)+i-1,i-1)%kcz);
for(res i=0;i<=R;i++)
for(res j=0;j<=i;j++)add(dp[i],1LL*(j&1?-1:1)*C(i,j)*f[i-j]%kcz*g[i-j]%kcz);
printf("%d\n",dp[R]);
}
}
namespace subtask1{
int d[K],lim;
int f[1000+10][100+10],g[1000+10][100+10],ans;
inline int F(const res &r,const res &mx,const res &tx){
res ret=0,lim=_min(r,tx/(mx+1));
for(res i=0;i<=lim;i++)add(ret,1LL*(i&1?-1:1)*C(r,i)*C(tx-(mx+1)*i+r-1,r-1)%kcz);
return ret;
}
inline int DP(const res &r,const res &lim){
res ret=0;
for(res i=0;i<=r;i++)add(ret,1LL*((r-i)&1?-1:1)*C(r,i)*f[i][lim]%kcz);
return ret;
}
inline void MAIN(){
for(res i=1;i<=k;i++)d[i]=read()/G;
sort(d+1,d+k+1);
k=unique(d+1,d+k+1)-d-1;
lim=_min(Tx,Ty)/G;
for(res i=0;i<=R;i++)
for(res j=0;j<=lim;j++)f[i][j]=1LL*F(i,Mx,Tx-G*j)*F(i,My,Ty-G*j)%kcz;
g[0][0]=1;
for(res i=1;i<=R;i++)
for(res j=0;j<=lim;j++)
for(res h=1;h<=k;h++)
if(j-d[h]>=0)add(g[i][j],g[i-1][j-d[h]]);
for(res i=0;i<=R;i++){
res ret=0;
for(res j=i;j<=lim;j++)add(ret,1LL*g[i][j]*DP(R-i,j)%kcz);
add(ans,1LL*(i&1?-1:1)*C(R,i)*ret%kcz);
}
printf("%d\n",ans);
}
}
inline void MAIN(){
Tx=read(),Ty=read(),Mx=read(),My=read(),R=read(),G=read(),k=read(),pre();
if(k==0)subtask0::MAIN();
else subtask1::MAIN();
}
}
int main(){
MAIN::MAIN();
return 0;
}

成功跑了loj的rnk2,开心!