byd 谁想做课件啊，byd 我还有一堆东西没学，byd 难过了。
读者记得提醒笔者这里面应当含有 dp 套 dp 和耳分解内容。
本文源码中含有一些 <span title="">，读者如果感兴趣可以自行找出受影响文字的位置。
谁想接 DP（一）讲啊/ng，等我把找的题整完了再继续树形 DP 吧。
在开始之前，先来做一道题。
P11256 [GDKOI2023 普及组] 置换
link。
为什么非要放 link 啊...
对于排列 \(P=\{p_1, p_2, ..., p_n\}\) 和排列 \(Q=\{q_1, q_2, ..., q_n\}\), 定义这两个排列的乘积:
\[P \times Q = \{q_{p1} , q_{p2} , ..., q_{pn} \} \]而排列 \(X\) 的 \(k\) 次幂 \(X^k\) 为 \(k\) 个排列 \(X\) 的乘积，现在考虑给定排列 \(Y\) 和正整数 \(k\), 求满足方程 \(X^k = Y\) 的排列 \(X\) 的数量，对 \(998244353\) 取模。
\(1 \le n \le 3000, 1 \le k \le 10^6, 1 \le T \le 10\)。
先做做吧，别着急看题解。
首先你搞懂置换是什么了吗？以防你读错题，你可以先列一列 \(X^k\) 到底是什么。
对照一下吧。
$X^k$ 是啥
对于第 \(i\) 个位置的数，是 \(p_{p_{\cdots_{p_i}}}\)，省略号加上旁边的 \(p\) 一共 \(k\) 个。
然后你再做做。
Hint
注意连出的环在 \(k\) 次幂中间的变化。
Solution
有人用了上面的提示爆掉了数据范围吗？如果有的话，你可以开写了，下面的 sol 大概对你没有什么帮助。
首先你需要知道，如果我们探讨的是 \(X \to X^k\)，那么任何长度为 \(l\) 的环全部会分解成 \(\gcd(l,k)\) 个相同长度的环。这个是容易理解的，因为你在新环上走一步相当于你在旧环上走了 \(k\) 步，假设环有编号，初始点为 \(0\)，这个时候你能走到的位置就只能是编号为 \(\gcd(l,k)\) 倍数的点。
而我们是在探讨 \(X^k\to X\)，相当于我们要干的事情是把被分解的环拼回去。显然只有长度相等的环才能拼在一起，然后还需要满足拼的个数就是拼起来环长和 \(k\) 的 \(\gcd\)，这个判一下就行了。
所以我们对于每个环长做一遍背包，然后 \(a\) 个长为 \(x\) 的环拼起来的贡献是 \((a-1)!x^{a-1}\)，相当于钦定第一个环，枚举后面的顺序，然后枚举后面用哪个起始。
注意转移系数有一个组合数。不难发现该 DP 最劣 \(O(n^2)\)，足以通过。
高明人士可以上生成函数推导，得到一个可以使用多项式优化的解法，应该足以通过 P4709。
还有高明做法都去 P4709 题解区看吧，比如说还有什么转移个数其实较少。
Code
钦定 __gcd 复杂度为 \(O(1)\)。
#include<bits/stdc++.h>
using namespace std;
int n,k;
const int M=3005;
int a[M],F[M][M];
bool vis[M];
int f[M],fac[M],ifac[M];
int lenc[M],ans;
const int mod=998244353;
inline void R(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
return;
}
#define ll long long
ll ksm(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
return res;
}
inline int C(int a,int b){return a<b?0:1ll*fac[a]*ifac[b]%mod*ifac[a-b]%mod;}
inline void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i],vis[i]=0,lenc[i]=0;
for(int cnt,nw,i=1;i<=n;i++)if(!vis[i]){
nw=i;
cnt=0;
do{
vis[nw]=1;
cnt++;
nw=a[nw];
}while(nw!=i);
lenc[cnt]++;
}
ans=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=lenc[i];j++)f[j]=0;
f[0]=1;
for(int j=1;j<=lenc[i];j++){
for(int o=1;o<=j;o++){
if(k%o==0&&__gcd(k/o,i)==1)R(f[j],1ll*f[j-o]*fac[o-1]%mod*C(j-1,o-1)%mod*F[i][o-1]%mod);
}
}
ans=1ll*ans*f[lenc[i]]%mod;
}
cout<<ans<<"\n";
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
fac[0]=1;
for(int i=1;i<=3000;i++)fac[i]=1ll*i*fac[i-1]%mod;
ifac[3000]=ksm(fac[3000],mod-2);
for(int i=2999;i>=0;i--)ifac[i]=1ll*(i+1)*ifac[i+1]%mod;
for(int i=1;i<=3000;i++){
F[i][0]=1;
for(int j=1;j<=3000;j++)F[i][j]=1ll*i*F[i][j-1]%mod;
}
while(T--)solve();
return 0;
}
如果你做出来这个题那你其实已经很牛了，这个博客可能你能收获的不大，因为题都是乱选的。
接下来就是正文了。
连续段 DP
如果你认为你很喜欢锤子的话，你可以把这个 DP 叫做锤子 DP。
这种 DP 大概就是把目前已经填了的序列的连续段的个数塞进状态里面转移。
已经会了的可以跳过。
P5999 [CEOI2016] kangaroo
link。
有一个园子，里面有 \(n\) 个草丛排成一排，标号 \(1\sim n\)，有一个袋鼠，从 \(s\) 出发，每次跳一步跳到一个其他的草丛，经过每个草丛恰好一次，最终到达 \(t\)。显然他会跳跃 \(n-1\) 次。为了不被人类发现，袋鼠每次跳跃的方向必须与前一次不同。
具体地，如果他现在在 \(now\)，他是从 $prev $ 跳跃一次到达 \(now\) 的，然后他跳跃一次到达 \(next\)：
- 那么如果 \(prev<now\)，就必须有 \(next<now\)；
- 如果 \(now<prev\)，就必须有 \(now<next\)。
问从 \(s\) 到 \(t\) 的方案数模 \(10^9+7\) 的结果。
两个路线不同，当且仅当草丛被访问的顺序不同。
保证至少有一种方案，初始时可以往任意方向跳。
\(1\leq n\leq 2\times 10^3\)。
如果你有线性做法，那你就太牛了。
Solution
连续段 DP 也需要考虑在哪个序列上面 DP，比如说这个题，你如果在 是否跳跃过的序列上 DP，那你需要考虑 \(s\) 和 \(t\) 在最后合并的时候左右两边个数正确，显然没法做。
所以考虑把位置编号填进 跳跃经过的点编号序列中，这个时候我们要满足一个元素一定同时大于或同时小于左右相邻元素。
考虑编号顺序加入，我们探讨几个操作。
加入一段，显然是可以的，但是需要注意 \(s\) 必然在开头，\(t\) 必然在结尾，转移 \(s\) 或 \(t\) 后，就少一个位置能插一段。
接在一段后面，显然不满足性质。
将两段拼起来，也是可以的。
\(s\) 和 \(t\) 特殊转移，然后就做完了。
Code
#include<bits/stdc++.h>
using namespace std;
const int M=2005;
int dp[M][M];
int n,s,t;
const int mod=1e9+7;
inline void R(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>s>>t;
dp[1][1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
if(i!=s&&i!=t){
R(dp[i][j],1ll*j*dp[i-1][j+1]%mod);
R(dp[i][j],1ll*(j-(i>s)-(i>t))*dp[i-1][j-1]%mod);
}else R(dp[i][j],dp[i-1][j]),R(dp[i][j],dp[i-1][j-1]);
}
}
cout<<dp[n][1];
return 0;
}
P7967 [COCI2021-2022#2] Magneti
link。
给定 \(n\) 个磁铁和 \(l\) 个空位，其中相邻空位之间的距离为 \(1\)，每个空位可放置一个磁铁。所有 \(n\) 个磁铁都必须被放置。每个磁铁可以吸引距离小于 \(r_i\) 的其它磁铁。
求所有磁铁互不吸引的方案总数对 \(10^9+7\) 取模的结果。
\(1 \le n \le 50\)，\(n \le l \le 10000\)，\(1 \le r_i \le l\)。
别着急翻题解，尽量自己想想，如果记录某个连续段不行就换一个记。
Solution
如果你把限制变成磁铁中间还能不能再放磁铁，那你怎么做也做不出来。
考虑 DP 某种顺序下磁铁挤满剩下的空间，对其大小计数。这个时候连续段 DP 显然，按照 \(r_i\) 升序排然后直接 DP 讨论情况即可。
最后插板一下统计贡献即可。时间复杂度 \(O(n^2l)\)。
Code
#include<bits/stdc++.h>
using namespace std;
int dp[55][55][30005];
const int mod=1e9+7;
inline void R(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
return;
}
inline int _(int x,int y){
x-=y;
if(x<0)x+=mod;
return x;
}
#define ll long long
int r[55],fac[20005],ifac[20005];
inline ll ksm(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
return res;
}
inline int C(int a,int b){return a<b?0:1ll*fac[a]*ifac[b]%mod*ifac[a-b]%mod;}
int _0;
int n,l;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>l;
fac[0]=1;
for(int i=1;i<=l+l;i++)fac[i]=1ll*i*fac[i-1]%mod;
ifac[l+l]=ksm(fac[l+l],mod-2);
for(int i=l+l-1;i>=0;i--)ifac[i]=1ll*(i+1)*ifac[i+1]%mod;
for(int i=1;i<=n;i++)cin>>r[i];
sort(r+1,r+n+1);
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
for(int k=0;k<=l;k++){
R(dp[i][j][k+1],dp[i-1][j-1][k]);
R(dp[i][j][k+r[i]],2ll*j*dp[i-1][j][k]%mod);
R(dp[i][j][k+2*r[i]-1],1ll*(j+1)*(j)*dp[i-1][j+1][k]%mod);
}
}
}
int ans=0;
for(int i=0;i<=l;i++){
R(ans,1ll*C(l-i+n,n)*dp[n][1][i]%mod);
}
cout<<ans;
return 0;
}
Subsequence
以下的内容可能都没啥营养。
我在 AT 上面找了标题中有某特定串的题目，还有一些无意间找到的相关的题，几乎全部放进来了。
难度乱序，没有 Hint，大家适当 跳过 完成。
[ABC299F] Square Subsequence
link。
给定一个由小写英文字母组成的字符串 \(S\)。计算满足以下条件的非空字符串 \(T\) 的数量，答案对 \(998244353\) 取模。
将 \(T\) 复制一倍形成 \(TT\)，则 \(TT\) 是 \(S\) 的子序列（不一定连续）。
\(1\leq |S|\leq 100\)。
ABC 的 F，你猜有多难。
Solution
没多难。
建出子序列自动机，然后每次钦定开头和某个起始点，计数从这两个状态开始到某两个状态有多少个合法匹配，容易直接 DP。每次只加入结束点在钦定的第二个起始点的所有贡献。
显然没有重复，时间复杂度 \(O(n^3|\Sigma|)\)。
Code
#include<bits/stdc++.h>
using namespace std;
string s;
int n;
const int M=105;
const int mod=998244353;
int to[M][26],pre[26];
int f[M][M];
inline void R(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>s;
n=s.size();
s=" "+s;
for(int i=1;i<=n;i++){
for(int j=pre[s[i]-'a'];j<i;j++)to[j][s[i]-'a']=i;
pre[s[i]-'a']=i;
}
int ans=0;
for(int j=1;j<=n;j++){
memset(f,0,sizeof f);
f[0][j-1]=1;
for(int k=0;k<j;k++){
for(int o=j-1;o<=n;o++){
for(int i=0;i<26;i++){
R(f[to[k][i]][to[o][i]],f[k][o]);
}
}
}
for(int o=j;o<=n;o++)R(ans,f[j-1][o]);
}
cout<<ans;
return 0;
}
[ARC180C] Subsequence and Prefix Sum
link。
给你一个长度为 \(N\) 的序列 \(A\)，你需要选出 \(A\) 的恰好一个非空子序列，然后将这一子序列替换为其前缀和。求能得到多少种本质不同的序列，对 \(10^9+7\) 取模。
\(1\le N\le 100\)，\(-10\le A_i\le 10\)。
Hanghang 场切了然后上大分/bx。
Solution
我觉得有点难说实话。
考虑相较于直接 DP，什么时候会算重，发现如果前面选的子序列的和是 \(0\)，那么选择下一次是不变的，选择下两次也会受到限制。
那么考虑转移非 \(0\) 的值直接转移，然后转移 \(0\) 的值就枚举转移到下两次上，时间复杂度 \(O(n^2|V|)\)。
Code
#include<bits/stdc++.h>
using namespace std;
const int M=105,mod=1e9+7;
int n,a[M];
int F[M][M*40],G[M*40];
inline auto& f(int pos,int val){return F[pos][val+M*20];}
inline auto& g(int val){return G[val+M*20];}
inline void R(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
return;
}
#define ll long long
inline ll ksm(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
return res;
}
bool vis[M];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
f(0,0)=1;
for(int i=0;i<=n;i++){
for(int j=-i*10;j<=i*10;j++)if(j!=a[i])R(f(i,j),g(j-a[i]));
for(int j=-i*10;j<=i*10;j++)R(g(j),f(i,j));
memset(vis,0,sizeof vis);
vis[10]=1;
for(int j=i+1;j<=n;j++){
for(int k=0;k<=20;k++)if(k!=10&&vis[k])R(f(j,a[j]+k-10),f(i,0));
if(!vis[a[j]+10])vis[a[j]+10]=1;
}
}
int ans=0;
for(int j=-n*10;j<=n*10;j++)R(ans,g(j));
cout<<ans;
return 0;
}
[ARC150F] Constant Sum Subsequence
link。
有一个长度为 \(n^2\) 的序列 \(\{ a_i \}\) 以及一个整数 \(sum\)。
对于 \(\forall i\in[1,n^2-n]\)，这个序列满足 \(a_i=a_{i+n}\)，在本题中只给出 \(n\) 个数 \(\{ a_1,\dots,a_n\}\)。
现在要求你找到一个最小的整数 \(p\)，使得所有满足 \(\sum_{i} b_i=sum\) 的序列 \(\{b_i\}\) 是 \(\{a_1,\dots,a_p\}\) 的子序列。
$ 1\leq N\leq 1.5\times 10^6, 1\leq S\leq \min(N,2 \times 10^5) ,1 \leq A_i \leq S $。
Solution 1
从答案上考虑，设 \(f_i\) 表示和为 \(i\) 的所有序列在 \(f_i\) 位置前面的序列中均以子序列的形式出现过。
则我们有转移：
\[f_i=\max_{j<i}(\operatorname{next}(f_j+1,i-j)) \]意义显然，就是想要在后面拼一个 \(i-j\)。注意 \(\operatorname{next}\) 是把起始位置含在内的，\(\operatorname{last}\) 也是。
我们只知道 \(f\) 是单增的，但是似乎并不满足决策单调性。
如果你观察力够强，你可以考虑分治优化。每次考虑一个整体转移到另外一个整体。
考虑若 \(\operatorname{next}(f_i,k)<\operatorname{next}(f_j,k)\)，那么一定有 \(\operatorname{next}(f_i,k)<j\)，因为一定有 \(\operatorname{next}(f_i,k)\leq\operatorname{last}(f_j-1,k)\)。那么转移到的 \(i+k\) 位置一定不如从 \(j\) 转移而来。
所以我们分治每次枚举 \(k\)，然后只用转移 \(\operatorname{next}(f_i,k)=\operatorname{next}(f_{mid},k)\) 的 \(i\)，转移到的显然是一个区间，而 \(f\) 单增，所以相当于是一个后缀取 \(\max\)，可以简单维护。
显然相等的 \(\operatorname{next}\) 是可以直接 set \(O(\log n)\) 求，那么问题就以 \(O(S\log S\log n+n\log n)\) 的复杂度解决了。
Solution 2
换个角度，在序列角度上考虑。
我们在 \(f_i\to f_{i+1}\) 的过程中考虑扩展。
扩展的话，我们一定是考虑把没有满足的拼接给整满足了。
设 \(g_i\) 表示 \(i\) 位置及之前的序列最多能满足和为多少的序列全部出现。这个单次询问就二分所在 \(f\) 的位置做到 \(O(\log S)\) 查询。
考虑我们如果扩展到的东西合法，那么我们需要让所有的 \(g_{\operatorname{last}(now,j)-1}+j\geq v\)，其中 \(v\) 是下一个和。
使用小根堆对于每个 \(j\) 维护 \(g_{\operatorname{last}(now,j)-1}+j\)，延时更新，首先先计算出其真实值，若真实值也不合法，那么我们就找到 \(\operatorname{next}(now+1,j)\) 作为目前的 \(now\)，并更新这个 \(j\) 的值为 \(j-1+v\)。重复更新直到最小值合法，这个时候 \(now\) 位置就是 \(f_v\) 的正确值。
考虑证明复杂度，不难发现后面的更新至少加 \(j\)，是调和级数，而前面的更新，在下次不合法时，如果只计算真实值就合法，那么 \(f_{v-1}\) 和 \(f_{v'-1}\) 的真实值就不同，代表其对应 \(\operatorname{last}\) 位置不同，显然有第二次的 \(\operatorname{last}\) 位置在 \(f_{v-1}\) 之后，所以此次更新一定会将值更新到 \(v-1+j\) 以上。两者都是调和级数的。所以总时间复杂度为 \(O(S\ln S\log n)\)。
第一种方法是将限制拍到整体转移中，发现一个整体的转移，实际上只有一部分转移有用。
而这个方法是将相同的限制扩展，然后发现扩展的次数较少。
Code of Sol 2
懒得删注释了。
#include<bits/stdc++.h>
using namespace std;
int n,s;
const int M=1.5e6+5,S=2e5+5;
#define ll long long
set<int> pos[S];
int a[M<<1];
ll f[S];
priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2> > > q;
inline ll find_pre(ll ps,int x){
int st=(ps-1)%n+1+n;
return ((ps-1)/n-1)*n+*(--pos[x].upper_bound(st));
}
inline ll find_nxt(ll ps,int x){
int st=(ps-1)%n+1;
return (ps-1)/n*n+(*pos[x].lower_bound(st));
}
inline int calc(ll ps,int v){
if(ps<0)return -1e9;
int mid,L=0,R=v,res=0;
while(L<=R){
mid=(L+R)>>1;
if(f[mid]<=ps)L=mid+1,res=mid;
else R=mid-1;
}
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>s;
for(int i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];
for(int i=1;i<=n+n;i++)pos[a[i]].insert(i);
for(int i=1;i<=s;i++){
//join i
ll &g=f[i];
g=f[i-1]+1;
ll lst=find_pre(f[i-1]+1,i);
q.push({calc(lst-1,i-1)+i,i});
// cerr<<calc(lst-1,i-1)+i<<" "<<i<<" I\n";
while(q.top()[0]<i){
auto p=q.top();q.pop();
p[0]=calc(find_pre(g,p[1])-1,i-1)+p[1];
if(p[0]>=i){
// cerr<<i<<" "<<p[0]<<" "<<p[1]<<"\n";
q.push(p);
continue;
}
g=find_nxt(g+1,p[1]);
p[0]=i-1+p[1];
// cerr<<p[0]<<" "<<p[1]<<" renew\n";
q.push(p);
}
// cerr<<i<<" "<<g<<"\n";
}
cout<<f[s];
return 0;
}
[ARC138E] Decreasing Subsequence
link。
没有人回复我消息。
给出 \(3\leq N \leq 5000,2\leq K \leq \frac{N+1}{2}\)，对所有长度为 \(N\) 的满足 \(0\leq A_i \leq i\) 且正数项两两不同的序列 \(A\)，求长度为 \(K\) 的元素非 \(0\) 的下降子序列个数之和。
Solution 1
不是 DP 做法。
考虑将所有 \(a_i\) 减一，对于所有非负 \(a_i\) 连边 \(i\to a_i\)。显然我们会得到一个链的集合。
选出子序列合法当且仅当选择了一些直观上有 \(k-1\) 个包含关系的边。枚举这些边左边和右边在相同链上的点集大小，把它们分成 \(k\) 条链，那么中间链的连接是固定的，然后再计算没有被枚举到的点划分成任意链的方案数就做完了。
注意你选出左边和右边大小和的元素之后（左边 \(i\) 个右边 \(j\) 个），这里前 \(i\) 个就一定在左边，后 \(j\) 个数就一定在右边。
设 \(w_{i}\) 为 \(\sum_{1\leq i\leq n}{n\brace i}\)，可以列出答案式子：
\[\sum_{i\geq k,j\geq k}\binom{n+1}{i+j}{i\brace k}{j\brace k}\times w_{n+1-i-j} \]Solution 2
我太菜了，还不会。
大家可以自己看看洛谷第一篇题解，如果会了记得给笔者讲讲。
Code of Sol 1
#include<bits/stdc++.h>
using namespace std;
const int M=5005;
int W[M][M],C[M][M],S[M];
const int mod=1e9+7;
inline int add(int a,int b){
a+=b;
if(a>=mod)a-=mod;
return a;
}
int n,k;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
W[0][0]=1,C[0][0]=1;
for(int i=1;i<=n+1;i++){
C[i][0]=1,W[i][0]=0;
for(int j=1;j<=i;j++){
C[i][j]=add(C[i-1][j-1],C[i-1][j]);
W[i][j]=add(W[i-1][j-1],1ll*j*W[i-1][j]%mod);
}
}
for(int i=0;i<=n+1;i++)for(int j=0;j<=n+1;j++)S[i]=add(S[i],W[i][j]);
int ans=0;
for(int i=k;i<=n;i++)for(int j=k;j<=n;j++){
if(n+1-i-j>=0)ans=add(ans,1ll*C[n+1][i+j]*W[i][k]%mod*W[j][k]%mod*S[n+1-i-j]%mod);
}
cout<<ans;
return 0;
}
[AGC026E] Synchronized Subsequence
link。
有一个长度为 \(2 N\) 的仅由字符 \(\mathtt{a}, \mathtt{b}\) 构成的字符串，且 \(\mathtt{a}\) 的个数恰好等于 \(\mathtt{b}\) 的个数，都出现了 \(N\) 次。
你需要保留一些字符，剩下的字符删掉。对于一个 \(i\)，你可以保留从左往右数的第 \(i\) 个 \(\mathtt{a}\) 和第 \(i\) 个 \(\mathtt{b}\)。
注意，对于这两个字符，只能同时保留或同时删掉，不能只保留其中一个。
请你求出能得到的字典序最大的串。
\(1 \le N \le 3 \times {10}^3\)。
Solution
这个题就看谁敢把字符串作为 DP 答案。
注意到是字典序，如果贪心的话一定是从前往后贪，但是 DP 的话则一定是从后往前 DP，相当于把前面的最优选法和后面的最优选法拼起来。而如果从前往后，就不知道从何开始选择最优。
设 \(f_i\) 为只考虑 \([i,n]\) 号字符对，最大字典序串是什么。对，就是把整个串作为答案。
现在我们只需要考虑如何操作加入的字符对。设 \(a_i\) 为 \(i\) 号字符对中 a 的位置，\(b_i\) 则为 b 的位置，\(rk_i\) 为第一个完全出现在 \(i\) 位置及之后的字符对的编号。
假设 \(a_i<b_i\)，那么在 \((a_i,b_i)\) 区间的 b 一定属于 \(<i\) 号字符对，我们如果要选 \(i\) 号字符对，那么最优情况下一定是这个字符对的 b 在第二个位置。此时有：
\[f_i\gets {\text{ab}}+f_{rk_{b_i+1}} \]然后是 \(a_i>b_i\)，同样的，在中间的 a 一定属于 \(<i\) 号字符对，现在我们考虑中间的 b。显然选择这些 b 是比不选这些 b 优的，所以，如果这里到目前的结尾中间还有没有选的 b，我们就把这个字符对加入并且更新结尾位置，设结尾位置最终为 \(x\)，选择出的子序列构成的串为 \(s\)，有：
\[f_i\gets s+f_{rk_{x+1}} \]最后当然还有 \(f_i\gets f_{i+1}\)，\(f_1\) 就是答案，时间复杂度 \(O(n^2)\)。
Code
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
const int M=3005;
int a[M],b[M],ca,cb;
string f[M];
int rk[M<<1];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
cin>>s;
s=" "+s;
for(int i=1;i<=n+n;i++){
if(s[i]=='a')a[++ca]=i;
else b[++cb]=i;
}
ca=0,cb=0;
for(int i=n+n;i>=1;i--){
if(s[i]=='a')ca++;
else cb++;
rk[i]=n-min(ca,cb)+1;
}
string tmp;
for(int i=n;i>=1;i--){
f[i]=f[i+1];
if(a[i]<b[i]){
tmp="ab"+f[rk[b[i]+1]];
if(f[i]<tmp)f[i]=tmp;
}else{
tmp="";
int r=a[i];
for(int j=b[i],k=i-1;j<=r;j++){
if(s[j]=='b')r=a[++k];
if(s[j]=='a'&&j<a[i])continue;
tmp+=s[j];
}
tmp+=f[rk[r+1]];
if(f[i]<tmp)f[i]=tmp;
}
}
cout<<f[1];
return 0;
}
[AGC024E] Sequence Growing Hard
link。
我觉得大家都能做出来这个题，真的。
给定 \(n\), \(k\), \(m\) , 问有多少个序列组 \((A_0,A_1,\cdots,A_n)\) 满足：序列 \(A_i\) 的元素个数为 \(i\) ; 所有元素都在 \([1,k]\) 内; \(\forall i\in[0,n)\) , \(A_i\) 是 \(A_{i+1}\) 的子序列且 \(A_i\) 的字典序小于 \(A_{i+1}\)。
输出在 \(\bmod m\) 意义下的答案.
\(1\leq n,k\leq 300\)。
这个题是托下一个题的缘分被找到加进来的。
Solution
真的不难。
首先发现 \(A_0=\{0\}\) 对计数没有影响。
考虑某次操作，发现一定是删去一个满足 \(a_i>a_{i+1}\) 的 \(a_i\)。设 \(f_{i,j}\) 为下标为 \(1\sim i\)，\(A_0=\{j\}\) 的序列组的方案数。
枚举 \(A_1\)，发现从此时开始，\(A_1\) 中的 \(a_1\) 和 \(j\) 就没有任何关联，分成了两个子问题，即未知下标范围，最后剩下 \(x\) 的序列组的方案数。我们可以枚举前面操作了多少次，后面操作了多少次，然后用组合数合并起来。具体转移可以看代码。
这样复杂度是 \(O(n^4)\) 的，但是不难发现我们可以每次将 \(>j\) 的所有数一起贡献，相当于做一个后缀和，这样就能优化至 \(O(n^3)\) 了。
Code
#include<bits/stdc++.h>
using namespace std;
int n,k,m;
const int M=305;
int f[M][M];
int g[M][M];
inline void R(int &x,int y){
x+=y;
if(x>=m)x-=m;
return;
}
inline int A(int x,int y){
x+=y;
if(x>=m)x-=m;
return x;
}
int C[305][305];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k>>m;
C[0][0]=1;
for(int i=1;i<=300;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)C[i][j]=A(C[i-1][j-1],C[i-1][j]);
}
for(int i=0;i<=k;i++)f[0][i]=1;
for(int i=k;i>=0;i--)g[0][i]=A(g[0][i+1],f[0][i]);
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
for(int o=0;o<i;o++){
R(f[i][j],1ll*g[o][j+1]*f[i-1-o][j]%m*C[i-1][o]%m);
}
}
for(int j=k;j>=0;j--)g[i][j]=A(g[i][j+1],f[i][j]);
}
cout<<f[n][0];
return 0;
}
[AGC024F] Simple Subsequence Problem
link。
有一个
01串集合 \(S\)，其中每个串的长度都不超过 \(N\)，你要求出至少是 \(S\) 中 \(K\) 个串的子序列的最长串，如果有多解，输出字典序最小的那组解。由于 \(S\) 可能很大，因此我们是这样描述 \(S\) 的：
- 你将得到 \((N+1)\) 个
01串，第 \(i\) 个串的长度为 \(2^{i-1}\)。- 第 \(i\) 个字符串的第 \(j\) 个字符，代表数字 \((j-1)\) 的、长度为 \((i-1)\) 的二进制表示是否出现在 \(S\) 中。
\(0\leq N \leq 20\)。
Solution
首先有一个非常 naive 的想法，就是直接枚举每个子序列去找有多少个原串拥有这样的子序列。
每次找的过程都是一个子序列匹配的过程，因为字符串长度都很小，所以我们可以考虑状压这个匹配的过程尝试做到一个很好的复杂度。
类似子序列自动机的贪心，考虑状压目前匹配到什么串，和还有什么样的没有匹配的串。如果我们枚举目前匹配的长度的话，每次状态数是 \(\sum_{i=k}^N 2^i=O(2^N)\)，所以我们可以直接考虑在这里进行转移。
设 \(f(s|t)\) 为目前匹配了 \(s\)，剩下还有 \(t\) 没有匹配的情况数。
显然有转移：\(f(s+\text{0}|t')\gets f(s|t)\) 和 \(f(s+\text{1}|t'')\gets f(s|t)\)，这两个都可以用位运算 \(O(1)\) 转移。还有贡献答案的转移 \(ans_s\gets f(s|t)\)。
最后枚举 \(2^N\) 个串找到答案即可。总时间复杂度为 \(O(N2^N)\)，注意需要使用正确的状态存储方式。
Code
#include<bits/stdc++.h>
using namespace std;
vector<int> f[25],g[25];
int v[25][1<<20];
int n,K;
string s;
string ans,tmp;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>K;
for(int i=0;i<=n;i++){
cin>>s;
f[i].resize(1<<i);
for(int j=0;j<(1<<i);j++)if(s[j]=='1')f[i][j]=1;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n-i;j++)swap(g[j],f[j]),f[j].clear(),f[j].resize((1<<(i+j+1)));//,cerr<<i<<" "<<g[j].size()<<'\n';
for(int j=0;j<=n-i;j++){
for(int k=0,tp,num,ok,va;k<(1<<(i+j));k++)if(g[j][k]){
va=g[j][k];
// cerr<<i<<" "<<j<<" "<<(bitset<20>)k<<" "<<va<<"\n";
num=(k&((1<<j)-1));
ok=k>>j;
v[i][ok]+=va;
if(num!=0){
tp=__lg(num);
f[tp][(ok<<(tp+1))|num]+=va;
}
if(num!=(1<<j)-1){
tp=__lg(num^((1<<j)-1));
f[tp][(ok<<(tp+1))|(num&((1<<(tp+1))-1))]+=va;
}
}
}
}
for(int i=1;i<=n;i++)for(int j=0;j<(1<<(i));j++)if(v[i][j]>=K){
tmp="";
for(int k=i-1;k>=0;k--)tmp+='0'+((j>>k)&1);
if(ans.empty()||ans>tmp||ans.size()<i)ans=tmp;
}
cout<<ans;
return 0;
}
[JSC2024 Final C] Max of Sum of Prefix Min
link。
回收伏笔（剧透做法警告）。
设 \(f(a)=\sum_i premin_i\)，其中 \(premin\) 是 \(a\) 数组的前缀 \(\min\) 数组。
给定长度为 \(N\) 的序列 \(A\)，你需要将其分为两个子序列 \(X_1,X_2\)（可以为空），使得 \(f(X_1)+f(X_2)\) 最大。
6s。\(1\leq N\leq 5\times 10^5,1\leq A_i\leq 10^9\)。
我是伊娜的粉丝！
Solution
讲个笑话，笔者做的时候不会这个题的 \(O(n^2)\) 做法遗憾离场。
观察过程中两个序列的前缀 \(\min\)，不难发现其中某个子序列的前缀 \(\min\) 是原位置原序列的前缀 \(\min\)。依照这个来转移，设 \(f_{i,j}\) 为 \(i\) 位置，某一个子序列目前的全局 \(\min\) 是 \(premin_i\)，另一个子序列目前的前缀 \(\min\) 是 \(j\) 的最大 \(f\) 和。
然后转移式子中包含了类似区间加，区间加上 \(v_i\)（\(v_i\) 初始的时候已经定下来），区间询问 \(\max\)。这个可以直接 KTT，即递归到阈值大于等于目前要改变的值。当然也能分块凸包（伊娜做法），不过疑似跑的有点慢。
Code
#include<bits/stdc++.h>
using namespace std;
int n;
const int M=5e5+5;
int a[M],pre[M];
int val[M],vcnt;
#define ll long long
#define fi first
#define se second
#define mid ((l+r)>>1)
struct KTT{
struct line{ll k,b;};
inline static pair<line,ll> mer(const line &x,const line &y){
if(x.k==y.k){
if(x.b>y.b)return {x,1e18};
else return {y,1e18};
}
if(x.k>y.k){
if(x.b>=y.b)return {x,1e18};
else return {y,(y.b-x.b)/(x.k-y.k)};
}
if(x.b>y.b)return {x,(x.b-y.b)/(y.k-x.k)};
return {y,1e18};
}
struct node{
line x;ll t;
inline node operator +(const node &y)const{
node res;
auto tmp=mer(x,y.x);
res.t=min({t,y.t,tmp.se});
res.x=tmp.fi;
return res;
}
}xds[M<<2];
ll tg[M<<2],tgb[M<<2];
inline void pushup(int now){
xds[now]=xds[now<<1]+xds[now<<1|1];
return;
}
inline void upd(int now,ll w){
xds[now].t-=w;
xds[now].x.b+=xds[now].x.k*w;
tg[now]+=w;
return;
}
inline void add(int now,ll w){
xds[now].x.b+=w;
tgb[now]+=w;
return;
}
inline void pushdown(int now){
if(tg[now]){
upd(now<<1,tg[now]),upd(now<<1|1,tg[now]);
tg[now]=0;
}
if(tgb[now]){
add(now<<1,tgb[now]),add(now<<1|1,tgb[now]);
tgb[now]=0;
}
return;
}
inline void mdf(int now,int l,int r,int pos,ll v){
if(l==r){
xds[now].x.b=max(xds[now].x.b,v);
return;
}
pushdown(now);
if(pos<=mid)mdf(now<<1,l,mid,pos,v);
else mdf(now<<1|1,mid+1,r,pos,v);
return pushup(now);
}
inline void add(int now,int l,int r,int sl,int sr,ll w){
if(sl<=l&&r<=sr)return add(now,w);
pushdown(now);
if(sl<=mid)add(now<<1,l,mid,sl,sr,w);
if(sr>mid)add(now<<1|1,mid+1,r,sl,sr,w);
return pushup(now);
}
inline void upd(int now,int l,int r,ll w){
if(xds[now].t>=w)return upd(now,w);
pushdown(now);
upd(now<<1,l,mid,w),upd(now<<1|1,mid+1,r,w);
return pushup(now);
}
inline void addv(int now,int l,int r,int sl,int sr,ll w){
if(sl<=l&&r<=sr)return upd(now,l,r,w);
pushdown(now);
if(sl<=mid)addv(now<<1,l,mid,sl,sr,w);
if(sr>mid)addv(now<<1|1,mid+1,r,sl,sr,w);
return pushup(now);
}
inline ll ask(int now,int l,int r,int sl,int sr){
if(sl<=l&&r<=sr)return xds[now].x.b;
pushdown(now);
if(sl>mid)return ask(now<<1|1,mid+1,r,sl,sr);
if(sr<=mid)return ask(now<<1,l,mid,sl,sr);
return max(ask(now<<1,l,mid,sl,sr),ask(now<<1|1,mid+1,r,sl,sr));
}
inline void build(int now,int l,int r){
if(l==r){
xds[now].x.k=val[l];
xds[now].x.b=-1e18;
xds[now].t=1e18;
return;
}
build(now<<1,l,mid),build(now<<1|1,mid+1,r);
return pushup(now);
}
}T;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],val[i]=a[i];
sort(val+1,val+n+1);
vcnt=unique(val+1,val+n+1)-val-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(val+1,val+vcnt+1,a[i])-val;
val[++vcnt]=1e9+1;
T.build(1,1,vcnt);
T.mdf(1,1,n,vcnt,0);
pre[0]=vcnt+1;a[0]=vcnt+1;
for(int i=1;i<=n;i++)pre[i]=min(pre[i-1],a[i]);
ll tmp;
for(int i=1;i<=n;i++){
if(a[i]==pre[i]){
// cerr<<"IN 1"<<'\n';
tmp=T.ask(1,1,vcnt,1,vcnt)+val[a[i]];
// cerr<<tmp<<"\n";
T.add(1,1,vcnt,a[i],vcnt,val[a[i]]);
T.mdf(1,1,vcnt,pre[i-1],tmp);
}else{
// cerr<<"IN 2"<<"\n";
tmp=T.ask(1,1,vcnt,a[i]+1,vcnt)+val[a[i]];
// cerr<<tmp<<"\n";
T.add(1,1,vcnt,a[i]+1,vcnt,val[pre[i]]);
T.addv(1,1,vcnt,1,a[i],1);
T.mdf(1,1,vcnt,a[i],tmp);
}
// cerr<<"nowmax: "<<T.ask(1,1,vcnt,1,vcnt)<<" "<<T.ask(1,1,vcnt,5,5)<<"\n";
}
cout<<T.ask(1,1,vcnt,1,vcnt);
return 0;
}
[ABC349F] Subsequence LCM
link。
又是一个 ABC F 题。
给你一个长度为 \(N\) 的正整数序列 \(A=(A_1,A_2,\dots,A_N)\) 和一个正整数 \(M\) 。求元素的最小公倍数为 \(M\) 的 \(A\) 的非空子序列（不一定连续）的个数。
由于数量可能很大，你只需输出答案模 \(998244353\) 的结果。
注意：内容相同但位置不同的子序列被认为是不同的子序列。
另外，若子序列仅包含一个元素，认为这个子序列的最小公倍数为这个元素本身。
\(1 \leq N \leq 2 \times 10^5,1 \leq M \leq 10^{16},1 \leq A_i \leq 10^{16}\)。
Solution
显然这个 \(N\) 没有用，只有 \(M\) 的因数有用，我们知道 \(\max d_{M}\approx 40000\)，我们之后就可以用这个范围计数。
设 \(f_S\) 为集合 \(S\) 的质数达到 \(M\) 的上界，可以枚举因数 DP。可知 \(|S|\leq 13\)，计算一下，目前复杂度还是有点爆，为 \(O(d(M)2^{|S|})\)，但是显然只有能达到 \(M\) 某个质数的幂的因数才能进入这一步，而因为上界 \(\leq 13\)，所以这里转移数理论上只有 \(O(2^{|S|}\log M)\)，实际上肯定比这个少的多，因为 \(13\) 和 \(\log M\) 分别是两个极限的范围。
然后这样 DP 就可以过了。
Code
#include<bits/stdc++.h>
using namespace std;
int n;
const int M=2e5+5;
#define ll long long
ll a[M],m,tpm;
array<ll,2> d[17];
ll val[17];
int dcnt;
unordered_map<ll,int> mp;
int _2[M];
const int mod=998244353;
int f[1<<13];
inline void R(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
return;
}
ll P[M],G[M],pcnt;
void dfs(int dep,ll now){
if(dep>dcnt){
P[++pcnt]=now;
for(int i=1;i<=dcnt;i++)if(now%val[i]==0)G[pcnt]|=(1<<(i-1));
return;
}
for(int i=0;i<=d[dep][1];i++){
dfs(dep+1,now);
now*=d[dep][0];
}
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
tpm=m;
for(int i=1;i<=n;i++)cin>>a[i],mp[a[i]]++;
for(int i=2,lim=sqrt(m);i<=lim;i++){
if(tpm%i==0){
d[++dcnt]={i,0};
val[dcnt]=1;
while(tpm%i==0){
d[dcnt][1]++;
tpm/=i;
val[dcnt]*=i;
}
lim=sqrt(tpm);
}
}
if(tpm!=1){d[++dcnt]={tpm,1};val[dcnt]=tpm;}
_2[0]=1;
for(int i=1;i<=n;i++)_2[i]=2ll*_2[i-1]%mod;
if(m==1){
cout<<_2[mp[1]]-1<<"\n";
return 0;
}
dfs(1,1);
// for(int i=1;i<=pcnt;i++)cout<<i<<" "<<P[i]<<" "<<G[i]<<" "<<mp[P[i]]<<'\n';
f[0]=0;
for(int i=1;i<=pcnt;i++)if(G[i]==0){
f[0]+=mp[P[i]];
}
f[0]=_2[f[0]];
// cerr<<f[0]<<"\n";
for(int i=1;i<=pcnt;i++)if(G[i]){
int tmp=_2[mp[P[i]]]-1;
for(int j=(1<<dcnt)-1;j>=0;j--){
R(f[j|G[i]],1ll*f[j]*tmp%mod);
}
}
cout<<f[(1<<dcnt)-1];
return 0;
}
[ABC345E] Colorful Subsequence
link。
有 \(N\) 个球，每一个球有一个颜色 \(C_i\) 和价值 \(V_i\)，现在要删除其中的 \(K\) 个球，使得剩下的球没有相邻的两个球颜色相等。求剩下的球的最大价值总和。
$ 1\leq K<N\leq 2\times 10^5,K\leq 500 $。
当时我和 nit 都在场，然后好像都没有胡出来简单做法。
Solution
一个非常简单的思路就是设 \(f_{i,j}\) 为 \(i\) 位置钦定保留，之前删去了 \(j\) 个位置的最大价值和。转移可以枚举前 \(k\) 个位置然后做到 \(O(NK^2)\)。
上面这个做法是显然过不了的。考虑我们先不看相邻球颜色不等的条件，我们发现如果接着这个思路 DP，那么我们可以直接对于 \(i\) 维护 \(c_{i-j}\gets f_{i,j}\)，然后对于一个位置 \(i+1\)，转移变为 \(f_{i+1,j}\gets c_{i-j}+v_{i+1}\)。这里 \(c\) 就表示前 \(k\) 个位置（\(k\) 是你目前枚举到的数）还剩下 \(i\) 个此时的最大价值和。
但是加入了这个颜色的限制怎么办？一个经典的 trick 是把最大值和次大值都记录下来，其中钦定最大值和次大值对应的颜色不同，这样如果目前颜色和最大值颜色相同，它可以直接使用次大值作为最大值。
这样这个 \(c_i\) 就可以简单维护了，时间复杂度 \(O(NK)\)。
Code
#include<bits/stdc++.h>
using namespace std;
const int M=2e5+5;
int n,k;
int c[M],v[M];
#define ll long long
struct info{
int mxc;
ll mx;
int sec;
ll se;
}C[M];//i-k
inline void mer(info &x,int col,ll w){
if(w>x.mx){
if(col==x.mxc)x.mx=w;
else{
x.sec=x.mxc,x.se=x.mx;
x.mxc=col,x.mx=w;
}
}else if(w>x.se){
if(col==x.mxc)return;
x.sec=col,x.se=w;
}
return;
}
ll f[505];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>c[i]>>v[i];
f[0]=0;
for(int i=0;i<=n;i++)C[i]={0,-1000000000000000000ll,1000000000,-1000000000000000000ll};
C[0].mx=0;
ll ans=-1;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++)f[j]=-1e18;
for(int j=max(i-k-1,0);j<i;j++){
if(c[i]==C[j].mxc)f[i-j-1]=C[j].se+v[i];
else f[i-j-1]=C[j].mx+v[i];
}
if(i>=n-k)ans=max(ans,f[k+i-n]);
for(int j=min(i,k);j>=0;j--)mer(C[i-j],c[i],f[j]);
}
cout<<ans;
return 0;
}
LCS
Longest Common Subsequence。不是 Substring。
因为 AT 题比较少，所以加了几道其它的。
CF578D LCS Again
link。
给定一个字符串 \(S\)，求有多少个与 \(S\) 等长字符串 \(T\)，满足 \(\mathrm{LCS}(S,T)=|S|-1\)，其中 \(S,T\) 只包含前 \(m\) 个小写字母。
$ 1\leq n\leq 100000,2\leq m\leq 26 $。
Solution 1
一个非常简单的非 DP 做法。
显然匹配只可能长成：
\[(i,i),(j,j+1),(k,k)\\ (i,i),(j+1,j),(k,k) \]钦定两个未被匹配的位置 \(s,t\) 不等，计数随便做就完了。
但是你容易发现算重了，具体来说，形如 ababababa 的长度大于 \(1\) 的字符串可以使得两种匹配中间的那个都匹配上，去除即可。
时间复杂度 \(O(n)\)。
Solution 2
如果是把题中 \(|S|-1\) 变成 \(|S|-k\)，其中 \(k\) 是一个比较小的数，上面那个做法就死了。
考虑这时怎么做。为了去重，我们需要一种状态使得从这个状态出发，我们只需要 \(T\) 后面的所有字符就能得到唯一的 \(\operatorname{LCS}\) 长度。显然如果我们对于 \(T\) 上的每个位置，把 \(S\) 上的每个位置的 \(\operatorname{LCS}\) 长度记下来一定是没问题的，但是这样状态就疑似有点大了。
一种 trival 的思路是差分掉这个信息，因为显然 \(\operatorname{LCS}(S_{1\sim i},T_{1\sim j})\) 和 \(\operatorname{LCS}(S_{1\sim i+1},T_{1\sim j})\) 的差最多为 \(1\)，可以状压。但是还不够。
遇到这种瓶颈，我们可以考虑目前那些 \(\operatorname{LCS}\) 长度信息可能对最终的答案产生贡献。不难发现对于 \(\operatorname{LCS}(S_{1\sim i},T_{1\sim j})\)，\(i<j-k\) 和 \(i>j+k\) 的所有信息都没用，因为这个位置的剩余答案的最大增量和这个 \(\operatorname{LCS}\) 的长度值之和已经小于 \(|S|-k\) 了，所以我们只需要记录 \(j-k\leq i\leq j+k\) 对应的所有值即可。这一部分可以差分并且记录 \(\operatorname{LCS}(S_{1\sim i},T_{1\sim i})\) 的答案，这个答案和 \(i\) 的差值不超过 \(k\)，这个时候我们就成功把状态压成 \(O(k2^{2k})\) 级别了。
而转移显然是简单的，就是枚举下一个填什么。因为只有 \(O(k)\) 有个本质不同效果的字母，所以总复杂度可以做到 \(O(nk^3 2^{2k})\)，可以通过这个题。
Code for Sol 1
#include<bits/stdc++.h>
using namespace std;
int n,m;
string s;
const int M=1e5+5;
int pr[M],su[M];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
cin>>s;s=" "+s;
for(int i=2;i<=n;i++)pr[i]=pr[i-1]+(s[i]==s[i-1]);
for(int i=n-1;i>=1;i--)su[i]=su[i+1]+(s[i]==s[i+1]);
long long ans=0;
for(int i=1;i<=n;i++)ans+=1ll*(m-1)*(i-pr[i]);
for(int i=n;i>=1;i--)ans+=1ll*(m-1)*(n-i-su[i]);
int len=1;
char lstc=s[1];
for(int i=2;i<=n;i++){
if(s[i]==s[i-1]){
len=1,lstc=s[i];
}else if(len<2){
ans-=len;
len++;
}else if(lstc!=s[i]){
len=2;
ans--;
lstc=s[i-1];
}else{
ans-=len;
len++;
lstc=s[i-1];
}
}
cout<<ans;
return 0;
}
Code for Sol 2
Sol 2 中提到的那个题的代码。
#include<bits/stdc++.h>
using namespace std;
string s;
// #define int long long
const int mod=1e9+7;
inline void R(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
return;
}
int n;
bool vis[26];
int f[5][1<<3][1<<3],g[5][1<<3][1<<3],k,val[50005],nval[50005];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>s;
n=s.size();
s=" "+s;
cin>>k;
f[0][0][0]=1;
for(int i=0;i<n;i++){
memcpy(g,f,sizeof g);
memset(f,0,sizeof f);
for(int lim1,lim2,zt1,zt2,v=max(0,i-k);v<=i;v++){
lim1=min(i,k),lim2=min(n-i,k);
val[i]=v;
for(int o1=0;o1<(1<<lim1);o1++){
for(int j=0;j>-lim1;j--)val[i+j-1]=val[i+j]-((o1>>(-j))&1);
for(int o2=0,cnt;o2<(1<<lim2);o2++){
if(!g[i-v][o1][o2])continue;
for(int j=0;j<lim2;j++)val[i+j+1]=val[i+j]+((o2>>(lim2-j-1))&1);
val[i+lim2+1]=0;
nval[i-lim1]=val[i-lim1];
cnt=0;
for(int j=i-lim1+1,lim=min(n,i+1+lim2);j<=lim;j++)nval[j]=max({val[j],val[j-1]}),cnt+=(!vis[s[j]-'A']),vis[s[j]-'A']=1;
zt1=0,zt2=0;
for(int j=max(i+1-k,i-lim1);j<=i;j++)zt1<<=1,zt1|=((nval[j+1]-nval[j]));
for(int j=i+2,lim=min(n,i+1+lim2);j<=lim;j++)zt2<<=1,zt2|=(nval[j]-nval[j-1]);
R(f[i+1-nval[i+1]][zt1][zt2],1ll*(26-cnt)*g[i-v][o1][o2]%mod);
for(char T='A';T<='Z';T++){
if(!vis[T-'A'])continue;
vis[T-'A']=0;
for(int j=i-lim1+1,lim=min(n,i+1+lim2);j<=lim;j++)nval[j]=max({nval[j-1],val[j],val[j-1]+(T==s[j])});//,cerr<<j<<" "<<nval[j]<<"\n";
zt1=0,zt2=0;
for(int j=max(i+1-k,i-lim1);j<=i;j++)zt1<<=1,zt1|=((nval[j+1]-nval[j]));
for(int j=i+2,lim=min(n,i+1+lim2);j<=lim;j++)zt2<<=1,zt2|=(nval[j]-nval[j-1]);
// cerr<<i<<" "<<i+1-nval[i+1]<<" "<<(bitset<1>)zt1<<" "<<(bitset<1>)zt2<<" from "<<i-v<<" "<<(bitset<1>)o1<<" "<<(bitset<1>)o2<<" val = "<<g[i-v][o1][o2]<<"\n";
R(f[i+1-nval[i+1]][zt1][zt2],g[i-v][o1][o2]);
}
}
}
}
}
int ans=0;
for(int i=0;i<=k;i++)for(int j=0;j<(1<<k);j++)R(ans,f[i][j][0]);
cout<<ans;
return 0;
}
[ARC157F] XY Ladder LCS
link。
给定两个长度为 \(n\)，且仅包含
X或Y的字符串 \(S,T\)。对于每个整数 \(i\in [1,n]\)，你都可以选择交换 \(S_i,T_i\) 或者不交换。请你最大化交换完后的最长公共子序列长度，并输出一组合法的最长公共子序列。如果有多种合法答案，请输出 字典序最小的。
\(n\le 50\)。
Solution
显然这个题最难之处是在描述这个交换的状态，因为这个 \(\operatorname{LCS}\) 的 DP \(f_{i,j}\) 中需要时刻保持对大于 \(\min(i,j)\) 的下标的字符了解清楚是什么。
暴力点想，我们可以直接暴力状压中间的位置有没有被交换过，容易做到 \(O(n2^{n})\) 或 \(O(n^22^n)\)。
沿用上一道题的思路，我们尝试证明其下界以降低状压长度。不难手玩发现对于一个长度为 \(3\) 的串，答案至少为 \(2\)，所以容易知道对于长度为 \(n\) 的串，答案至少为 \(\lfloor\frac{2n}{3}\rfloor\)。所以我们 \(|i-j|\leq \lceil\frac{n}{3}\rceil\)，是因为同样的原因，如果超过这个值的状态有用，那么答案一定小于 \(\lfloor\frac{2n}{3}\rfloor\)，矛盾。
而我们的状态如果按照某个字符串顺序滚动，那么我们知道对于另一维的状态数是 \(\sum_{0\leq i\leq \lceil\frac{n}{3}\rceil}2^{i}=O(2^{\frac{n}{3}})\)，转移是 \(O(1)\) 的，所以总复杂度为 \(O(n2^{\frac{n}{3}})\)。
输出方案的话，DP 的时候记录可以直接记录状压后的答案。
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int f[55][1<<17],g[55][1<<17];
long long sf[55][1<<17],sg[55][1<<17];
int n;
string s[2];
inline void R(int &pf,long long &psf,int &pg,long long &psg,int op=2){
int val=(op<2);
ll tp=0;
if(pg<pf+val){
pg=pf+val;
psg=psf;
if(op<2)psg=(psg<<1)|op;
}else if(pg==pf+val){
tp=psf;
if(op<2)tp=(tp<<1)|op;
if(psg>tp)psg=tp;
}
return;
}
inline int _1(int p){return (1<<p)-1;}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
cin>>s[0]>>s[1];
s[0]=" "+s[0],s[1]=" "+s[1];
for(int i=0;i<n;i++){
// cerr<<i<<" TO start\n";
for(int j=max(i-16,0);j<=min(i+16,n);j++){
for(int k=0,lim=(1<<abs(i-j));k<lim;k++){
g[j][k]=0,sg[j][k]=0;
}
}
char tmp;
int vt;
for(int j=max(i-16,0);j<i;j++){
for(int k=0,lim=(1<<(i-j));k<lim;k++){
vt=k&_1(i-j-1);
R(f[j][k],sf[j][k],f[j+1][vt],sf[j+1][vt]);
R(f[j][k],sf[j][k],g[j][k<<1],sg[j][k<<1]);
R(f[j][k],sf[j][k],g[j][k<<1|1],sg[j][k<<1|1]);
tmp=s[(k>>(i-j-1))&1][j+1];
if(tmp==s[0][i+1])R(f[j][k],sf[j][k],g[j+1][vt<<1|1],sg[j+1][vt<<1|1],tmp-'X');
if(tmp==s[1][i+1])R(f[j][k],sf[j][k],g[j+1][vt<<1],sg[j+1][vt<<1],tmp-'X');
}
}
// =i
R(f[i][0],sf[i][0],f[i+1][1],sf[i+1][1]);
R(f[i][0],sf[i][0],f[i+1][0],sf[i+1][0]);
R(f[i][0],sf[i][0],g[i][0],sg[i][0]);
R(f[i][0],sf[i][0],g[i][1],sg[i][1]);
if(s[0][i+1]==s[1][i+1])R(f[i][0],sf[i][0],g[i+1][0],sg[i+1][0],s[0][i+1]-'X');
for(int j=i+1,lim=min(i+16,n);j<=lim;j++){
for(int k=0,lim=(1<<(j-i));k<lim;k++){
vt=k&_1(j-i-1);
R(f[j][k],sf[j][k],f[j+1][k<<1],sf[j+1][k<<1]);
R(f[j][k],sf[j][k],f[j+1][k<<1|1],sf[j+1][k<<1|1]);
R(f[j][k],sf[j][k],g[j][vt],sg[j][vt]);
tmp=s[((k>>(j-i-1))&1)^1][i+1];
if(tmp==s[0][j+1])R(f[j][k],sf[j][k],g[j+1][vt<<1],sg[j+1][vt<<1],tmp-'X');
if(tmp==s[1][j+1])R(f[j][k],sf[j][k],g[j+1][vt<<1|1],sg[j+1][vt<<1|1],tmp-'X');
}
}
for(int j=max(i-16,0);j<=min(i+16,n);j++){
for(int k=0,lim=(1<<abs(i-j));k<lim;k++){
f[j][k]=g[j][k],swap(sf[j][k],sg[j][k]);
}
}
// cerr<<i<<" TO complete\n";
}
int ans=0;ll pans=0;
for(int j=max(n-17,0);j<=n;j++){
for(int k=0,lim=(1<<(n-j));k<lim;k++){
if(f[j][k]>ans){
ans=f[j][k],pans=sf[j][k];
}else if(f[j][k]==ans&&pans>sf[j][k])pans=sf[j][k];
}
}
for(int i=ans-1;i>=0;i--){
cout<<(char)('X'+((pans>>i)&1));
}
return 0;
}
[AGC021D] Reversed LCS
link。
高桥决定给他母亲一根字符串。
字符串 \(T\) 的值是 \(T\) 和 \(T'\) 最长公共子序列的长度，其中 \(T'\) 是通过反转 \(T\) 获得的字符串。
高桥有一个字符串 \(s\)。他想给她母亲一个可能值最高的字符串，所以他想将 \(s\) 中最多 \(k\) 个字符更改为任何其他字符，以获得可能值最高的字符串。找到可能达到的最高值。
$ 1\ \leq\ |s|\ \leq\ 300 $。
Solution
其实这个题我想给个 Hint 的。
引理：\(\operatorname{LCS}(T,\operatorname{rev}(T))=\operatorname{LPS}(T)\)，其中 \(\operatorname{LPS}\) 是 Longest Palindrome Subsequence。
怎么证？简单点说，首先不难发现任意回文子序列都是公共子序列；其次对于一个最长公共子序列，我们一定能找到一个 \(i+j=n\) 使得把两个序列分成两个完全一致的部分（\(T_{1\sim i}\) 和 \(\operatorname{rev(T)}_{1\sim j}\) 为一部分，剩余为一部分），那么左右两边的公共子序列可以一致，并且拼在一起就是回文串，所以存在最长公共子序列使得其是回文。
剩下的就好办了，可以直接区间 DP，设区间 \([i,j]\) 更改了 \(k\) 个字符的回文子序列最大长度。注意这里是自己和自己反串的回文最大长度，转移容易。时间复杂度 \(O(n^3)\)。
Code
#include<bits/stdc++.h>
using namespace std;
string s;
int k,n;
const int M=305;
int f[M][M][M];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>s;
n=s.size();
s=" "+s;
cin>>k;
for(int i=1;i<=n;i++)f[i][i][0]=1;
for(int len=2;len<=n;len++){
for(int l=n-len+1,r;l>0;l--){
r=l+len-1;
for(int o=0;o<=k;o++){
f[l][r][o]=max(f[l][r-1][o],f[l+1][r][o]);
if(s[l]==s[r])f[l][r][o]=max(f[l][r][o],f[l+1][r-1][o]+2);
else if(o)f[l][r][o]=max(f[l][r][o],f[l+1][r-1][o-1]+2);
}
}
}
int ans=0;
for(int i=0;i<=k;i++)ans=max(f[1][n][i],ans);
cout<<ans;
return 0;
}
SP12076 LCS0
link。
给定两个只包含小写字母的字符串，长度小于等于 \(50000\)。求最长公共子序列。
Solution
LOJ 上也有几乎一样的题：LOJ6564。
显然直接 \(O(nm)\) 会私募 不能过。
有别于 LIS，LCS 是对两个串进行操作，虽然 LCS 的确可以转化成 LIS，具体就是把某个串按顺序出现的每个字母 在另一个串出现位置的序列降序排列之后的序列 拼在一起，但是显然可以被卡到 \(O(n^2)\) 长度。所以转化成其他基础问题然后 1log 做掉其实是不太现实的。那么我们尝试对 LCS 最暴力的 DP 分析，看能不能在 \(O(nm)\) 的基础上在复杂度上除去一个值。
设 \(f_{i,j}\) 为第一个串长度为 \(i\) 的前缀和第二个串长度为 \(j\) 的前缀的 LCS 长度，首先滚动该数组（假设滚动第二个串），然后将该数组差分，得到一个二进制串，接下来我们对这个二进制串操作。
我们钦定一个目前的二进制串进行分析（注意低位是小下标）。假设目前的串是 \(x=000010010001\)，目前加入的字母在第一个串是否出现的二进制表示是 \(s=001100100110\)。考虑合并。
对于 \(s\) 中的每个 \(1\)，若想转移它，那么一定用的是小于该位的所有 \(x\) 中的 \(1\)。所以我们可以发现可以这样转移：将 \(x\) 分成若干形如 \(100\cdots\) 的块（若首位非 \(1\) 则第一块是含最高位连续 \(0\) 段），我们将 \(x\operatorname{or} s\) 按相同的划分来分块，取每一块最右边的 \(1\) 作为这一块中的 \(1\)。
正确性是显然的，因为一个块中至多含有一个 \(1\)，并且之前 \(x\) 中有 \(1\) 的块一定有 \(1\)，不影响刚才说的转移方式，可以模拟上面的例子来理解。
如何用基本运算表示上面的合并过程？设 \(g=x\operatorname{or} s\)，可以发现上面的过程可以表示为 \(((g-(\operatorname{mov}(x,\gets,1)\operatorname{or}1))\oplus g)\operatorname{and} g\)，如果减法会减出负数那么就把减数的首位去除。手写 bitset 即可。
时间复杂度 \(O(\frac{nm}{\omega})\)。
其实不难发现上面的操作其实就是由高位到低位按 LIS 那种贪心加入每个 \(s\) 中的 \(1\)。
Code
#include<bits/stdc++.h>
using namespace std;
string s,t;
int ssiz,tsiz;
#define ull unsigned long long
template<int D>
struct bits_{
ull b[D/64+5];
const int LIM=D/64+1;
inline bool ask(int x){
return (b[x/64]>>(x%64))&1;
}
inline void set(int x,bool op){
if(((b[x/64]>>(x%64))&1)^op)b[x/64]^=(1ull<<(x%64));
return;
}
inline bits_<D> operator =(bits_<D> y){
memcpy(b,y.b,sizeof b);
return *this;
}
inline bits_<D> operator ^(bits_<D> &y){
bits_<D> res;
for(int i=0;i<=LIM;i++)res.b[i]=b[i]^y.b[i];
return res;
}
inline bits_<D> operator &(bits_<D> &y){
bits_<D> res;
for(int i=0;i<=LIM;i++)res.b[i]=b[i]&y.b[i];
return res;
}
inline bits_<D> operator *(bits_<D> &y){
bits_<D> res;
for(int i=0;i<=LIM;i++)res.b[i]=(b[i]^y.b[i])&y.b[i];
return res;
}
inline bits_<D> operator |(bits_<D> &y){
bits_<D> res;
for(int i=0;i<=LIM;i++)res.b[i]=b[i]|y.b[i];
return res;
}
inline bits_<D> operator -(bits_<D> &y){
bool op=0,po=0;
bits_<D> res;
for(int i=0;i<=LIM;i++){
if(b[i]<y.b[i]||(b[i]==y.b[i]&&op))po=1;
else po=0;
res.b[i]=b[i]-op-y.b[i];
op=po;
}
return res;
}
inline bits_<D> operator <<(int x){
//x<64
if(x==0)return *this;
bits_<D> res;
ull sed=0,ps=0;
for(int i=0;i<=LIM;i++){
ps=b[i]>>(64-x);
res.b[i]=b[i]<<x|sed;
sed=ps;
}
return res;
}
inline int highbit(){
for(int j=LIM,x=(LIM)*64;j>=0;j--,x-=64){
if(b[j])return x+__lg(b[j]);
}
return -1;
}
inline int count(){
int res=0;
for(int j=0;j<=LIM;j++)res+=__builtin_popcountll(b[j]);
return res;
}
};
bits_<50005> S[26],f,g,cf,cg;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>s>>t;
ssiz=s.size(),tsiz=t.size();
s=" "+s,t=" "+t;
for(char d='a';d<='z';d++){
for(int i=1;i<=ssiz;i++){
if(s[i]==d)S[d-'a'].set(i-1,1);
}
}
for(int i=1;i<=tsiz;i++){
g=S[t[i]-'a']|f;
cf=f<<1;
cf.set(0,1);
int p1=cf.highbit(),p2=g.highbit();
if(p1>p2)cf.set(p1,0);
cg=g-cf;
g=cg*g;
f=g;
}
cout<<f.count();
return 0;
}
CF1584F Strange LCS
link。
给定 \(n\) 个字符串 \(s_i\)，每个字符串只包含大写和小写英文字母，且每个字母在每个字符串中最多出现两次，求这些字符串的最长公共子序列。
\(1\leq n\leq 10,1\leq T\leq 5\)。
Solution
很简单的啊，仔细想想的话应该大家都能做出来。
考虑一个经典 trick，就是枚举转移会有额外贡献的转移，既然有额外贡献，那么被转移的状态所有目前的字符一定会一致，那么我们就可以状压这个字符是每个串中的第一个还是第二个。
转移就直接枚举下一个字符是什么就行了，时间复杂度 \(O\left(Tn2^n|\Sigma|^2\right)\)。
Code
#include<bits/stdc++.h>
using namespace std;
int f[65][1<<10];
inline int id(char T){
if(T>='a')return T-'a';
else return T+26-'A';
}
string s[15];
int n,siz[15];
int to[15][55][2];
array<int,2> g[55][1<<10];
inline char org(int x){
if(x<26)return x+'a';
else return x+'A'-26;
}
inline void solve(){
cin>>n;
memset(to,0,sizeof to),memset(f,0,sizeof f);
for(int i=0;i<=52;i++){
for(int j=0;j<(1<<n);j++){
g[i][j]={-1,-1};
}
}
for(int i=1;i<=n;i++)cin>>s[i],siz[i]=s[i].size(),s[i]="["+s[i];
for(int i=1;i<=n;i++)for(int j=0;j<=siz[i];j++){
if(to[i][id(s[i][j])][0])to[i][id(s[i][j])][1]=j+1;
else to[i][id(s[i][j])][0]=j+1;
}
bool ok=0;
for(int i=0;i<=siz[1];i++){
int ID=id(s[1][i]);
bool val=(to[1][ID][1]==i+1);
bool flg=0;
for(int j=1;j<=n;j++)if(!to[j][ID][0])flg=1;
if(flg)continue;
if(i!=0)ok=1;
for(int nv,ft,j=0;j<(1<<(n-1));j++){
nv=j<<1|val;
ft=0;
for(int o=1;o<=n;o++)if(!to[o][ID][(nv>>(o-1))&1])ft=1;
if(ft)continue;
for(int k=0,nxt,fl;k<52;k++){
nxt=0;
fl=0;
for(int o=1;o<=n;o++){
if(to[o][k][0]>to[o][ID][(nv>>(o-1))&1])continue;
if(to[o][k][1]>to[o][ID][(nv>>(o-1))&1])nxt|=(1<<(o-1));
else{
fl=1;
break;
}
}
if(!fl){
if(f[k][nxt]<f[ID][nv]+1){
f[k][nxt]=f[ID][nv]+1;
g[k][nxt]={ID,nv};
}
}
}
}
}
// cerr<<"ok = "<<ok<<'\n';
if(!ok)cout<<0<<"\n\n";
else{
int ans=0;
int p1=0,p2=0;
for(int i=0;i<52;i++)for(int j=0;j<(1<<n);j++){
if(ans<f[i][j]){
ans=f[i][j],p1=i,p2=j;
}
}
cout<<ans<<"\n";
string st="";
while(g[p1][p2][0]!=-1){
st=org(p1)+st;
auto tmp=g[p1][p2];
p1=tmp[0],p2=tmp[1];
// cout<<org(p1)<<" "<<p2<<'\n';
}
cout<<st;
cout<<'\n';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--)solve();
return 0;
}
LIS
写完这个这个课件就暂告一段落了。
[ARC180E] LIS and Inversion
link。
Hanghang 写了题解/bx。
给你一个长度为 \(N\) 的序列 \(A\)，满足 \(0\le A_i<i\)。
定义一个排列 \(P\) 的得分为它的最长上升子序列长度，同时定义其代价为满足以下条件的正整数 \(i\) 的数量：
- 只存在小于 \(A_i\) 个位置 \(j<i\)，使得 \(P_j>P_i\)。
对每个 \(k=1,2,\cdots,n\)，求所有得分不小于 \(k\) 的排列的最小代价。
$ 1\leq N\leq 250000,0\leq A_i <i $。
Solution
首先可以想到类似正常排列 DP 那样，设 \(f_{i,j,k}\) 为前 \(i\) 个数中，LIS 末对应的数是第 \(j\) 小，目前 LIS 长度为 \(k\) 的最小代价。注意这里有 \(f_{i,i,1}=1\)，因为 LIS 长至少为一。
注意到它求得是一个不小于 \(k\) 的的得分，所以我们不用担心转移时转移到其他非 LIS 上，因为是取 \(\min\)，其对前面的贡献是不优的。
因为是三维状态，显然巨难优化，考虑暴力删掉 LIS 长度一维，把它放到 DP 的结果中。现在我们不得不钦定代价是什么，现在我们考虑代价为 \(0\)。
容易列出式子：
\[f_{i,j}\gets f_{i-1,j-1}\ \ (j>a_i+1)\\ f_{i,j}\gets f_{i-1,j}\\ f_{i,j}\gets f_{i-1,j}+1\ \ (j> a_i) \]因为 \(f_{i,i}\) 等于 \(1\)，所以显然第一个转移没有一点用。然后第三个转移是显然转移到 \(j\) 更优，因为转移到 \(<j\) 的更容易受 \(a_{i}\) 限制。
那就相当于 \(f_{i,j}\gets f_{i-1,j}+[j>a_i]\)。对于每个 \(j\) 转移，容易差分计算出 \(f_{n,j}\)。
考虑成本不为 \(0\)，为 \(r\)，那就对所有 \(j\leq n-r\) 的所有 \(f_{n,j}\) 加 \(r\)。考虑得分小于等于 \(k\) 的答案，钦定成本为 \(k\)，模拟加的过程，显然会加 \(k\)，我们只需要减去原来可以有的 \(f_{n,j}\) 贡献就能获得真实值，故答案为 \(\max(k-\max_{i=1}^{n-k+1}f_{n,i},0)\)。
Code
#include<bits/stdc++.h>
using namespace std;
int n;
const int M=2.5e5+5;
int f[M];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1,x;i<=n;i++)cin>>x,f[x+1]++,f[i+1]--;
for(int i=1;i<=n;i++)f[i]+=f[i-1];
for(int i=1;i<=n;i++)f[i]=max(f[i],f[i-1]);
for(int i=1;i<=n;i++)cout<<max(i-f[n-i+1],0)<<" ";
return 0;
}
[ARC175D] LIS on Tree 2
link。
有 DP 元素。
给定一棵 \(N\) 个节点的树。
你需要给每一个点 \(i\) 赋一个 \([1,N]\) 间的权值 \(w_i\)，任意两个节点权值不同。
对于每个点 \(i\)，令 \((v_1=1,v_2,...,v_k=i)\) 为点 \(1\) 到点 \(i\) 的路径。定义该点的得分为序列 $ (w_{v_1},w_{v_2},...,w_{v_k})$ 的最长上升子序列长度。
请给出一种赋值方案使所有节点得分之和为 \(K\)，或报告不存在。
$ 2 \leq N \leq 2\times 10^5,1\leq K \leq 10^{11} $。
Solution
怎么构造被加入题单了/qd。
做这个题的时候巨唐，想的方向基本正确，但是最唐的构造没想出来。
首先可以想到，假设一个点 对 LIS 一定没有贡献，那么贡献需要减去以该点为根的子树大小。假设我们知道 一些点没有贡献，同时钦定其它点一定有贡献 的构造方式，那么我们一定至少需要解决这个问题：你需要选择一些子树，使得它们的大小之和等于 \(K\)。
乍一看只能背包解决，但是别急着优化普通做法，因为子树的特殊性，这个问题实际上可以贪心，因为可以归纳证明一定可达所有在上下界间的数。
接下来看怎么构造，不难发现可以直接让没有贡献的点最小并且倒序排列，剩余的点更大然后正序排列，这样就 OK 了。注意根必须有贡献。
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll k;
const int M=2e5+5;
vector<int> E[M];
int siz[M],ans[M];
ll sum;
void dfs(int now,int f){
siz[now]=1;
for(auto p:E[now])if(p^f){
dfs(p,now);
siz[now]+=siz[p];
}
return;
}
array<int,2> po[M];
bool vis[M];
int cnt;
void dfsnv(int now,int f){
for(auto p:E[now])if(p^f)dfsnv(p,now);
if(!vis[now])ans[now]=++cnt;
return;
}
void dfsv(int now,int f){
if(vis[now])ans[now]=++cnt;
for(auto p:E[now])if(p^f)dfsv(p,now);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1,u,v;i<n;i++)cin>>u>>v,E[u].push_back(v),E[v].push_back(u);
dfs(1,0);
for(int i=1;i<=n;i++)sum+=siz[i],po[i]={siz[i],i};
if(k>sum||k<n)return cout<<"No\n",0;
sort(po+1,po+n+1,greater<array<int,2> >());
for(int i=1;i<=n;i++)if(k>=po[i][0]){
vis[po[i][1]]=1;
k-=po[i][0];
}
dfsnv(1,0);
dfsv(1,0);
cout<<"Yes\n";
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
return 0;
}
P3643 [APIO2016] 划艇
link。
本来是要选另外一道题的，但是太史了就换成这个了。
在首尔城中，汉江横贯东西。在汉江的北岸，从西向东星星点点地分布着 \(N\) 个划艇学校，编号依次为 \(1\) 到 \(N\)。每个学校都拥有若干艘划艇。同一所学校的所有划艇颜色相同，不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一样的。每个学校可以选择派出一些划艇参加节日的庆典，也可以选择不派出任何划艇参加。如果编号为 \(i\) 的学校选择派出划艇参加庆典，那么，派出的划艇数量可以在 \(a_i\) 至 \(b_i\) 之间任意选择。
值得注意的是，编号为 \(i\) 的学校如果选择派出划艇参加庆典，那么它派出的划艇数量必须大于任意一所编号小于它的学校派出的划艇数量。
输入所有学校的 \(a_i,b_i\) 的值，求出参加庆典的划艇有多少种可能的情况，必须有至少一艘划艇参加庆典。两种情况不同当且仅当有参加庆典的某种颜色的划艇数量不同。
\(1 \leq N \leq 500,1\leq a_i\leq b_i\leq 10^9\)。
Solution
注意到值域很大，就不能把值域塞到状态里。
但是我们可以把值域连续段塞到状态里。设 \(f_{i,j,k}\) 表示前 \(i\) 个学校，目前 IS 末尾在 \(j\) 连续段，已经有 \(k\) 个在 \(j\) 连续段的数在 IS 中。
转移到 \(f_{i,j,1}\) 是简单的，前缀和优化即可。而转移到 \(f_{i,j,k}(k>1)\)，就从 \(f_{i-1,j,k-1}\) 转移过来乘上吸收的系数即可，因为相同段的贡献是一个组合数。
Code
#include<bits/stdc++.h>
using namespace std;
int n;
const int mod=1e9+7;
const int M=505;
int f[M*4][M],g[M*4],a[M],b[M];
inline void R(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
return;
}
#define ll long long
inline ll ksm(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
return res;
}
int val[M*2],vcnt;
int fac[M],ifac[M],inv[M];
int len[M*4];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=1ll*i*fac[i-1]%mod;
ifac[n]=ksm(fac[n],mod-2);
for(int i=n-1;i>=0;i--)ifac[i]=1ll*(i+1)*ifac[i+1]%mod;
for(int i=1;i<=n;i++)inv[i]=1ll*fac[i-1]*ifac[i]%mod;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
val[++vcnt]=a[i];
val[++vcnt]=b[i];
}
sort(val+1,val+vcnt+1);
vcnt=unique(val+1,val+vcnt+1)-val-1;
for(int i=1;i<=vcnt*2;i++){
if(i&1)len[i]=val[i/2+1]-val[i/2]-1;
else len[i]=1;
}
len[1]=1;
f[1][1]=1;
for(int i=1;i<=n;i++){
memset(g,0,sizeof g);
for(int j=1;j<=vcnt*2;j++){
for(int k=1;k<=min(n,len[j]);k++)R(g[j],f[j][k]);
R(g[j],g[j-1]);
}
int pl=lower_bound(val+1,val+vcnt+1,a[i])-val,pr=lower_bound(val+1,val+vcnt+1,b[i])-val;
// cerr<<pl*2<<" "<<pr*2<<" "<<len[pl*2]<<" "<<len[pr*2]<<" "<<g[1]<<"\n";
for(int j=pl*2;j<=pr*2;j++){
for(int k=min(n,len[j]);k>=2;k--)R(f[j][k],1ll*f[j][k-1]*(len[j]-k+1)%mod*inv[k]%mod);
if(len[j])R(f[j][1],1ll*g[j-1]*len[j]%mod);
}
}
int ans=0;
for(int i=2;i<=vcnt*2;i++)for(int j=1;j<=n;j++)R(ans,f[i][j]);
cout<<ans;
return 0;
}
[AGC055C] Weird LIS
link。
记 \(f(p)\) 表示排列 \(p\) 的最长上升子序列长度。
记 \(P_i\) 表示排列 \(p\) 去掉第 \(i\) 个数的序列。求有多少长为 \(N\)，值域为 \([2,M]\) 的序列 \(a\) 使得：存在一个排列 \(p\)，\(\forall i\) 有 \(f(P_i)=a_i\)。
答案对素数 \(Q\) 取模。
$ 3\le N\le 5000 , 2 \le M\le N-1 $。
Solution
题解区的做法我是一个没看懂。
设 LIS 长为 \(x\)，那么 \(a\) 的值域为 \([x-1,x]\)。
注意到如果顺序考虑，有 \(x-1\)，那么 LIS 长必然加一，然后如果有 \(x\)，那么要么这里没用，要么这里就是可以被替换。显然一个 \(x\) 段对 LIS 长的贡献至多有 \(\lfloor\frac{len}{2}\rfloor\)，因为前后的 \(x-1\) 一定需要在 LIS 中，中间的数在 LIS 上需要值域连续。为了不算重，我们一个想法是找到能贡献的上界和下界。
所以我们可以设 \(f_{i,j,k}\) 表示前 \(i\) 个数，有 \(j\) 个 \(x-1\)，目前最大可能的 LIS 长度为 \(k\) 的方案数。应该使用前缀和能简单优化至 \(O(n^3)\)。
但是上述做法并不能通过。考虑用钦定避免算重。钦定所有非 选 \(x-1\) 的贡献一定来源于前面，我们可以考虑设 \(f_{i,j,0/1/2/3/4}\)，其中 \(0\) 表示目前可以由 选 \(x\) 贡献而来 时选择一个 \(x-1\)，\(1\) 表示目前可以由 选 \(x\) 贡献而来 时选了一个 \(x\)，\(2\) 表示此时选了 \(2\) 个 \(x\)，对 LIS 贡献为 \(1\)，\(3\) 表示目前不能由 \(x\) 贡献而来时，选一个 \(x\)，\(4\) 则表示不能由 \(x\) 贡献而来时，选一个 \(x-1\)。
一个一个看转移，从 \(0\) 转移，可以转移到 \(1\) 和 \(0\)；从 \(1\) 转移，可以转移到 \(0\) 和 \(2\) 和 \(3\)（因为此时选了两个 \(x\) 不产生贡献，已经违背了前缀的限制，所以一定不能再选）；从 \(2\) 转移，可以转移到 \(0\) 和 \(1\)；从 \(3\) 转移，可以转移到 \(3\) 和 \(4\)；从 \(4\) 转移，也可以转移到 \(3\) 和 \(4\)。\(0\)，\(2\)，\(4\) 被转移到的时候需要从 \(j\) 转移到 \(j+1\)。
时间复杂度 \(O(n^2)\)，注意一些特判即可。
实际上这个题似乎可以组合数算。
Code
#include<bits/stdc++.h>
using namespace std;
const int M=5005;
int f[M][5],g[M][5];
int mod,n,m;
inline void R(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>mod;
f[0][0]=1;
for(int i=1;i<=n;i++){
memset(g,0,sizeof g);
for(int j=0;j<=m;j++){
R(g[j+1][0],f[j][0]);
R(g[j][1],f[j][0]);
R(g[j+1][0],f[j][1]);
R(g[j+1][2],f[j][1]);
R(g[j][3],f[j][1]);
R(g[j+1][0],f[j][2]);
R(g[j][1],f[j][2]);
R(g[j][3],f[j][3]);
R(g[j+1][4],f[j][3]);
R(g[j+1][4],f[j][4]);
R(g[j][3],f[j][4]);
}
memcpy(f,g,sizeof g);
}
int ans=0;
for(int i=3;i<=m;i++)for(int j=0;j<5;j++)R(ans,f[i][j]);
R(ans,(n>3)+(m==n-1));
cout<<ans;
return 0;
}
[JAGSC2018 Day 2] Short LIS
link。
给你三个数字 \(n,A,B\)，你需要统计满足条件的排列 \(p_{0\cdots n-1}\) 的个数：
- 最长上升子序列长度不超过 2。
- \(p_A=B\)。
\(1\le n\le 10^6\)，对 \(10^9+7\) 取模。
Solution
有可能这个题在某些人看来和 DP 毫无关系。
记得导弹拦截吗？我都快忘了（
根据 Dilworth 定理，把这个 LIS 长不超过 \(2\)，变成原序列可以被拆分成两个降序子序列。
为了方便，我们可以钦定 \(p_i\gets n-p_i+1\)，使得问题变成 IS。
容易发现一个 IS 可以被钦定在前缀最大值组成的序列中，另外一个必须满足 IS 才合法，可以感性理解就是前缀最大值不可能接剩下的，所以为了更优，我们肯定不会让剩下的接前缀最大值。
而某个序列可以成为排列的前缀最大值的充要条件是 \(premax_i\geq i\)，容易理解，因为如果小于，前面的可填的数就不够了。
转化为格路计数问题，显然如果钦定了前缀最大值，那么剩下的填法只有一种。现在我们只需要计数使 \(p_A=B\) 成立的格路。
首先考虑 \(B\geq A\)，这样这个一定在前缀最大值中，因为剩下的填法是升序填，前面一定被前缀最大值序列占了格子，因此不可能出现 \(i\leq p_i\) 的情况。那么我们只需要钦定经过这个点即可。考虑我们设一个格路是 \((i,p_i)\to (i,p_{i+1})\to (i+1,p_{i+1})\)，那么我们只需要钦定经过 \((A-1,B-1),(A-1,B),(A,B)\) 即可。根据上面的充要条件，我们只需让这个格路不触碰 \(y=x-1\) 这个直线即可。随便做。
然后是 \(B<A\)。考虑将原序列 \(i\leftrightarrow p_i\)。那么显然剩下的序列仍然满足能分为两个 IS，转化为了上面那种情况。
时间复杂度 \(O(n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7,M=1e6+5;
inline ll ksm(ll a,ll b){
ll res=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
return res;
}
inline void R(int &x,int y){
x+=y;
if(x>=mod)x-=mod;
return;
}
int n,A,B;
int fac[M<<1],ifac[M<<1];
inline int C(int a,int b){return (a<b||b<0)?0:1ll*fac[a]*ifac[b]%mod*ifac[a-b]%mod;}
inline int calc(int X1,int Y1,int X2,int Y2){
int x=Y1+1,y=X1-1;
return (C(X2-X1+Y2-Y1,X2-X1)-C(X2-x+Y2-y,X2-x)+mod)%mod;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>A>>B;
B=n-B;
A++;
fac[0]=1;
for(int i=1;i<=n+n;i++)fac[i]=1ll*fac[i-1]*i%mod;
ifac[n+n]=ksm(fac[n+n],mod-2);
for(int i=n+n-1;i>=0;i--)ifac[i]=1ll*(i+1)*ifac[i+1]%mod;
int ans=0;
if(A>B)swap(A,B);
R(ans,1ll*calc(0,0,A-1,B-1)*calc(A,B,n,n)%mod);
cout<<ans;
return 0;
}
[Yahoo Procon 2017 F] KthLIS
link。
给你一个长度为 \(n\) 的序列 \(a\)，请你求出按字典序升序排列的第 \(K\) 个关于 \(a\) 的最长上升子序列。
$ 1\leq N\leq 300,000,1\leq K\leq 10^{18},1\leq A_i\leq 10^9 $。
这个题我看题解有个地方一直卡住，/bx gyy 一看就知道是什么了。
Solution
建议先看洛谷题解。
首先往序列开头插入 \(-\infty\)，往末尾插入 \(+\infty\)。
一种朴素的想法是，建出 LIS 关系转移图，然后 DP 求出每个点到达终点的方案数。我们先来解决这个 DP 的一些问题。考虑设 \(f_{i}\) 为 \(a_{1\sim i}\) 钦定 \(a_i\) 为末尾的 LIS 长度。我们对于 \(a_{i}\) 和 \(f_i\) 均相同的位置，正常连边 DP 显然会算重，因为我们题目求的是关于数去重，不是关于位置去重。那么我们对于 \(i,j\) 位置使得 \(a_i=a_j,f_i=f_j\) 且 \([i,j]\) 没有其他满足这个条件的点，我们可以让 \(i\) 只连向 \([i,j]\) 区间内的转移。这样去掉了多余的 \([j,n]\) 的贡献，显然不重不漏。
考虑优化 DP。按 \(a_i\) 降序插入原序列，对每个不同 \(f_i\) 的值都建立一棵线段树，每次查询一个区间的和。动态开点即可。
还原回去显然是 \(O(n)\) 的，因为每次我们相当于枚举所有 \(f_{i}=p\) 的位置，总枚举量显然 \(O(n)\)，注意字典序和方案数的一些细节即可。
时间复杂度 \(O(n\log n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll k;
const int M=3e5+5;
int a[M];
const ll inf=1e18;
#define mid ((l+r)>>1)
struct ST{
int tcnt;
int ls[M*20],rs[M*20];
ll sum[M*20];
bool op[M*20];
inline void pushup(int now){
if(op[ls[now]]||op[rs[now]])op[now]=1;
else{
sum[now]=sum[ls[now]]+sum[rs[now]];
if(sum[now]>=inf)op[now]=1;
}
return;
}
inline void mdf(int &now,int l,int r,int pos,ll v){
if(!now)now=++tcnt;
if(l==r){
if(op[now])return;
sum[now]+=v;
if(sum[now]>=inf)op[now]=1;
return;
}
if(pos<=mid)mdf(ls[now],l,mid,pos,v);
else mdf(rs[now],mid+1,r,pos,v);
return pushup(now);
}
inline ll ask(int now,int l,int r,int sl,int sr){
if(!now)return 0;
if(sl<=l&&r<=sr)return op[now]?1e18:sum[now];
ll res=0;
if(sl<=mid)res+=ask(ls[now],l,mid,sl,sr);
if(sr>mid)res+=ask(rs[now],mid+1,r,sl,sr);
if(res>inf)res=inf;
return res;
}
}T;
int vcnt;
struct BIT{
int t[M];
inline void mdf(int x,int v){
while(x<=vcnt){
t[x]=max(t[x],v);
x+=(x&-x);
}
return;
}
inline int ask(int x){
int res=0;
while(x>0){
res=max(res,t[x]);
x-=(x&-x);
}
return res;
}
}xT;
int rt[M];
int dr[M];
ll dp[M];
int f[M],va[M];
unordered_map<ll,int> mp;
vector<int> ans;
array<int,3> seq[M];
vector<array<int,2> > pf[M];
bool vis[M];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
n++;
for(int i=2;i<=n;i++)cin>>a[i],va[i]=a[i];
n++;
a[1]=0,va[1]=0;
a[n]=1e9+1,va[n]=1e9+1;
sort(va+1,va+n+1);
vcnt=unique(va+1,va+n+1)-va-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(va+1,va+vcnt+1,a[i])-va;
for(int i=1;i<=n;i++)f[i]=xT.ask(a[i]-1)+1,xT.mdf(a[i],f[i]),dr[i]=n+1,pf[f[i]].push_back({a[i],i});
for(int i=1;i<=vcnt;i++)sort(pf[i].begin(),pf[i].end());
for(int i=1;i<=n;i++){
ll tp=1ll*a[i]*300005+f[i];
if(!mp[tp])mp[tp]=i;
else{
dr[mp[tp]]=i;
mp[tp]=i;
}
}
for(int i=1;i<=n;i++)seq[i]={a[i],n-f[i],i};
sort(seq+1,seq+n+1,greater<array<int,3> >());
T.mdf(rt[f[n]],1,n,n,1);dp[n]=1;
for(int i=2;i<=n;i++)T.mdf(rt[n-seq[i][1]],1,n,seq[i][2],dp[seq[i][2]]=T.ask(rt[n-seq[i][1]+1],1,n,seq[i][2],dr[seq[i][2]]-1));
if(k>dp[1])return cout<<"None\n",0;
int now=1;
mp.clear();
for(int i=n;i>=1;i--){
ll tp=1ll*a[i]*300005+f[i];
if(mp[tp]){
dp[i]+=dp[mp[tp]];
if(dp[i]>inf)dp[i]=inf;
}
mp[tp]=i;
}
while(now!=n){
int P=now;
for(auto p:pf[f[now]+1])if(a[p[1]]>a[now]&&p[1]>now&&!vis[p[0]]){
vis[p[0]]=1;
if(k>dp[p[1]])k-=dp[p[1]];
else{
ans.push_back(va[a[p[1]]]);
now=p[1];
break;
}
}
assert(now!=P);
for(auto p:pf[f[P]+1])vis[p[0]]=0;
}
ans.pop_back();
for(auto p:ans)cout<<p<<" ";
return 0;
}
P4577 [FJOI2018] 领导集团问题
link。
一个公司的组织领导架构可以用一棵领导树来表示。公司的每个成员对应于树中一个结点 \(v_i\)，且每个成员都有响应的级别 \(w_i\)。越高层的领导，其级别值 \(w_i\) 越小。树中任何两个结点之间有边相连，则表示与结点相应的两个成员属于同一部门。领导集团问题就是根据公司的领导树确定公司的最大部门。换句话说，也就是在领导树中寻找最大的部门结点子集，使得的结点 \(v_i\) 和 \(v_j\)，如果 \(v_i\) 是 \(v_j\) 的子孙结点，则 \(w_i \ge w_j\)。
编程任务：对于任意对于给定的领导树，计算出领导树中最大的部门结点子集。
\(1\le n\le 2\times 10 ^ 5\)，\(0 < w_i \le 10 ^ 9\)。
Solution
讲个简单做法就下拨。
题意可以变成求树上类 LIS。考虑用序列 LIS 的贪心做法，树上合并两棵子树的贪心数组怎么办？不难发现直接合并即可，因为我们是 \(\max (f_i,g_j)\to h_{i+j}\)，模拟归并的过程发现我们不就在干这个事情吗。
加入一个点就正常二分替换即可。使用树上启发式合并，2log。
Code
#include<bits/stdc++.h>
using namespace std;
int n;
const int M=2e5+5;
int w[M],fa[M];
set<pair<int,int> > s[M];
vector<int> E[M];
int hson[M],siz[M];
inline void dfs(int now){
siz[now]=1;
for(auto p:E[now]){
dfs(p);
siz[now]+=siz[p];
if(siz[p]>siz[hson[now]])hson[now]=p;
}
return;
}
#define mp make_pair
inline void dfs2(int now){
if(!hson[now]){
s[now].insert(mp(w[now],now));
return;
}
dfs2(hson[now]);
swap(s[now],s[hson[now]]);
for(auto p:E[now])if(p^hson[now]){
dfs2(p);
for(auto p1:s[p])s[now].insert(p1);
s[p].clear();
}
auto it=s[now].lower_bound(mp(w[now],0));
if(it!=s[now].end())s[now].erase(it);
s[now].insert(mp(w[now],now));
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i],w[i]=1e9-w[i];
for(int i=2;i<=n;i++)cin>>fa[i],E[fa[i]].push_back(i);
dfs(1);
dfs2(1);
cout<<s[1].size();
return 0;
}