一開始我在那里dp推，發(fā)現(xiàn)有重復(fù)之類的東西不好搞
 看了Sevenkplus的，容斥，感覺好神奇
 
 最多有P = N - M + 1個(gè)回文串
 由于規(guī)模比較小，枚舉選出哪幾個(gè)作為回文串，使得至少有K個(gè)，令這個(gè)模式為Ti
 （如N = 3, M= 2 , K = 1 ，一個(gè)合法的模式為 010）
 則答案為|T0∪T1...∪Tc|，這里就要用到容斥了
 = ∑|Ti|
   -∑|Ti∩Tj|
   +∑|Ti∩Tj∩Tk|
   ...
     直接套用的話復(fù)雜度為2^(2^P) ！！

  與平常的容斥有點(diǎn)不一樣，這里存在很多“Tj包含于Ti”，即其交集就是子集了
  如011包含于010
  因?yàn)闈M足011的肯定滿足010，所以011是010的子集，這里注意了！！二進(jìn)制枚舉Ti的超集Tj，是模式Ti的子集

  畫個(gè)韋恩圖，一個(gè)集合Tj要計(jì)算的次數(shù)就是先減去其余集合Ti在這部分算的次數(shù)（減完就為空了），再加上1
  即為 1 - 其余集合Ti在這部分算的次數(shù)
 用num[i]表示集合Ti需要算的次數(shù)，則num[i] = 1 - ∑num[ii]  ii為i的超集
 for(int j = i+1 ; j < (1<<P) ; j++)
 {
  if((j & i) == i)//j是i的子集
   num[j] -= num[i];
 }
 所以集合Ti對(duì)答案的貢獻(xiàn)為 ans += num[i]*26^cnt
 O((2^p)^2)
 cnt為集合Ti獨(dú)立變量的個(gè)數(shù)
 對(duì)Ti,求獨(dú)立變量的個(gè)數(shù)，可以先建圖（利用回文串兩端相等的性質(zhì)），然后dfs算出連通塊的個(gè)數(shù)就是獨(dú)立變量的個(gè)數(shù)了
*/


TCO'10 Qualification Round 1A 1000pt MegadiamondHunt
/*
 將只含有'<','>'的串，每次去掉<..<>..>連著的幾個(gè)
 如果去掉中有n對(duì)，則得分為n^2
 求最大得分
 
 一開始以為去掉的順序沒關(guān)系，過不了最后一個(gè)sample
 看了LayCurse的代碼，它是每次選擇 極大的<..<>..>中最小的一個(gè)去掉
 這樣子去貪心...
 如 <<<>><>>
 如果先去掉<<>>，然后剩下<<>> 得分為 2^2+2^2
 但若先去掉<>，則剩下<<<>>> 得分為 1 + 3^2
 因?yàn)椋紤]一個(gè)極大的<..<>..>,若它能擴(kuò)大，則它的左右肯定先去掉了一個(gè)
 極大的<..<>..>，如果已去掉的那個(gè)比當(dāng)前的大，得分是不會(huì)比先去掉當(dāng)前
 這個(gè)較小的大，所以每次選極大中的最小那個(gè)去掉
*/

