【学习笔记】「JOISC 2022 Day1」错误拼写
久违的字符串计数题。
显然只用考虑 [ i : j ] [i:j] [i:j]这一段拼成的串。不难得出结论：设 n x t i nxt_i nxti表示 i i i之后第一个本质不同的字符的位置，那么 n x t i ≤ j nxt_i\le j nxti≤j，并且 s i ? s n x t i s_i?s_{nxt_i} si?snxti，或者 n x t i > j nxt_i>j nxti>j。
我真傻，真的。这题恶心的地方在于转移，我们希望避免数据结构的使用。
注意到， s i = s i − 1 s_i=s_{i-1} si=si−1始终是一个合法的转移。这意味着， i − 1 i-1 i−1的状态可以直接照搬到 i i i。那么，考虑当 s i < s i − 1 s_i<s_{i-1} si<si−1时，假设 s i s_i si的连续段到了 k k k，那么只需满足不存在 k ≤ l < i ， r ≥ i k\le l<i，r\ge i k≤l<i，r≥i，并且 s i > s i − 1 s_i>s_{i-1} si>si−1的限制 [ l , r ] [l,r] [l,r]。显然 k k k的取值范围是一段后缀，可以前缀和解决。当然还应该满足 s k ≠ s k − 1 s_k\ne s_{k-1} sk=sk−1，这可以通过修改 d p dp dp状态定义来解决。这道题就做完了。
复杂度 O ( 26 n ) O(26n) O(26n)。
代码咕的有点儿久，但还是来了。
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod=1e9+7;
const int N=5e5+5;
int n,m;
ll sub[N][26],isub[N][26];
vector<pair<int,int>>G[N];
multiset<int>s1,s2;
void add(ll &x,ll y){x=(x+y)%mod;}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
if(l<r){
G[r].pb({l,0});
s1.insert(l);
}
else{
G[l].pb({r,1});
s2.insert(r);
}
}
for(int i=0;i<26;i++)sub[1][i]=i+1;
for(int i=0;i<26;i++)isub[1][i]=26-i;
for(int i=2;i<=n;i++){
for(auto x:G[i-1]){
if(x.se==0){
s1.erase(s1.find(x.fi));
}
else{
s2.erase(s2.find(x.fi));
}
}
auto it=s1.lower_bound(i);
int lmax=(it!=s1.begin())?(*--it):0;
for(int j=1;j<26;j++){
add(sub[i][j],sub[i-1][j-1]-sub[lmax][j-1]);
add(isub[i][j],sub[i-1][j-1]-sub[lmax][j-1]);
}
it=s2.lower_bound(i);
lmax=(it!=s2.begin())?(*--it):0;
for(int j=0;j<25;j++){
add(sub[i][j],isub[i-1][j+1]-isub[lmax][j+1]);
add(isub[i][j],isub[i-1][j+1]-isub[lmax][j+1]);
}
for(int j=1;j<26;j++)add(sub[i][j],sub[i][j-1]);
for(int j=24;j>=0;j--)add(isub[i][j],isub[i][j+1]);
for(int j=0;j<26;j++){
add(sub[i][j],sub[i-1][j]);
add(isub[i][j],isub[i-1][j]);
}
}
cout<<(sub[n][25]+mod)%mod;
}