#P3096. 跳棋

    ID: 2214 传统题 1000ms 512MiB 尝试: 6 已通过: 6 难度: 7 上传者: 标签>CF2300提高+/省选-容斥原理计数 DP前缀和优化 DP状态维度消除Pascal 递推滚动数组

跳棋

题目描述

一个无限大的边长为 11 的网格地图上一开始有一个跳棋在 (0,0)(0,0),要跳到 (tx,ty)(tx,ty)。每次在 xx 方向的位移量为 [0,mx][0,mx],每次在y方向的位移量为 [0,my][0,my],每次必须移动,不能留在原位置上。现在想知道通过 rr 次跳到目标的方案数。限制条件是:给定 nn 个数字 bib_i,要求每次跳的向量不能为 (bi,bi)(b_i,b_i)。

输入格式

第一行六个整数 tx,ty,mx,my,r,ntx,ty,mx,my,r,n。

第二行 nn 个整数为 bib_i。

输出格式

一个整数为方案数  mod 10007\bmod 10007(质数)后的值。

2 2 1 1 2 0
1

数据规模与约定

对于 100%100\% 的数据,1≤tx,ty,mx,my≤8001\le tx,ty,mx,my\le 800,1≤r≤16001\le r\le 1600,0≤n≤500\le n\le 50,输入数据保证每个 bib_i 都是 1010 的倍数,1≤bi≤min⁡(mx,my)1\le bi\le \min(mx,my),且 bib_i 各不相同。