Posted on 2009-11-16 02:34
王之昊 閱讀(208)
評論(0) 編輯 收藏 引用
NOT TWO
一道有意思的數學題, m * n的棋盤最多能放幾個子,要求每格只能放一個,且任意兩個的距離不能為2
令人眼前一亮的是出題人把棋盤劃分為四部分,每部分相互獨立,的確優美
IOIString
關鍵想到反面.即求有多少個不是IOIString的串,再用所有情況減去之. 而這樣想是看到了一個結論:
若該串不是IOIString,那么其所有的 I 等距, 且相鄰 I 差距奇數個.然后就可以搞了.
簡略證明一下那個結論: 題目說 I 在 位置 a 上, O 在位置 a + b上, I在位置 a + 2*b上 就構成了一個IOIString.
1 那么相鄰的兩個I之間必相差奇數.如果相差偶數( a , a + 2*k) 那么中間必有 (a + k)是O,矛盾
2 必等距, 如果不等距 三個位置為a , a + b a + b + c ( b != c)則中間必有一點為 a + (b+c)/2是O ,矛盾
此題讓我第一次在tc上tle, 悲劇
IOIString 和IOI有什么關系莫?
IncreasingNumber
看到10^18數位的數著實嚇了一跳, 這么長的一個數!!!
出題者將一個遞增數表示成 a*1 + b*11 + c*111 + .... (a + b + c + .. <= 9)的表示方式以前沒見過,感覺很好
然后接下來的就簡單了.自然想到把模divisor相等的歸到一類.而且這一類里面的東西是等價的.然后再dp
1 , 11, 111, ..., ( mod divisor)是一個P字形的循環.剛開始沒反應過來
舉個例子來說如果 11 = 1111 ( mod d) 那么 111 = 11111(mod d) 因為 11 * 10 + 1 = 1111 * 10 + 1 (mod d)
無限ym petr. 再次 ym petr~~