---
title: Codeforce 582 B. Once Again... 解析(思維、DP、LIS、矩陣冪)
description: "Codeforce 582 B. Once Again... 解析(思維、DP、LIS、矩陣冪)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 582 B. Once Again... 解析(思維、DP、LIS、矩陣冪)">
<!-- toc -->
# Codeforce 582 B. Once Again... 解析(思維、DP、LIS、矩陣冪)
今天我們來看看CF582B
[題目連結](https://codeforces.com/problemset/problem/582/B)
> **題目**
給你一個長度為$n$的數列$a$，求$a$循環$T$次以後的最大遞增子序列(LIS)。$n\le100,T\le10^7$
### 前言
這題實在是搞了非常非常久，經驗過於不足，無論是矩陣快速冪的奇怪$dp$式或者是偏思維作法，都搞不太出來
<div class="VVVcopyrightAAA";>@copyright petjelinux 版權所有<br>
<a href="https://www.cnblogs.com/petjelinux/">觀看更多正版原始文章請至petjelinux的blog</a></div>
### 想法
首先，要來講一下$LIS$的作法:
1. $dp:$ 我們維護以第$i$個元素為結尾的$LIS$長度為$dp[i]$，轉移式$:dp[i]=\max\limits_{j=0,a[j]\le a[i]}^n\{dp[i],dp[j]+1\}$ 且要考慮$LIS$只有單一個元素時長度為1，所以$dp[i]$有個最小值$1$。
複雜度:$O(n^2)$
2. 二分搜$:$ 我們維護一個$stack$，且每次加入一個元素考慮$LIS$。$stack$頂端放目前維護的$LIS$的最後一個元素，如果新元素$\ge$頂端的元素，那就加入。如果新元素$<$頂端的元素，那麼我們可以二分搜目前維護的$LIS$中第一個大於新元素的元素，並且替換為新元素，如此一來，因為我們換了一個比較小的元素上去，且不影響**目前的**$LIS$長度，因此整個$stack$在之後能獲得更好的遞增子序列的「**潛力**」就變高了。**非常建議直接看code思考為什麼這樣做**
複雜度:$O(n\lg(n))$
```c++=
int LIS(){
int sta[_n*_n],top=0;
sta[top++]=a[0];
rep(i,1,nn){
if(a[i]>=sta[top-1])sta[top++]=a[i];
else *upper_bound(sta,sta+top,a[i])=a[i];
}
return top;
}
```
回歸正題，這題有兩種做法，偏思維作法或者是奇怪$dp$式做法。
1. 偏思維作法
畢竟循環($T$)太長了，而$n$又很小，所以自然地感覺應該會用到經典的$LIS$(最大遞增子序列)問題再加上一些觀察。
注意到，最慢最慢在數列$a$循環$n$次以後，$LIS$會重複某個字元。也就是如果每次循環我們都取一個相異的元素，那麼$n$次循環以後就不可能再取到相異的元素了。而因此，我們會想要去維護長度為$n^2$的$LIS$(如果$T>n$)。
現在，如果$T\le n$，那麼我們只要暴力算出$LIS$就行，畢竟$n$很小。
如果$T>n$，觀察到，因為$T>n$，所以我們可以想像得出，整串$LIS$一定有非常多重複的數字，整串$LIS$會先遞增，然後到某個數字開始重複，接著在尾端繼續遞增。
那麼我們只要先算出數列$a$中最多重複出現幾次同樣的數字，並且算出長度$n^2$的$LIS$以後，由於我們知道當$T>n$時，至少會有$T-n$次$a$數列的循環會貢獻給$LIS$同樣的數字，因此，解答就是:$LIS(長度n^2的)+(T-n)\times(出現次數最多的數字)$。([想法來源](https://blog.csdn.net/weixin_42102584/article/details/88607337?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-6.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-6.channel_param))
還有另一個可能會想到的作法，但是複雜度會高一些，直接放[連結](https://blog.csdn.net/mengxiang000000/article/details/53204591?utm_medium=distribute.pc_relevant.none-task-blog-title-1&spm=1001.2101.3001.4242)
2. 奇怪$dp$式做法:
其實這個做法是矩陣快速冪，但我不知道為什麼想得到這種狀態
考慮$dp$狀態: $dp[i][j]$表示「目前為止考慮過的循環節」(考慮過幾個循環節並沒有在狀態中)的，開頭元素$\ge a[i]$且結尾為最後一個循環的第$j$個元素的$LIS$長度。
而會有一個轉移式$:dp_{p+q}[i][j]=\max\limits_{k=0}^n\{dp_p[i][k]+dp_q[k][j]\}$(就是把兩個對於(不/相)同長度循環節的$LIS$接起來)
其中$dp_p$表示目前這個$dp$狀態考慮的數列長度是$p\times n$(也就是$p$個循環節)
我們想要求的是$dp_{nT}$，而我們可以用樸素的$dp$算法($O(n^2)$的方法)來算出$dp_1$。
把$dp[][]$看成是矩陣，而一次轉移看成是一次矩陣乘法，那麼就可以用矩陣快速冪算出來了。
要注意如果在算$dp[i][j]$時如果$a[i]>a[j]$代表這種可能不可能發生，要給一個極小值。
複雜度:偏思維作法中較慢的$:O(n^4)$、偏思維作法中較快的想法但是沒用二分搜$LIS:O(n^4)$、矩陣快速冪$:O(n^3\lg(T))$、偏思維作法中較快的想法且有用二分搜$:O(n^2\lg(n^2))$
### 程式碼(偏思維作法中較慢的):
```cpp=
const int _n=110;
int tt,a[_n*_n],st[_n*_n],ed[_n*_n],num[310];
ll n,nn,t;
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>t;rep(i,0,n){cin>>a[i];num[a[i]]++;} nn=min(n*n,n*t);
rep(i,n,nn)a[i]=a[i%n];
rep(i,0,nn){ed[i]=1;{rep(j,0,i)if(a[j]<=a[i])ed[i]=max(ed[i],ed[j]+1);}}
per(i,0,nn){st[i]=1;{per(j,i+1,nn)if(a[j]>=a[i])st[i]=max(st[i],st[j]+1);}}
int maxx=-1;
if(t<n)rep(i,0,nn)maxx=max(maxx,ed[i]);
else rep(i,0,nn)maxx=max(maxx,ed[i]+st[i]-1+num[a[i]]*(t-n));
cout<<maxx<<'\n';
return 0;
}
```
標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/582/submission/91455635)
### 程式碼(偏思維作法中較快的想法但是沒用二分搜):
```cpp=
const int _n=110;
int tt,a[_n*_n],dp[_n*_n],num[310];
ll n,nn,t,k;
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>t;rep(i,0,n){cin>>a[i];num[a[i]]++;k=max(k,num[a[i]]);}
nn=min(n*n,n*t);
rep(i,n,nn)a[i]=a[i%n]; dp[0]=1;
rep(i,1,nn){
dp[i]=1;
rep(j,0,i)if(a[j]<=a[i])dp[i]=max(dp[i],dp[j]+1);
}
if(t>n){
int ans=k*(t-n);
int maxx=0;rep(i,0,nn)maxx=max(maxx,dp[i]);
ans+=maxx;
cout<<ans<<'\n';
}else{
int maxx=0;rep(i,0,nn)maxx=max(maxx,dp[i]);
cout<<maxx<<'\n';
}
return 0;
}
```
標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/582/submission/91473424)
### 程式碼(矩陣快速冪):
```cpp=
const int _n=110;
int t,n,a[_n];
struct mat{
int a[_n][_n];
mat(){memset(a,0,sizeof a);}
mat operator*(const mat& rhs)const{
mat res;
rep(i,0,n)rep(j,0,n){
res.a[i][j]=-1e5;
rep(k,0,n)res.a[i][j]=max(res.a[i][j],a[i][k]+rhs.a[k][j]);
}
return res;
}
mat operator^(int b){
mat res,tmp=*this;
while(b){
if(b&1)res=res*tmp;
b>>=1;tmp=tmp*tmp;
}
return res;
}
};
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>t;rep(i,0,n)cin>>a[i]; mat ans;
rep(i,0,n)rep(j,0,n){
if(a[i]>a[j]){ans.a[i][j]=-1e5;continue;}
ans.a[i][j]=1;
rep(k,0,j)if(a[k]<=a[j])ans.a[i][j]=max(ans.a[i][j],ans.a[i][k]+1);
}ans=ans^t;
int maxx=0;rep(i,0,n)rep(j,0,n)maxx=max(maxx,ans.a[i][j]);
cout<<maxx<<'\n';
return 0;
}
```
標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/582/submission/91469857)
### 程式碼(偏思維作法中較快的想法且有用二分搜):
```cpp=
const int _n=110;
int tt,a[_n*_n],num[310];
ll n,nn,t,k;
int LIS(){
int sta[_n*_n],top=0;
sta[top++]=a[0];
rep(i,1,nn){
if(a[i]>=sta[top-1])sta[top++]=a[i];
else *upper_bound(sta,sta+top,a[i])=a[i];
}
return top;
}
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>t;rep(i,0,n){cin>>a[i];num[a[i]]++;k=max(k,num[a[i]]);}
nn=min(n*n,n*t);
rep(i,n,nn)a[i]=a[i%n];
if(t>n){
int ans=k*(t-n);
ans+=LIS();
cout<<ans<<'\n';
}else cout<<LIS()<<'\n';
return 0;
}
```
標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/582/submission/91473830)
Sign in with Wallet
Connect another wallet