模拟赛考过的题
当时太菜了现在也一样只拿到了$ 30$分
回来填个坑
题意
你要从$ (0,0)$走到$ (T_x,T_y)$，每次移动的坐标增量满足$ 0 \leq \Delta x \leq M_x，0 \leq \Delta y \leq M_y$
不允许原地不动，且存在$ k$个坐标增量$ (k_i,k_i)$不能移动
求恰好$ R$步走到终点的方案数，对$ 1e9+7$取模
数据范围有$ T_x,T_y \leq 10^6，k \leq 50，R \leq 1000 $
保证所有$ k_i$均为$ G$的倍数且$ 10000 \leq G \leq 50000$
$ Solution$
先考虑没有$ k$的限制怎么做
容易发现坐标两维是很独立的
尝试把它们分开来做
用$ calc(x,y,z)$表示走$ z$步，每步走的距离$ \in [0,y]$，走到$ x$的方案数
直接$ DP$复杂度过大，尝试用容斥优化这个东西
设$ g(i)$表示至少有$i$步超出限制的情况
我们找出$ i$步让他们均移动$ y+1$的距离，然后剩下的没有限制，用插板法计算
即
$ g(i)=\binom{z}{i}·\binom{x-(y+1)*i+z-1}{z-1}$
然后根据套路容斥得
$ calc(x,y,z)=\sum\limits_{i=0}^{limit} (-1)^ig(i)$
（貌似这里可以看成二项式反演中$ \binom{n}{0}=1$的特殊情况）
这样单次计算的复杂度是$ O(R)$的
容易发现这两维并不完全独立
因为两维不允许均原地不动的情况出现
即这样算出来的$ calc(T_x,M_x,R)*calc(T_y,M_y,R)$其实是走了至多$ R$步的方案数
按照套路二项式反演
设$ g(i)$表示走了至多$ i$步的方案数，$ f(i)$表示恰好走了$ i$步的方案数
由
$ g(R)=calc(T_x,M_x,R)*calc(T_y,M_y,R)=\sum\limits_{i=0}^R\binom{R}{i}f(i)$
反演得
$ f(R)=\sum\limits_{i=0}^n (-1)^{n-i}\binom{R}{i}g(i)$
这样就解决了没有$ k$的情况
时间复杂度$ O(R^2)$
然后再考虑有$ k$条限制的情况(每条限制可以多次违反，注意去重！)
依旧考虑容斥
设$ g(i)$表示至少违反了$ i$条限制的方案数,$ f(i)$表示恰好违反了$ i$条限制的方案数
显然我们需要计算的是$ f(0)=\sum\limits_{i=0}^{limit} (-1)^i g(i)$
现在问题是$ g(i)$如何计算
我们设$ F(x,y)$表示违反了$ x$条限制，这些限制的$ k_i$之和为$ y*G$的方案数
显然$ DP$的第二维不超过$ \frac{10^6}{10^4}=100$，因此可以非常轻易的计算出$ DP$的结果
然后发现$ limit$也并不大，直接利用$ F$数组计算$ g$数组的值并计算即可
理论复杂度可能高达$ 1000*1000*100*100$
但由于内层可以记忆化，复杂度能去掉一个$ 1000$
再加上数据极度不满，这个算法跑的飞快
就解决了这道题
$ my \ code$
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define p 1000000007
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x=;char zf=;char ch=getchar();
while(ch!='-'&&!isdigit(ch))ch=getchar();
if(ch=='-')zf=-,ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();return x*zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt,Tx,Ty,Mx,My,R,G;
int a[],g[];
int jc[],njc[],inv[];
int C(int x,int y){return 1ll*jc[x]*njc[y]%p*njc[x-y]%p;}
int calc(int x,int y,int bs){//每步不超过y，走的距离为x，走了bs步
if(y*bs<x)return ;int ans=;
for(rt i=,fla=;i<=bs&&(y+)*i<=x;i++,fla*=-)
(ans+=1ll*fla*C(bs,i)*C(x-(y+)*i+bs-,bs-)%p)%=p;
return ans;
}
int anss[][],ans2[][];
int solve(int x,int R){
int ans=;
for(rt i=R,fla=;i>=;i--,fla*=-){
int v;
if(anss[x/G][i])v=anss[x/G][i];else v=1ll*calc(Tx-x,Mx,i)*calc(Ty-x,My,i)%p;
anss[x/G][i]=v;
(ans+=1ll*v*C(R,i)*fla%p)%=p;
}
return (ans+p)%p;
}
int F[][];//F[i][j]走i步走出i*G的方案数
int main(){
jc[]=jc[]=njc[]=njc[]=inv[]=inv[]=;
Tx=read(),Ty=read(),Mx=read(),My=read();
R=read();G=read();k=read();
for(rt i=;i<=max(Tx,Ty)+R;i++){
jc[i]=1ll*jc[i-]*i%p;
inv[i]=1ll*inv[p%i]*(p-p/i)%p;
njc[i]=1ll*njc[i-]*inv[i]%p;
}
if(!k)return write(solve(,R)),;
for(rt i=;i<=k;i++)a[i]=read();
sort(a+,a+k+);k=unique(a+,a+k+)-a-; F[][]=;
g[]+=solve(,R);
for(rt i=;i*G<=min(Tx,Ty);i++)
for(rt j=;j*G<=min(Tx,Ty);j++){
for(rt d=;d<=k;d++)if(a[d]<=min(Tx,Ty)&&a[d]<=j*G)
(F[i][j]+=F[i-][j-a[d]/G])%=p;
(g[i]+=1ll*solve(j*G,R-i)*F[i][j]%p)%=p;
}
ll ret=;
for(rt i=,fla=;i*G<=min(Tx,Ty);i++,fla*=-)(ret+=1ll*fla*g[i]*C(R,i)%p)%=p;
cout<<(ret+p)%p;
return ;
}