250pt MagicalGirlLevelOneDivOne
某神在(0,0)處, 需要走到(x,y)處(0<x,y<=10^9), 他只能按類(lèi)似馬跳的方式走, 即, 給出一個(gè)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) 中的一個(gè).現(xiàn)在給出50個(gè)不同的n[1..50], 他可以以任意的n[i]方式走, 每種方式的使用次數(shù)不限. 問(wèn)能否走到目的地(x,y).

很明顯, 此神可以沿任意方向2步2步的走, 即先走個(gè)(+1,-n), 再走個(gè)(+1,+n). 所以能否到終點(diǎn), 只與奇偶性有關(guān). 
經(jīng)過(guò)一陣分類(lèi)討論可知:
1) 如果x+y=0(mod 2), 則YES. 
2) 如果x+y=1(mod 2), 且n[i]中有偶數(shù), 則YES.
3) 否則NO.

[雜]

600pt MagicalGirlLevelTwoDivOne
給一個(gè)H*W(1<=H,W<=50)的矩陣A, 每一位上已經(jīng)有一個(gè)1~9的數(shù)字, 或者是個(gè)'.', 在'.'處可以填上任意1~9的數(shù)字. 再給出n和m(1<=n<=min{10,H}, 1<=m<=min{10,W}). 問(wèn)一共有多少種填'?'的方法, 使得整個(gè)矩陣滿(mǎn)足:
對(duì)任意的r和c, 以(r,c)開(kāi)始的水平方向上連續(xù)m個(gè)數(shù)之和是奇數(shù);
對(duì)任意的r和c, 以(r,c)開(kāi)始的垂直方向上連續(xù)n個(gè)數(shù)之和是奇數(shù).

首先要注意到一個(gè)性質(zhì): 對(duì)任意r和c有 A[r,c]與A[r+n,c]的奇偶性相同. 很顯然, 因?yàn)橐獫M(mǎn)足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]的奇偶性相同, 都是奇數(shù). 列上同樣有A[r,c]與A[r,c+m]奇偶性相同.
因此在一行上, 只用記錄n位的奇偶狀態(tài), 列上同理. 這樣,所有的(r+pn,c+qm)都能合并成同一個(gè)點(diǎn), 且只有兩種狀態(tài): 奇和偶. 合并后該點(diǎn)為奇(或偶)的方法數(shù), 等于組成它的所有點(diǎn)方法數(shù)之積. 最后整個(gè)矩陣合并壓縮成一個(gè)n*m的矩陣, 就可以用狀態(tài)DP來(lái)搞, 求每行每列之和都為奇的方法數(shù). dp[n][1<<m], 前n行, 每一列和的奇偶性對(duì)應(yīng)bit為0或1. O(1<<m)的轉(zhuǎn)移復(fù)雜度, 轉(zhuǎn)移時(shí)要注意該行狀態(tài)1有奇數(shù)個(gè).

覺(jué)得是道很好的題, 狀態(tài)設(shè)計(jì)很巧妙...

[狀態(tài)DP 狀態(tài)壓縮設(shè)計(jì)]

900pt MagicalGirlLevelThreeDivOne
某神給出K(K<=50)個(gè)01串, 每個(gè)串的長(zhǎng)度不超過(guò)50. 用這些串組成新的串放到數(shù)組A[]里. 如果i<K, 則A[i]為給出的第i個(gè)串. 否則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的最大整數(shù). 現(xiàn)在此神給出n, lo, hi, 要你求A[n]的子串A[n][lo...hi]中有多少個(gè)連續(xù)的1. 0<=n<=10^15, 0<=hi<= min{A[n]的長(zhǎng)度, 10^15}, 0<=lo<=hi. 所有計(jì)數(shù)以0開(kāi)始.

首先隨便打個(gè)表或者手推一下化簡(jiǎn)A[i]的遞推式, 可以發(fā)現(xiàn)當(dāng)i>=2*K時(shí), A[i] = A[i-1] + (A[i-K-1] + ... A[i-p*K-1]) = A[i-1] + A[i-K], 而K<=50. 所以A[i]的長(zhǎng)度關(guān)于i是指數(shù)增長(zhǎng)的, 50log(10^15)可能夠用(嚴(yán)格證明不太會(huì), 求指導(dǎo)#.#). 因此其實(shí)n<=10^15范圍是坑爹的, hi不會(huì)超過(guò)A[10^4]的長(zhǎng)度. 而這些串的前綴都是一樣的, 所以A[n][lo..hi]其實(shí)與A[10^4][lo..hi]相同.
這樣便可直接利用A[i] = A[i-1] + A[i-K]的關(guān)系分治. 和用線(xiàn)段樹(shù)求最長(zhǎng)連續(xù)1串的思想差不多: 每個(gè)結(jié)點(diǎn)的狀態(tài)變量是(id,lo,hi), 存放A[id][lo..hi]的最優(yōu)解. 除了存放當(dāng)前段的最大長(zhǎng)度max外, 為了能合并子區(qū)間, 還要記錄當(dāng)前區(qū)間從左端開(kāi)始連續(xù)1的個(gè)數(shù)sl, 和從右端開(kāi)始連續(xù)1的個(gè)數(shù)sr. 剩下的工作與線(xiàn)段樹(shù)無(wú)異, 假設(shè)要求(id, lo, hi)的(max, sl, sr):
對(duì)于A[id], 它的左兒子就是A[id-1], 右兒子是A[id-K].
1)如果id<2*K, 直接暴力.
2)如果lo>=len[id-1](類(lèi)似于線(xiàn)段樹(shù)中的查詢(xún)區(qū)間完全落在右兒子), 則遞歸查詢(xún)(id-K, lo-len[id-1], hi-len[id-1]).
3)如果hi<len[id-1], 則遞歸查詢(xún)(id-1, lo, hi).
4)否則兩個(gè)兒子都要查詢(xún), 并根據(jù)返回的結(jié)果求當(dāng)前區(qū)間的結(jié)果.

分治思想很強(qiáng)大, 用map寫(xiě)的"線(xiàn)段樹(shù)"很YD, 偶依然蒻爆了.

[分治 復(fù)雜度分析]