zoj 3458
/*
 0 < b - a < 1 + 2sqrt(a)  求 floor(sqrt(a)+sqrt(b))^n % 2(a+b)

 看watashi的，沒接觸過這種問題，做法挺神奇( ⊙ o ⊙ )！

 由 0 < b - a < 1 + 2sqrt(a)
  => 0 < sqrt(b) - sqrt(a) < 1
 令Xn = (sqrt(b)+sqrt(a))^2n = (b+a+2sqrt(ab))^n
    Yn = (sqrt(b)-sqrt(a))^2n = (b+a-2sqrt(ab))^n
    Zn = Xn +Yn = (b+a+2sqrt(ab))^n + (b+a-2sqrt(ab))^n
 
 由于X1 = b+a+2sqrt(ab) , Y1 = b+a-2sqrt(ab)
 是方程(U-X1)(U-Y1) = 0 ，即 U^2 - 2(a+b)U + (a-b)^2 = 0 的根
 則Zn+2 = 2(a+b)Zn+1 - (a-b)^2Zn
 用矩陣乘法可以求得Zn
 由于Yn<1 ，所以floor(Xn) = Zn - 1，所以最后答案Zn-1即可

 以上方法有個(gè)地方
 “
 由于X1 = b+a+2sqrt(ab) , Y1 = b+a-2sqrt(ab)
 是方程(U-X1)(U-Y1) = 0 ，即 U^2 - 2(a+b)U + (a-b)^2 = 0 的根
 則Zn+2 = 2(a+b)Zn+1 - (a-b)^2Zn
 ”
 我不太懂，查了下特征根的一點(diǎn)東西
 若An+2 = pAn+1 +qAn
 則An = C1α^n + C2β^n
 上面應(yīng)該是逆過來
 由Zn = Xn +Yn = (b+a+2sqrt(ab))^n + (b+a-2sqrt(ab))^n
 推出Zn+2 = 2(a+b)Zn+1 - (a-b)^2Zn
*/


zoj 3461
/*
 給出一個(gè)無向圖，有邊權(quán)，點(diǎn)權(quán)。點(diǎn)權(quán)val[i]為正的表示要將val[i]分出給點(diǎn)權(quán)為負(fù)的，每個(gè)點(diǎn)可以作為中間節(jié)點(diǎn)
 點(diǎn)權(quán)val[i]為負(fù)的表示要接收val[i]，傳送的花費(fèi)為路徑的距離，求最小距離
 n<=16

 按照題意，花費(fèi)即為∑val[i] = 0 的樹的MST 
 我有想過需要?jiǎng)澐殖蓭撞糠郑鸪鯖]想過怎么劃分

 解題報(bào)告是枚舉子集作為一部分樹，dp求解（n那么小，要往集合方面想吧?。?br> 即dp[mask] = dp[mask^i] + mst[i];
 注意需要sum[mask] = 0 的才有意義
*/


zoj 3463
/*
 一只手，相對(duì)拇指不動(dòng)，至少要占5個(gè)鍵的位置，至多可以彈到9個(gè)鍵。
 拇指移動(dòng)距離x需要花費(fèi)floor(sqrt(x))，已知左右手初始位置和接下來
 需要彈奏的1000個(gè)鍵，求最小花費(fèi)。

 狀態(tài)比較明顯，dp[n,l,r]表示已經(jīng)彈了n個(gè)音符，左、右手拇指分別在l,r
 的最小代價(jià)
 無效狀態(tài)很多，不能計(jì)算，否則會(huì)超時(shí)
 枚舉左右手到需要彈的位置，其他情況不用考慮，不會(huì)更優(yōu)

 這句話不太懂："But, one finger touching the key between two fingers of the other hand is fobidden."
 貌似不用處理？
 
 看watashi的代碼的
 sqrt的初始化很漂亮

 hdu 3651是簡(jiǎn)化版，都是無效狀態(tài)不用算，決策是直接到需要的位置
*/


zoj 3464
/*
 N個(gè)人，起初在一條線上。
 每個(gè)人有速度vi，且每個(gè)人最多只能跑帶著棒Ts，問最快時(shí)間接棒跑完L

 貪心，最快的人跑最后Ts，倒數(shù)第二快的跑倒數(shù)第二Ts...
*/



