题目
搞题面太烦啦就不整了OAO
题解
首先考虑没有$k$的限制怎么做
发现二维可以分开搞，设${f_x}(i,n,R)$表示横坐标要跳$R$步跳到$n$上至少有$i$次坐标变化超过$M_x$的方案数，则有
${f_x}(i,n,R)=C_{R}^{i}C_{n-i(M_x+1)+R-1}^{R-1}$
后面那部分就是先确定$i$个$M_x+1$后随便选，即用$R-1$个板子把$n-i(M_x+1)$隔成$R$段
设$F_x(n,R)$表示跳$R$步到$n$没有一次坐标变化超过$M_x$的方案数，则有
$F_x(n,R)=\sum_{i=0}^{R}(-1)^if_x(i,n,R)$
似乎最后答案就是$F_x(T_x,R)\times F_y(T_y,R)$？
不对，题目中规定不能不走，所以$g(T_x,T_y,R)=F_x(T_x,R)\times F_y(T_y,R)$表示的是最多走$R$步的方案数
似乎还能容斥？设$G(T_x,T_y,R)$表示恰好走$R$步的方案数
$g(T_x,T_y,R)=\sum_{i=0}^{R}C_{R}^{i}G(T_x,T_y,i)$
二项式反演一下就成了$G(T_x,T_y,R)=\sum_{i=0}^{R}(-1)^{R-i}C_{R}^{i}g(T_x,T_y,i)$
$G(T_x,T_y,R)$就是答案了
现在有了限制，设$t_i$表示至少违反$i$条限制的答案，$h_i$表示恰好违反$i$条限制的答案，则有
$h_0=\sum_{i=0}^{K}(-1)^it_i$
设$s_{i,j}$表示违反$i$条限制，走$j$步的方案数
因为$k_i$都是$G$的倍数，所以直接全乘$\frac{1}{G}$
所以$t_i=\sum_{j}C_{R}^{i}s_{i,j}G(T_x-j,T_y-j,R-i)$
再求出$h_0$即可
复杂度最差是$O(R^2(\frac{T_x}{G})^2)$的？但是跑的飞快……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e3+5,N=2e6+5,mod=1e9+7;
int n,m,Mx,My,R,G,K,ans,Nw;
int fac[N],inv[N],Inv[N],k[MAX],f[MAX];
int ouo[105][105];
int C(int n,int m) {return (n<0||m<0||n<m)?0:1ll*fac[n]*Inv[m]%mod*Inv[n-m]%mod;}
int Calc(int n,int Mx,int R)
{
int ans=0;
for(int i=0,tt=1;i<=R&&n-i*(Mx+1)+R-1>=R-1;++i)
(ans+=(1ll*tt*C(R,i)*C(n-i*(Mx+1)+R-1,R-1)%mod+mod)%mod)%=mod,tt*=-1;
return ans;
}
int main()
{
scanf("%d%d%d%d%d%d%d",&n,&m,&Mx,&My,&R,&G,&K);
for(int i=1;i<=K;++i)
scanf("%d",&k[i]);
sort(k+1,k+1+K),K=unique(k+1,k+1+K)-k-1,Nw=min(n,m)/G,ouo[0][0]=1;
for(int i=0;i<=min(R,Nw);++i)
for(int j=1;j<=K;++j)
for(int l=0;l<=Nw;++l)
(ouo[i][l+k[j]/G]+=ouo[i-1][l])%=mod;
inv[0]=inv[1]=Inv[0]=Inv[1]=fac[0]=fac[1]=1;
for(int i=2,M=max(n+R,m+R);i<=M;++i)
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod,Inv[i]=1ll*Inv[i-1]*inv[i]%mod,fac[i]=1ll*fac[i-1]*i%mod;
for(int i=0;i<=min(R,Nw);++i)
for(int j=0,x,Ans;j<=Nw;++j)
if(ouo[i][j])
{
x=1ll*C(R,i)*ouo[i][j]%mod,Ans=0;
for(int l=0,tt=1;l<=R-i;++l)
(Ans+=1ll*tt*C(R-i,R-i-l)*Calc(n-j*G,Mx,R-i-l)%mod*Calc(m-j*G,My,R-i-l)%mod)%=mod,tt*=-1;
(f[i]+=1ll*Ans*x%mod)%=mod;
}
for(int i=0,tt=1,M=min(R,Nw);i<=M;++i)
(ans+=(1ll*tt*f[i]%mod+mod)%mod)%=mod,tt*=-1;
return printf("%d",ans),0;
}
