信息學集訓隊作業(yè)

1、ersStudio 題意分遞歸定義圖形g(n)1. 若n0，則g(n)2. 若n=0，g(n)例如g(2)gxy(n)表示把g(n)向右移動x 個出n,x,y，問gxy(n)ersStudio 題意分遞歸定義圖形g(n)1. 若n0，則g(n)2. 若n=0，g(n)例如g(2)gxy(n)表示把g(n)向右移動x 個出n,x,y，問gxy(n)g(n)有多少個洞是y個例如n=x=y=2的問題分這是一道計數(shù)的題目。由于圖形g(n)來求解設 gxy(n)與g(n)有x, y)得f(n, x, y)先來看看當 2n-1x2n，且 0y2n-1 時的情況2n-y2n-x 把3塊，設這三塊分別有ab,

2、 c有f(n, x, y)=a+b+c。下面分別計算a, b 和c由于第一塊恰好問題分這是一道計數(shù)的題目。由于圖形g(n)來求解設 gxy(n)與g(n)有x, y)得f(n, x, y)先來看看當 2n-1x2n，且 0y2n-1 時的情況2n-y2n-x 把3塊，設這三塊分別有ab, c有f(n, x, y)=a+b+c。下面分別計算a, b 和c由于第一塊恰好位于圖 gxy(n)的實心部分，故不會有所以 a=0。g(n-1)x-2n-y-2n-個，向上移動了個。根據 f 的定義，這個區(qū)域有b=f(n-1,x-2n-1y-2n-1)g(n-1)了x-2n-1y，故c=f(n-1, x-2n

3、-1y)因此，當 2n-1x2n，且0y2n-1 時f(n, x, y)=a+b+c=f(n-1, x-2n-1, y-2n-1)+f(n-1, x-2n-1, 33212n-y122n-x5 1和的區(qū)域 1 的部分可以用f(n-1,x,y)表示，g(n)1 和gxy(n)的區(qū)域2 的123疊部分可以用f(n-1, x+2n-1, y)表示，如此類推，可以得到f(n, x, y)首先注意到如果f(n,x,y)不滿足（-2nx2n且-2ny2n）這個條件，gn與gxy(n)就沒有任何相交的部分，如下圖。這時，有f(n, x,y0。因此，只要考慮（-2nx2n 且-2ny2n）時，f(n, x,

4、y)的值。321疊部分可以用f(n-1, x+2n-1, y)表示，如此類推，可以得到f(n, x, y)首先注意到如果f(n,x,y)不滿足（-2nx2n且-2ny2n）這個條件，gn與gxy(n)就沒有任何相交的部分，如下圖。這時，有f(n, x,y0。因此，只要考慮（-2nx2n 且-2ny2n部分為空，f(nx使為了便于描述把x, y轉換成二進制，具體方法是對于給出的n, x, y，若x2n或者y2n，則f(n, x, 希望能夠得到函數(shù)F xxx f(n,x,y) f(n1,xd2,yd2n1n1kkkk1n yyy y1,0),(0,0),(0,0n 根據F這樣， 就得到了函數(shù)F的遞

5、推式。因為（-2nx2n且-2ny2n，所以我們可以限定a, b 的范圍：0a, b1。又因為F(k)的遞推式只與F(k-1)有關，若讀入n, x, 若x2n 或者y2nans=0，并轉 利用遞推式計算函數(shù)ans=F(n,0,輸出F，二是要用空間復雜度為O(n)。1d,(,()(2mod2 kxmod2 d根據F這樣， 就得到了函數(shù)F的遞推式。因為（-2nx2n且-2ny2n，所以我們可以限定a, b 的范圍：0a, b1。又因為F(k)的遞推式只與F(k-1)有關，若讀入n, x, 若x2n 或者y2nans=0，并轉 利用遞推式計算函數(shù)ans=F(n,0,輸出F，二是要用空間復雜度為O(n)。1d,(,()(2mod2 kxmod2 dkbyd)k 1k 1 b)yd)2 k1 k1 11Fmook20b2k)y2kx2i0ki1 k xx F(1 od2a2d2,ymod2b2d2 k 1 k k