TCO'10 Wildcard Round 500pt CalculationCards
/*
 n<=50張卡 如3張：+1 ,-2 , *3  其排列有
 0 + 1 - 2 * 3 = -5
 0 + 1 * 3 - 2 = 1
 0 - 2 + 1 * 3 = 1
 0 - 2 * 3 + 1 = -5
 0 * 3 + 1 - 2 = -1
 0 * 3 - 2 + 1 = -1
 期望為-1.6666666666666667
 求給定的n張卡的期望值

 不可能n!的枚舉
 設(shè)+、-卡共有s張
 按照一個(gè)+、-卡后接連續(xù)的*卡分類，則有s部分，其全排列不影響期望（總共s!種，但期望都一樣）
 所以只考慮無序的（無序可以用默認(rèn)的一種順序，即卡出現(xiàn)的先后順序，或者說編號(hào)）
 ***a1***a2*** ... as***
 ***表示*卡
 由于是等概率的，所以總體來統(tǒng)計(jì)，每個(gè)+、-卡都會(huì)接同樣的*卡，
 既然每張+、-卡情況一樣，那就考慮a1卡
 其后會(huì)接0,1...,m張*卡
 答案就是 sum * (0,1,...m)張*卡的期望   sum = ∑ai
 求k張*卡的期望可以用dp做
 看bmerry代碼的做法，解題報(bào)告的麻煩一點(diǎn)吧
 一開始只有s張a卡排著，然后插入一張張*卡
 dp[i,j]表示插入了前面i張*卡，a1后接j張*卡，它們構(gòu)成的期望值
 分第i張卡插不插入到a1之后構(gòu)成j張連續(xù)的*卡，概率為 該插入的位置/總位置
 dp[i,j] =
    dp[i-1,j] * (n-j-1)/n
   + m[i]*dp[i-1,j-1] * j/n
 n為s+i

 這道題一個(gè)很好的想法就是答案為sum * (0,1,...m)張*卡的期望   sum = ∑ai   ！！?。。。?br> 而求后接k張*卡的期望，bmerry的做法是一張一張卡插入，然后求得期望
 小規(guī)模到大規(guī)模，通過考慮插入位置來實(shí)現(xiàn)，這個(gè)做法應(yīng)該較好
*/


TCO 2010 Qualification Round 1 250pt
/*
 題意：一個(gè)只有B,G組成的串，要將他們swap相鄰的，變成BB...GG或GG...BB
 求最少的次數(shù)  串長(zhǎng)<=50
 我用n^2的求逆序?qū)Γ?br> 看了別人的，直接就是累計(jì)將每個(gè)字母B移到左邊的步數(shù)
 if(row[i] == 'B')
 {
  tot += i - x;
  x ++;
 }
 x是當(dāng)前需要放B的位置，交換后就++移到下個(gè)位置
*/



TCO'10 Qualification Round 2 1000pt HandlesSpelling
/*
 給出一個(gè)文本串，一些模式串
 現(xiàn)要將模式串覆蓋文本串，不能有重疊部分
 求使得A^2 - B 最大
 A是最長(zhǎng)覆蓋的長(zhǎng)度，B是還未覆蓋的個(gè)數(shù)

 一開始一直關(guān)注A^2 - B ，不知怎么做
 解題報(bào)告是分開來做
 要求得A^2 - B的最大值，可以通過枚舉A
 枚舉某一段作為最大覆蓋值，然后看其左右未覆蓋的個(gè)數(shù)

 而計(jì)算為覆蓋的個(gè)數(shù)可以通過dp了
 dp[i,j]表示[i,j]為覆蓋的個(gè)數(shù)
 枚舉[i,i']一段是被覆蓋的，則答案就是min(dp[i'+1,j])
 注意的是，初始化有些dp[i,j]=0，就直接continue
*/


SRM 216 Refactoring
/*
 問一個(gè)數(shù)n<=2*10^9 可以拆分成多少種因子相乘的情況
 24 = 2*2*2*3
   = 2*2*6
   = 2*3*4
   = 2*12
   = 3*8
   = 4*6
 
 不需要高深的數(shù)學(xué)知識(shí)?。?！
 暴力dfs做
 f(n) = 1 + ∑f(n/i) 
 i 為其因子,i > 1 && i <= n/i（保證不會(huì)進(jìn)入多余的分支）
 為了保證無序，可以多加一個(gè)參數(shù)start，表示該輪的因子>=start
*/



