250pt MagicalGirlLevelOneDivOne
某神在(0,0)处, 需要走到(x,y)处(0<x,y<=10^9), 他只能按类似马跳的方式走, 即, 给出一个n, 他可以从(a,b)走到(a-1,b-n) (a+1,b-n) (a-1,b+n) (a+1,b+n) (a-n,b-1) (a+n,b-1) (a-n,b+1) (a+n, b+1) 中的一个.现在给出50个不同的n[1..50], 他可以以任意的n[i]方式走, 每种方式的使用次数不限. 问能否走到目的地(x,y).

很明显, 此神可以沿任意方向2步2步的走, 即先走个(+1,-n), 再走个(+1,+n). 所以能否到终点, 只与奇偶性有关. 
经过一阵分类讨论可知:
1) 如果x+y=0(mod 2), 则YES. 
2) 如果x+y=1(mod 2), 且n[i]中有偶数, 则YES.
3) 否则NO.

[杂]

600pt MagicalGirlLevelTwoDivOne
给一个H*W(1<=H,W<=50)的矩阵A, 每一位上已经有一个1~9的数字, 或者是个'.', 在'.'处可以填上任意1~9的数字. 再给出n和m(1<=n<=min{10,H}, 1<=m<=min{10,W}). 问一共有多少种填'?'的方法, 使得整个矩阵满足:
对任意的r和c, 以(r,c)开始的水平方向上连续m个数之和是奇数;
对任意的r和c, 以(r,c)开始的垂直方向上连续n个数之和是奇数.

首先要注意到一个性质: 对任意r和c有 A[r,c]与A[r+n,c]的奇偶性相同. 很显然, 因为要满足A[r,c]+A[r+1,c]+...+A[r+n-1,c]与A[r+1,c]+...+A[r+n-1,c]+A[r+n,c]的奇偶性相同, 都是奇数. 列上同样有A[r,c]与A[r,c+m]奇偶性相同.
因此在一行上, 只用记录n位的奇偶状态, 列上同理. 这样,所有的(r+pn,c+qm)都能合并成同一个点, 且只有两种状态: 奇和偶. 合并后该点为奇(或偶)的方法数, 等于组成它的所有点方法数之积. 最后整个矩阵合并压缩成一个n*m的矩阵, 就可以用状态DP来搞, 求每行每列之和都为奇的方法数. dp[n][1<<m], 前n行, 每一列和的奇偶性对应bit为0或1. O(1<<m)的转移复杂度, 转移时要注意该行状态1有奇数个.

觉得是道很好的题, 状态设计很巧妙...

[状态DP 状态压缩设计]

900pt MagicalGirlLevelThreeDivOne
某神给出K(K<=50)个01串, 每个串的长度不超过50. 用这些串组成新的串放到数组A[]里. 如果i<K, 则A[i]为给出的第i个串. 否则A[i] = A[i-1] + A[i-K-1] + A[i-2*K-1] + ... + A[i-p*K-1], 其中p是使i-p*K-1>=0的最大整数. 现在此神给出n, lo, hi, 要你求A[n]的子串A[n][lo...hi]中有多少个连续的1. 0<=n<=10^15, 0<=hi<= min{A[n]的长度, 10^15}, 0<=lo<=hi. 所有计数以0开始.

首先随便打个表或者手推一下化简A[i]的递推式, 可以发现当i>=2*K时, A[i] = A[i-1] + (A[i-K-1] + ... A[i-p*K-1]) = A[i-1] + A[i-K], 而K<=50. 所以A[i]的长度关于i是指数增长的, 50log(10^15)可能够用(严格证明不太会, 求指导#.#). 因此其实n<=10^15范围是坑爹的, hi不会超过A[10^4]的长度. 而这些串的前缀都是一样的, 所以A[n][lo..hi]其实与A[10^4][lo..hi]相同.
这样便可直接利用A[i] = A[i-1] + A[i-K]的关系分治. 和用线段树求最长连续1串的思想差不多: 每个结点的状态变量是(id,lo,hi), 存放A[id][lo..hi]的最优解. 除了存放当前段的最大长度max外, 为了能合并子区间, 还要记录当前区间从左端开始连续1的个数sl, 和从右端开始连续1的个数sr. 剩下的工作与线段树无异, 假设要求(id, lo, hi)的(max, sl, sr):
对于A[id], 它的左儿子就是A[id-1], 右儿子是A[id-K].
1)如果id<2*K, 直接暴力.
2)如果lo>=len[id-1](类似于线段树中的查询区间完全落在右儿子), 则递归查询(id-K, lo-len[id-1], hi-len[id-1]).
3)如果hi<len[id-1], 则递归查询(id-1, lo, hi).
4)否则两个儿子都要查询, 并根据返回的结果求当前区间的结果.

分治思想很强大, 用map写的"线段树"很YD, 偶依然蒻爆了.

[分治 复杂度分析]