http://www.lydsy.com/JudgeOnline/problem.php?id=2323 根本想不到... 方法： get(i,j)表示第i到j個數字拼起來組成的數字ans[i][0/1]表示第一次分裂中，第i個數字之後斷開，前i個數字第二次分裂後形成的最後一個二次分裂體否/是與其之 ...
http://www.lydsy.com/JudgeOnline/problem.php?id=2323
根本想不到...
方法：
get(i,j)表示第i到j個數字拼起來組成的數字
ans[i][0/1]表示第一次分裂中，第i個數字之後斷開，前i個數字第二次分裂後形成的最後一個二次分裂體否/是與其之後的二次體相切的總方案數
fib[i]表示斐波那契數列的第i項（令fib[0]=1,fib[1]=0）
ans[i][0]=sum{ans[i-j][0]*fib[get(i-j+1,i)]}+sum{ans[i-j][1]*fib[get(i-j+1,i)+1]}，1<=j<=i
ans[i][1]=sum{ans[i-j][0]*fib[get(i-j+1,i)+1]}+sum{ans[i-j][1]*fib[get(i-j+1,i)+2]}，1<=j<=i
解釋：
很容易可以看出，只要第一步、第二步中任何一步有至少一處劃分方法不一樣，那麼就是不同的方案。
（可以說這道題里不用關心去重的問題）
首先確定對於已確定數量（n個）的一些二次分裂體，如何得到其合併方案數f1(n)。
可以得到f1(n)=fib[n]，解釋
（當然像我這種蒟蒻就只能用n^2的演算法打打表找找規律什麼的，這個演算法就是對於每個n枚舉最後一段長度，不過這一步不是題目的重點，找規律也是可以的..吧）
然後確定ans數組的計算方式。（這個ans數組的第二維設計很有意思，根本想不到）
假設現在要求ans[i][1]。那麼首先可以枚舉從最後切下j個數字，作為一個一次分裂體。這個一次體分裂後形成get(i-j+1,i)個二次體。
那麼，由於第二維是1，這些二次體要求與第i個之後的數字形成的第一個二次體相切。
現在，這些二次體與第i-j+1個之前的數字形成的最後一個二次體可能有兩種關係：相切或者不相切。
如果相切，那麼這一小段的情況總數，相當於get(i-j+1,i)+2個二次體合併的方案數，就是fib[get(i-j+1,i)+2]
（讓這一段所含的get(i-j+1,i)個和兩端2個合併，則恰好兩端一定會都與中間get(i-j+1,i)個相切，因此可以這樣算）
而這一段數字的情況與之前段數字的情況都是獨立、互不影響的，因此這一種情況產生的貢獻是ans[i-j][1]*fib[get(i-j+1,i)+2]
同理，如果不相切，產生的貢獻是ans[i-j][0]*fib[get(i-j+1,i)+1]
最終的方案數是以上兩種情況產生的方案相加。
同理可得到求ans[i][0]時的轉移方程。
註意初值是ans[0][0]=1,ans[0][1]=0
優化：
斐波那契數列的計算可以用矩陣快速冪優化。
當然，如果直接按照這個去打高精+矩陣快速冪只能得到60分
（當然像我一樣明明有了優化策略然而複雜度亂來也可以得到60分）
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 typedef long long LL; 6 const LL md=1000000007; 7 LL n,a[100010]; 8 struct Mat 9 { 10 LL dat[3][3],x,y; 11 Mat(LL x=0,LL y=0):x(x),y(y){memset(dat,0,sizeof(dat));} 12 Mat operator*(const Mat& b) 13 { 14 Mat temp; 15 LL i,j,k; 16 for(i=1;i<=x;i++) 17 for(j=1;j<=b.y;j++) 18 for(k=1;k<=y;k++) 19 temp.dat[i][j]=(dat[i][k]*b.dat[k][j]+temp.dat[i][j])%md; 20 temp.x=x; 21 temp.y=b.y; 22 return temp; 23 } 24 Mat& operator*=(const Mat& b) 25 { 26 return (*this)=(*this)*b; 27 } 28 Mat& operator=(const Mat& b) 29 { 30 memcpy(dat,b.dat,sizeof(dat)); 31 x=b.x;y=b.y; 32 return *this; 33 } 34 }o,s,s2; 35 Mat px10[1001]; 36 Mat pow(const Mat& a,LL b) 37 { 38 Mat ans=o; 39 if(b==0) return ans; 40 Mat base=a; 41 while(b!=0) 42 { 43 if(b&1) ans*=base; 44 base*=base; 45 b>>=1; 46 } 47 return ans; 48 } 49 Mat mulx(LL l,LL r) 50 { 51 Mat ans=o; 52 for(LL i=0;r>=l;r--,i++) 53 { 54 ans*=pow(px10[i],a[r]); 55 } 56 return ans; 57 } 58 LL ans[1010][1010]; 59 int main() 60 { 61 LL i,j;Mat tmp; 62 o.x=o.y=2;o.dat[1][1]=o.dat[2][2]=1; 63 s.x=s.y=2;s.dat[1][2]=s.dat[2][1]=s.dat[2][2]=1; 64 s2.x=1;s2.y=2;s2.dat[1][1]=1; 65 px10[0]=s; 66 for(i=1;i<=1000;i++) px10[i]=pow(px10[i-1],10); 67 //ans[i]->fib[i] 68 //fib[0]=1,fib[1]=0; 69 scanf("%lld",&n); 70 for(i=1;i<=n;i++) scanf("%1lld",&a[i]); 71 ans[0][0]=1; 72 for(i=1;i<=n;i++) 73 for(j=1;j<=i;j++) 74 { 75 tmp=s2*mulx(i-j+1,i); 76 ans[i][0]=(ans[i][0]+ans[i-j][0]*tmp.dat[1][1])%md; 77 ans[i][0]=(ans[i][0]+ans[i-j][1]*tmp.dat[1][2])%md; 78 ans[i][1]=(ans[i][1]+ans[i-j][0]*tmp.dat[1][2])%md; 79 ans[i][1]=(ans[i][1]+ans[i-j][1]*(tmp*s).dat[1][2])%md; 80 } 81 printf("%lld",ans[n][0]); 82 return 0; 83 }View Code
可以發現，在斐波那契數列的計算中出現大量形如
$s^{一個十進位高精度整數}$
$=s^{10^0*x[r]+10^1*x[r-1]+...+10^{r-l}*x[l]}$
的計算（s表示轉移矩陣，l、r表示要算第l到r個數字）。（以下均省略取模）
那麼可以拆成${(s^{10^0})}^{x[r]}*{(s^{10^1})}^{x[r-1]}*...*{(s^{10^{r-l}})}^{x[l]}$。
可以令$px10[i]=s^{10^i}$，並用遞推（$px10[i]=px10[i-1]^{10}$）預處理出來。
然後就可以拆成$px10[0]^{x[r]}*px10[1]^{x[r-1]}*...px10[r-l]^{x[l]}$。
對於每一個l和r，這個式子可以在O(n)時間計算完成（矩陣大小是常數，因此矩陣乘法複雜度是常數）。這樣也是60分。
令$f2(l,r)=px10[0]^{x[r]}*px10[1]^{x[r-1]}*...px10[r-l]^{x[l]}$，可以發現存在遞推關係：
$f2(l,r)=f2(l+1,r)*px10[r-l]^{a[l]}$
因此可以一開始預處理出所有f2(l,r)，然後需要時直接調用而不是重新計算。這樣就得到了複雜度為O(n^2)的演算法。
附：對於此類將序列分段，要dp的題目，有的時候dp的狀態不能是位置+段數，難以決定的時候，可能要從某一段的兩端的狀態/與這一段旁邊段的聯繫著手，
1 #pragma GCC optimize(3) 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long LL; 7 const LL md=1000000007; 8 LL n,a[1010]; 9 struct Mat 10 { 11 LL dat[3][3],x,y; 12 Mat(LL x=0,LL y=0):x(x),y(y){memset(dat,0,sizeof(dat));} 13 Mat operator*(const Mat& b) 14 { 15 Mat temp; 16 LL i,j,k; 17 for(i=1;i<=x;i++) 18 for(j=1;j<=b.y;j++) 19 for(k=1;k<=y;k++) 20 temp.dat[i][j]=(dat[i][k]*b.dat[k][j]+temp.dat[i][j])%md; 21 temp.x=x; 22 temp.y=b.y; 23 return temp; 24 } 25 Mat& operator*=(const Mat& b) 26 { 27 return (*this)=(*this)*b; 28 } 29 Mat& operator=(const Mat& b) 30 { 31 memcpy(dat,b.dat,sizeof(dat)); 32 x=b.x;y=b.y; 33 return *this; 34 } 35 }o,s,s2; 36 Mat px10[1001]; 37 Mat pow(const Mat& a,LL b) 38 { 39 Mat ans=o; 40 if(b==0) return ans; 41 Mat base=a; 42 while(b!=0) 43 { 44 if(b&1) ans*=base; 45 base*=base; 46 b>>=1; 47 } 48 return ans; 49 } 50 Mat mulx[1010][1010]; 51 LL ans[1010][1010]; 52 int main() 53 { 54 LL i,j,l,r;Mat tmp; 55 o.x=o.y=2;o.dat[1][1]=o.dat[2][2]=1; 56 s.x=s.y=2;s.dat[1][2]=s.dat[2][1]=s.dat[2][2]=1; 57 s2.x=1;s2.y=2;s2.dat[1][1]=1; 58 px10[0]=s; 59 for(i=1;i<=1000;i++) px10[i]=pow(px10[i-1],10); 60 scanf("%lld",&n); 61 for(i=1;i<=n;i++) scanf("%1lld",&a[i]); 62 for(r=1;r<=n;r++) 63 { 64 mulx[r][r]=pow(px10[0],a[r]); 65 for(l=r-1;l>=1;l--) 66 mulx[l][r]=mulx[l+1][r]*pow(px10[r-l],a[l]); 67 } 68 ans[0][0]=1; 69 for(i=1;i<=n;i++) 70 for(j=1;j<=i;j++) 71 { 72 tmp=s2*mulx[i-j+1][i]; 73 ans[i][0]=(ans[i][0]+ans[i-j][0]*tmp.dat[1][1])%md; 74 ans[i][0]=(ans[i][0]+ans[i-j][1]*tmp.dat[1][2])%md; 75 ans[i][1]=(ans[i][1]+ans[i-j][0]*tmp.dat[1][2])%md; 76 ans[i][1]=(ans[i][1]+ans[i-j][1]*(tmp*s).dat[1][2])%md; 77 } 78 printf("%lld",ans[n][0]); 79 return 0; 80 }