SRM 223 PrimeAnagrams
/*
 給出一個(gè)數(shù)字串len<=8
 求將其分為三部分，每部分都是素?cái)?shù)，且乘積最小

 看解題報(bào)告的
 8! = 40320 ，而分成3部分情況為C(7,2) = 21種
 所以枚舉全排列，然后分成3部分來做

 Brute Force ！?。。。?！
*/


zoj 3471 mask dp
/*
 n<=10個(gè)球，i碰j會(huì)產(chǎn)生a[i,j]的能量，j同時(shí)會(huì)消失
 問最多產(chǎn)生的能量之和
 
 我知道跟mask有關(guān)，為啥還是想不出？
 
 要從整體來看??！
 現(xiàn)在有一些球，掩碼為mask
 假設(shè)最先碰撞的是u->v，然后v消失了
 局面就變成了沒有v的一些球了, mask^(1<<v)，一個(gè)子問題了
 所以轉(zhuǎn)移就是枚舉u,v
 dp[mask] = max(dp[mask^(1<<v)+a[u][v]) 

 從局面來看吧！??！

 一開始我是像zoj 3461 dp[mask] = dp[mask^i] + mst[i];
 發(fā)現(xiàn)會(huì)出問題，這樣子是隔離了一部分，但顯然隔離了后會(huì)丟失了連接著兩部分的那個(gè)值
 
*/

zoj 3470
/*
 如圖，問某個(gè)數(shù)字上下左右的數(shù)字是多少
 既然題目給了一副對(duì)應(yīng)的坐標(biāo)，發(fā)現(xiàn)，問題的重點(diǎn)就在于點(diǎn)坐標(biāo)跟數(shù)字的轉(zhuǎn)換
 
 我是先找出數(shù)字val在第n圈 即 (n-1)^2 < val <= n^2
 然后該圈的起點(diǎn)start就是(n-1)^2 + 1 ， 然后通過比較start，就能求出坐標(biāo)了
 發(fā)現(xiàn)奇數(shù)圈會(huì)使minx--,miny-- ; 偶數(shù)圈會(huì)使maxx++,maxy++
 數(shù)量關(guān)系是minx = miny = -(n-1)/2 , maxx = maxy = n/2
 
 然后點(diǎn)(x,y)轉(zhuǎn)化為值，跟上面類似的
 求出第n圈  二分判斷 minx<=x<=maxx , miny<=y<=maxy
 然后求出角落的點(diǎn)等等...
*/


zoj 3468
/*
 Dice游戲，一開始Attacker Defender各有骰子n,m個(gè)
 雙方拿出一定骰子來投，累計(jì)和
 誰多點(diǎn)誰贏
 Attacker拿出至少1個(gè)來攻擊
 問Attacker一次攻擊贏的概率
 骰子數(shù)目<=8
 枚舉Attacker投出的和為j，然后計(jì)算達(dá)到j(luò)的方法數(shù)，以及Defender投出的和小于j的方法數(shù)
 
 用背包的方法計(jì)算方法數(shù)
*/

