jzoj5664.【GDOI2018Day1模拟4.17】凫趋雀跃dp

Description

Input

Output

Sample Input

2 2 1 1 3 0

Sample Output

6

Data Constraint

Hint

分析&＃xff1a;
显然可以考虑容斥。
我们最终的答案为走不少于00次不合法向量-不少于1" role="presentation" >1$1$次不合法向量&＃43;不少于22次不合法向量……
设f[i][x][y]" role="presentation" >f[i][x][y]$f[i][x][y]$表示走ii步任意向量，到达(x,y)" role="presentation" >(x,y)$(x,y)$的方案。
g[i][x]g[i][x]为只走不合法向量&＃xff0c;到达(10x,10x)(10x,10x)的方案。
那么设s(k)s(k)为走不少于kk次不合法向量的方案。就等于先走到一个点(a,b)" role="presentation" >(a,b)$(a,b)$&＃xff0c;然后只走不合法向量到终点。由于不合法向量是可以不一定要最后走&＃xff0c;所以要乘一个组合数。因为不合法向量的起点一定是(Tx−10i,Ty−10i)(Tx−10i,Ty−10i)。注意&＃xff0c;(0,0)(0,0)也是一种不合法向量。
我们枚举ii，方案数即为

代码&＃xff1a;

#include
#include
#include const int maxn&＃61;807;
const int mod&＃61;10007;using namespace std;int f1[maxn<<1][maxn],f2[maxn<<1][maxn],g[maxn<<1][maxn];
int sum[maxn<<1][maxn],jc[maxn<<1];
int n,m,r,x,y,q;
int a[58];int power(int x,int y)
{if (y&＃61;&＃61;1) return x;int c&＃61;power(x,y/2);c&＃61;(c*c)%mod;if (y%2) c&＃61;(c*x)%mod;return c;
} int c(int n,int m)
{return jc[n]*power(jc[n-m]*jc[m]%mod,mod-2)%mod;
}int main()
{freopen("jump.in","r",stdin);freopen("jump.out","w",stdout);scanf("%d%d%d%d%d%d",&n,&m,&x,&y,&r,&q);for (int i&＃61;1;i<&＃61;q;i&＃43;&＃43;){scanf("%d",&a[i]);a[i]/&＃61;10;}f1[0][0]&＃61;f2[0][0]&＃61;g[0][0]&＃61;1;for (int i&＃61;0;i<&＃61;max(n,m);i&＃43;&＃43;) sum[0][i]&＃61;1;jc[0]&＃61;1;for (int i&＃61;1;i<&＃61;r;i&＃43;&＃43;) jc[i]&＃61;(jc[i-1]*i)%mod;for (int i&＃61;1;i<&＃61;r;i&＃43;&＃43;){for (int j&＃61;0;j<&＃61;n;j&＃43;&＃43;){if (j<&＃61;x) f1[i][j]&＃61;(f1[i][j]&＃43;sum[i-1][j])%mod;else f1[i][j]&＃61;(f1[i][j]&＃43;sum[i-1][j]-sum[i-1][j-x-1]&＃43;mod)%mod;sum[i][j]&＃61;(sum[i][j-1]&＃43;f1[i][j])%mod;}}for (int i&＃61;1;i<&＃61;r;i&＃43;&＃43;){for (int j&＃61;0;j<&＃61;m;j&＃43;&＃43;){if (j<&＃61;y) f2[i][j]&＃61;(f2[i][j]&＃43;sum[i-1][j])%mod;else f2[i][j]&＃61;(f2[i][j]&＃43;sum[i-1][j]-sum[i-1][j-y-1]&＃43;mod)%mod;sum[i][j]&＃61;(sum[i][j-1]&＃43;f2[i][j])%mod;}}g[0][0]&＃61;1;for (int i&＃61;1;i<&＃61;r;i&＃43;&＃43;){for (int j&＃61;0;j<&＃61;min(n/10,m/10);j&＃43;&＃43;){g[i][j]&＃61;g[i-1][j];for (int k&＃61;1;k<&＃61;q;k&＃43;&＃43;){if (j-a[k]>&＃61;0) g[i][j]&＃61;(g[i][j]&＃43;g[i-1][j-a[k]])%mod;}}} int ans&＃61;0,k&＃61;-1; for (int i&＃61;0;i<&＃61;r;i&＃43;&＃43;){k&＃61;-k;for (int j&＃61;0;j<&＃61;min(n/10,m/10);j&＃43;&＃43;){ans&＃61;(ans&＃43;k*g[i][j]*f1[r-i][n-10*j]%mod*f2[r-i][m-10*j]%mod*c(r,i)%mod&＃43;mod)%mod;}}printf("%d",ans);
}