今給一由01組成的字串A1(長度100萬)
定義A2=A1A1'，即原A1接上自己的補串
問對給出的n(到10^18)，An串的「01各數相同子串數」有多少？
例如
001110有4個子串合乎要求
123456<--編號，[1,4][2,3][5,6][1,6]四個子串內0和1數量相等
程式碼：從缺
我們需要解決的大問題有兩個：
一、怎麼樣在O(m)或O(mlgm)一類的時間得知A1的答案
二、如何利用A(n+1)=AnAn'的規律，在O(n)時間甚至O(lgn)內算出An答案？
首先對問題一，土法煉鋼用前綴的方法
設計函數b(x)代表第1個字元到第x個字元中，1的個數-0的個數
A1：0,0,1,1,1,0
b(x)：-1,-2,-1,0,1,0
顯然b(x)可以O(m)構造出來，這函數中所有的0都表示一組[1,x]的解
以本例來說[1,4]和[1,6]已經被找到了
再來，發現其他的b(x)值只要能「兩兩配對」就是一組解
例如這兒有兩個-1值，b(3)-b(1)=0、意味著[2,3]是合乎要求的解
另外別忘了0也是可以配對的，b(6)-b(4)=0、[5,6]也是一組解
如此一來，假如算到第x個字元
我們關心的就只是「在這之前有多少-1？多少0？」…
順利的把一個字串表示成了表格b：
-2 : 1個
-1 : 2個
0 : 2個
1 : 1個
如何快速回頭檢查這個表格可以直接開陣列來表示，第一問O(m)解決
再來對於第二問，我們需要觀察表格b變化的規律，以A1=001當例子
| 001 | 001110 | 001110110001 | |
| 2 | 0 | 0 | 1 |
| 1 | 0 | 1 | 3 |
| 0 | 0 | 2 | 4 |
| -1 | 2 | 2 | 3 |
| -2 | 1 | 1 | 1 |
觀察手算001->001110的過程，首先知道001的b序列是-1,-2,-1
那麼很簡單的知道補串A1'序列(以自己來說)將會是1,2,1
我們把這兩個暫時串起來得到-1,-2,-1/1,2,1
根據我們b函數這個前綴定義，後半這三個數字必須加上-1 (A1的最後一個數字)
得到-1,-2,-1,0,1,0
然而如何過度到A3呢？很機巧的發現，A1->A2這一步，一定會使最後一位變成0
想像一下假如A1得出的b序列值是x,y,z，A1'就是-x,-y,-z
最後A1'必須全體+z，正負z消除、會歸0
如此從A2開始，想手算b序列的下一項，只要簡單的正負顛倒、接起來就可以
b表格、A2的答案已經簡單到手，怎麼造出A3的答案呢？
我們把A3切成三個部分：原本A2已經有的子串數、A2'造成的子串數、界於兩者之間
所以很顯然A3=2 * A2 + f2 (請容許我設定f2是「一坨」代表A2,A2'之間合乎的串數)
觀察一下可以發現
f2=(表格2中)：[-2數量]*[2數量] + [-1數量]*[1數量] + [0數量]*[0數量] + [1數量]*[-1數量] + [2數量]*[-2數量]
很有對稱感，再來A2過到A3的過程會更有對稱感
請看一下A3那欄表格，發現：A3中2的數量=A2中2的數量+A2中-2的數量
在正負疊加之下很容易直覺證明：A3以後這個b表格是對稱的(x和-x的數量相等)
所以f3開始公式可以化簡成f3= 2(2數量)^2 + 2(1數量)^2 + (0數量)^2
並且由於A3以後的疊加規律，我們發現一件事：f4= 4 * f3
因為任何(x數量)在下一欄都會加倍，那麼它們的平方項會整齊的變成四倍
整理一下有兩樣遞回式，對於n>=3
An+1 = 2 * An + fn
fn+1 = 4 * fn
行將至此對於問題二，已經可以輕鬆O(n)求出答案
最後怎麼樣可以達到終極目標O(m+lgn)來AC本題呢？
經過手動模擬A1、A2、A3的情形，有了兩項變數的遞回式
精彩的來了，我們構造矩陣：
[4 0][f3] [f4]
[1 2][A3] = [A4]
只要模仿類似費氏數列那種方法，將矩陣4,0,1,2自己冪n-3次
乘上預先調理好的f3、A3，就可以漂亮得到An了
最後，原題的mod值有到long long、需要特別處理才能全對…(死)
<解題報告完，這篇數學式好多、寫得好亂>
沒有留言:
張貼留言