CF 60D
/*
 n<=10^6個(gè)點(diǎn)，每個(gè)點(diǎn)有權(quán)值a[i]<=10^7 各不相同
 若存在一個(gè)數(shù)x，使得a[i],a[j],x   is a beautiful triple
 即a^2 + b^2 = c^2   a,b,c互素
 則i可以傳播laugh到j(luò)
 問最少需要需要讓多少個(gè)頂點(diǎn)自行l(wèi)augh，然后傳播到全部的頂點(diǎn)

 看了解題報(bào)告的
 并查集做
 但如何判斷beautiful triple 兩兩判斷O(n^2)會(huì)超時(shí)

 有個(gè)性質(zhì)：對(duì)于滿足a^2 + b^2 = c^2的數(shù)，可用勾股數(shù)公式生成：
 (x^2-y^2 , 2xy , x^2+y^2)  x>y
 該公式能生成所有的素勾股數(shù)（互質(zhì)），需1奇1偶 ，且gcd(x,y) = 1
 也能生出部分派生勾股數(shù)(如 6 8 10) ， 2奇或2偶
 
 由于a[i]<=MAX       MAX= 10^7
 所以必有x^2-y^2 <= MAX , 2xy <= MAX  但x^2+y^2不一定<= MAX
 2y^2<=MAX
 x^2<=MAX+y^2<=3MAX/2
 => x<=sqrt(3MAX/2) , y <= sqrt(MAX/2)
 所以枚舉x,y復(fù)雜度為O(MAX)
 (注意x,y是1奇1偶且gcd(x,y) = 1)

 參考watashi代碼寫的 
*/


CF60E
/*
 一開始 n <= 10^6 個(gè) Mushroom 按升序排成一條直線 ， 每個(gè)Mushroom重為a[i]
 下一秒時(shí)，a[i] , a[i+1] 之間會(huì)出現(xiàn)一個(gè)a[i]+a[i+1]的Mushroom
 而x秒時(shí)，某人重新排序這些Mushroom
 問再經(jīng)過y秒，所有Mushroom的重量之和

 0 a1  a2  a3
 1 a1  a1+a2  a2  a2+a3  a3
 2 a1  2a1+a2  a1+a2  a1+2a2  a2  2a2+a3  a2+a3  a2+2a3  a3
 3 ...
 設(shè)時(shí)間i時(shí)重量為Ti 則Ti = 3Ti-1 - (a1+an)
 所以前x可用矩陣乘法求出Tx
 然后由于sort，最大的值是Fx-1*an-1 + Fx*an （找規(guī)律 Fx-1*ai-1 + Fx*ai , Fx*ai-1 + Fx-1*ai）
 F是斐波那契數(shù)列  F[-1] = 0 , F[0] = 1
 然后修改a1+an值即可，再次矩陣乘法 算出后來的y秒
*/


noip2002 G2 字串變換 雙向BFS
/*
 給出A,B串
 以及一些變化方法，即x->y
 求A變到B的最短步數(shù)
 
 bfs慢點(diǎn)
 雙向會(huì)快點(diǎn)
 由于x->y是單向的，所以兩邊的結(jié)構(gòu)不同，優(yōu)先擴(kuò)展隊(duì)列長(zhǎng)度短的優(yōu)化就有用了
 注意反向BFS時(shí)擴(kuò)展的順序是y->x
*/

poj 2411
/*
 問n*m的棋盤放置1*2的骨牌的方案數(shù)
 n,m<=11
 
 枚舉行，遞推計(jì)算列
 dp[row,col,s]  row行之前已經(jīng)放好,且當(dāng)前row行處于s狀態(tài)
 遞推 通過在row行，col列之后放置，擴(kuò)展計(jì)算
 dp[row,col,s1] += dp[row-1,col,s2]

 不是記憶化搜索 是從0遞推
 為了打表，在每個(gè)分支都計(jì)算了  即:dp[row][col][s1] += dp[row-1][col][s2];
 否則，可以在最后的時(shí)候才計(jì)算的
*/

sgu 131
/*
 n*m棋盤，問用1*2, 2*2去掉一個(gè)角的骨牌覆蓋完的方案數(shù)
 
 狀態(tài)定義為 dp[row,s]表示當(dāng)前第row行狀態(tài)為s，且前row-1行已經(jīng)覆蓋完的方案數(shù)
 則 dp[row,s] <-- dp[row-1,s']
 轉(zhuǎn)移是枚舉row這一行每個(gè)位置（注意是整行）怎么放
 同時(shí)，若枚舉了row怎么放，則由狀態(tài)的定義，row-1之前的必須覆蓋完，就知道了s'是什么了！！！
 
 每個(gè)位置有7種放法，除了被之前的方法限制了，就不足
*/


