集訓(xùn)隊(duì)作業(yè)畫家工作室

的方格矩形。尺寸為i的矩形包含2i行、2i列，并且在某些行與列的交點(diǎn)處有洞。定義尺寸為0的矩形是一個(gè)洞。對于i>0，尺寸為i的矩形可以劃分為四個(gè)尺寸為i-1的矩形，見下圖：沒有尺寸為i-的矩尺寸為i-的矩尺寸為i-的矩圖中位于右邊以及左下位置的都是尺寸為i-1的矩形。而左上位置一個(gè)2i1*

的完整正方形（無洞。完整的油畫就是這樣構(gòu)造的首先，給出三個(gè)非負(fù)整數(shù)n，a，b。然后，拿出兩個(gè)尺的一張向右移動a列，向上移動b行。最后，這個(gè)樣本移到一比如，考慮下面這兩個(gè)尺寸為2的矩形[輸入輸入文件“MAL.IN”的首行包含了一個(gè)數(shù)n，0<=n<=100，表示用來做油畫的矩形的尺寸。接下來的兩行分別給出了ab，0<=a,b2n。a表示向右移動的列數(shù)，b表示向上移動的行數(shù)。[輸出[輸入示例222[輸出示例3MAL解題報(bào)[題意分析POI9801x

ab個(gè)單位。在第二個(gè)正方形中對應(yīng)的坐標(biāo)為(x+b,y-a)。的(x,y)[約定ssSk1Sk (sk位二進(jìn)制數(shù)，0<=Si<=1，0<=i<k)[算法分析一個(gè)應(yīng)該符合的條件是什么。n 洞：(0,1)(1,0) 洞：(0,3)(1,2)(1,3)(2,1)(2,3)(3,0)(3,1)(3,2)觀察后，可以得出有關(guān)洞的幾個(gè)結(jié)論在邊長為2n的正方形中，設(shè)(x,y)為一個(gè)洞的坐標(biāo)，那么在2n+1的正方形中(x+2n,y)是一個(gè)洞(x,y+2n)是一個(gè)洞(x+2n,y+2n)是一個(gè)洞不（x，y<2n不(0Xn

X Yn

Y12100 。

1X0

1X0

是根據(jù)這四條結(jié)論，可以得出如下定理是定理*在邊長為2n的正方形中，如果坐標(biāo)(x,y)滿足：對于任一個(gè)滿足0<=I<nI，XiYi中至少有一個(gè)不為0，那么(x,y)對應(yīng)的格子為一個(gè) 把x+b、y-a這兩種十進(jìn)制的運(yùn)算都變?yōu)槎M(jìn)制來考慮。下面 用動態(tài)規(guī)劃求解坐標(biāo)的個(gè)數(shù)xy0~I-1位已經(jīng)確定且滿足定理*x+b、y-a0~I-1也可以計(jì)算出來，并且，x+bIp，y-aI位上產(chǎn)XI-1XI-2……X1 pBI-1BI-2B1B0RI-1RI-2R1

YI-1YI-2……Y1 qAI-1AI-2A1A0TI-1TI-2……T1T0F(I,p,q)表示(I,p,q)對應(yīng)的狀態(tài)總數(shù)，亦即有多少個(gè)(x,y)I位滿足pq。很自然的，想到用I來劃分階段，共有n個(gè)階段。下面，設(shè)法I-1I個(gè)階段之間架起橋梁。RI≡XI+BI+p(mod TI≡YI-AI-q(mod p’=q’=-[(YI-AI- （XiYi0，滿足定理* （RiTi0，滿足定理*（表示取下整，[-0.5]=-滿足上面五個(gè)式子的兩個(gè)狀態(tài)(I+1,p’,q’)與(I,p,q)可以實(shí)現(xiàn)轉(zhuǎn)化——即F(i1,p',q')

F(i,p,0XI,YI,XI,YIp,qp',q'/r