hdu 2640
/*
 n*m的棋盤，有一些位置不能放，問最多能放多少個(gè)十字架
    @
 @@@
    @

 注意的是，每個(gè)@都需要放，所以棋盤相應(yīng)的位置需要是空的
*/


xmu 1118
/*
 求用1*1,1*2,1*3的磚塊鋪滿 3*N的板的方案數(shù)目
 1*3，最多影響3行 所以狀態(tài)需要記錄當(dāng)前行以及前一行的情況  2bit 共4種
 _    *    _    *
 _    _    *    *
 _表示空，*表示被覆蓋

 dp[row,s]表示row-1之前的已經(jīng)覆蓋完了，row-1,row的狀態(tài)為s時(shí)的值
 
 對(duì)row這一行的每個(gè)位置，枚舉其放的方法
 雖然說4種狀態(tài)，實(shí)際上轉(zhuǎn)移時(shí)很多是不需要的。因?yàn)闉榱藵M足row-1之前的是覆蓋完的

不放，可以轉(zhuǎn)移兩種，即上面的1,2種類型
*/



hdu 2240
/*
 給出如圖n*5棋盤，其中第一塊最多只能用c個(gè)，其余的不限
 問能否鋪滿
 跟sgu 131類似
 不過這里dp的值是記錄最少使用的1
 b1,b2是之前的方法對(duì)當(dāng)前的影響
*/



hdu 2606
/*
 用1*1, 2*2, 3*3, 4*4覆蓋完N*4的棋盤的方案總數(shù)
 遞推
 dp[n] =  dp[n-1]         最底部放4個(gè)1*1
           + 4*dp[n-2]     最底部組合出2*4的，總共有4種
           + 4*dp[n-3]     最底部組合出3*4的，總共有4種  2個(gè)是2塊2*2上下交錯(cuò) 2個(gè)是一塊3*3
           + 3*dp[n-4]     最底部組合出4*4的，總共有3種  2個(gè)是3塊2*2上下交錯(cuò) 1個(gè)是一塊4*4
    + 2*(dp[n-5]+dp[n-6]...+dp[0])    用2*2上下交錯(cuò)放的
 則dp[n-1] = ....
 兩式相減，得到dp[n] = 2dp[n-1] +3dp[n-2] - dp[n-4] - dp[n-5]    n>=5
 至于n<=4的，結(jié)合上面的dp[n]的式子計(jì)算

 腦殘了，wa了好幾次
 沒想到可以2*2上下交錯(cuò)  腦殘
*/



hnu 10816 ugly number
/*
 題意：給出n個(gè)素?cái)?shù)<=10000  n<=10
 問[x,y]區(qū)間內(nèi)只包含這些素?cái)?shù)因子的數(shù)，要求全部打印出來
 x,y<=2^31
 一開始看到規(guī)模嚇了一跳
 事實(shí)上，只含有這些因子的數(shù)是很少的
 注意不是倍數(shù)??！之前第一印象看成倍數(shù)，搞個(gè)容斥了，算了下2和3的，數(shù)據(jù)巨大....
 
 像poj 的 ugly number那樣子做
 由于每個(gè)數(shù)都得乘以這些素?cái)?shù)來擴(kuò)展
 用num[]數(shù)組存儲(chǔ)生成的所有數(shù)
 pos[i]表示素?cái)?shù)pr[i]當(dāng)前要乘以num[pos[i]]
 初始num[0] = 1  pos[i] = 0
 然后每一步擴(kuò)展一個(gè)數(shù)，該數(shù)為num[tot] = min(num[pos[i]]*pr[i])
 然后判斷每個(gè)num[pos[i]]*pr[i] 是否 = num[tot]，是的話 pos[i]+1
 
 這種思想還是沒能很好掌握...
 肯定的是，每個(gè)數(shù)都得乘以pr[1],pr[2]...
 要用pos[i]記錄當(dāng)前pr[i]乘到哪個(gè)數(shù)了?。?！
*/



08 ZhuHai Contest  E Magic Squares 雙向bf
/*
 問一個(gè)排列變?yōu)?*3幻方的最小步數(shù)
 每一步可以選擇一個(gè)角進(jìn)行旋轉(zhuǎn)
 
 狀態(tài)數(shù)不多9!
 先全排列得到目標(biāo)狀態(tài)
 再雙向bfs  挺快的
 用康托展開（變進(jìn)制）判重更快
*/


poj 3255 無向圖值次短路 ★★★
/*
 給出一個(gè)無向圖 n<=5000, m <= 30000
 求1到n的值次短的路，如果有多條最短路，但次短的還是需要大于最短的
 允許點(diǎn)、邊走多次

 靠解題報(bào)告保養(yǎng)~~~ T_T
 求1到其他點(diǎn)的最短路dist[] ，再求n到其他點(diǎn)的最短路rdist[]
 枚舉每條邊，找到次短的 dist[u] + (u,v) + rdist[v]

 啟示:  枚舉哪條邊作為中間的必須經(jīng)過的邊u->v，然后連接1->u, v->n
*/


scu 3904
/*
 一個(gè)序列seq[i]   n<=10^5                -10000<=seq[i]<=10000
 將其劃分成幾部分，使得每一部分之和>=0
 求所有的劃分方法數(shù)
 顯然dp[i] = ∑dp[j]   (sum[i] - sum[j] >= 0)
 O(n^2)會(huì)超時(shí)
 用線段樹加速
 我一開始是以下標(biāo)作為線段樹的數(shù)軸，記錄該段Min[p],Max[p],還有一個(gè)sDp[p]記錄該段所有dp值
 但這樣比較慢，維護(hù)相對(duì)多了點(diǎn)

 看了標(biāo)程，是先計(jì)算所有的sum[]，然后離散化
 以sum值作為數(shù)軸來搞，用樹狀數(shù)組就很容易寫了

*/


中大第三本 ch2 負(fù)權(quán)數(shù)
/*
 平時(shí) N = anR^n + ... + a0R^0  其中R>0
 負(fù)權(quán)數(shù)是R < 0,使用負(fù)權(quán)數(shù)表示的優(yōu)點(diǎn)是對(duì)于負(fù)數(shù)，不用前置的符號(hào)
 比如 -15 = 1*(-2)^5 + 1*(-2)^4 + 0*(-2)^3 + 0*(-2)^2 + 0*(-2)^1 + 1*(-2)^0
 現(xiàn)給出N,  -16<= R <=-2
 求N的負(fù)權(quán)數(shù)R表示（題目的答案輸出一行，表明表示是唯一的）
 (無論正權(quán)、負(fù)權(quán)，系數(shù)ai都是 0<=ai<|R|)
 
 因?yàn)槿∮噙\(yùn)算只使用語(yǔ)正整數(shù)除法，所以不能通過連續(xù)連除求余的方法！！??！
 寫成普通形式時(shí)：

 N >= 0
 N = an|R|^n + ... + a0|R|^0 R < 0
 i為奇數(shù)時(shí):
  ai|R|i = R(i+1) + (|R|-ai)Ri          為了保證a'>=0
 i為偶數(shù)
  ai|R|i = aiRi
 所以先將N寫成正權(quán)形式，然后再修改為負(fù)權(quán)的

 同理
 N < 0
 N = -(an|R|^n + ... + a0|R|^0) R < 0
 i為奇數(shù)時(shí):
   -ai|R|i = aiRi         為了保證a'>=0
 i為偶數(shù)
  -ai|R|i = R(i+1) + (|R|-ai)Ri

 最后對(duì)a'[]進(jìn)行修正，使得0 <= a'i < |R|

 感覺挺不錯(cuò)的一道題，通過對(duì)正權(quán)的形式，修正為負(fù)權(quán)的
*/