省流：\(100 + 100 + 100 + 5\)。
T1
题意：给一个括号序列 \(s\)，求出长度最小的 \(s\) 的子序列 \(t\)，满足 \(t\) 是合法括号序列且删掉 \(t\) 后 \(s\) 是一个特殊的序列。定义特殊的序列为长度 \(2n\)，前 \(n\) 个都是 (，后 \(n\) 个都是 )。
\(n \leq 3 \times 10^6\)。
可以枚举特殊序列左右括号的分界点，有个比较显然的贪心就是往左一个一个加入左括号看合不合法，往右一个一个加入右括号看合不合法。这具有单调性，所以可以双指针。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5;
string s;
int a[N],l[N],r[N];
bool check() {
int sum=0;
for(int i=0; i<s.size(); i++) {
sum+=(s[i]=='(');
sum-=(s[i]==')');
if(sum<0) return false;
}
return sum==0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>s;int n=s.size();
if(!check()) return cout<<-1,0;
int tot=0,pos=1,sum1=0,sum2=0;
for(int i=0; i<n-1; i++) {
if(s[i]=='(') a[++tot]=0;
else a[tot]++,sum2++;
while(pos<=tot&&sum1<sum2) {
sum1+=(a[pos]==0);
sum2-=a[pos];
pos++;
}
l[i]=tot-pos+1;
}
tot=sum1=sum2=0;pos=1;
for(int i=n-1; i>0; i--) {
if(s[i]==')') a[++tot]=0;
else a[tot]++,sum2++;
while(pos<=tot&&sum1<sum2) {
sum1+=(a[pos]==0);
sum2-=a[pos];
pos++;
}
r[i-1]=tot-pos+1;
}
int ans=0;
for(int i=0; i<n-1; i++) ans=max(ans,min(l[i],r[i]));
cout<<n-2*ans;
return 0;
}
T2
原题：AT_cf17_final_g。
最优策略：每次选取第⼀个 \(a_i = i\) 的位置，然后操作，这样不会破坏已经可以操作的位置的性质，同时可以尽可能多地操作。
分析发现，每次操作会把整个序列的总和 \(-1\)。所以可以考虑计算出所有不同初始值下 \(-i\) 的方案数总和。本质上就是计算出了所有情况下减去的总和。再用所有方案数的总和减去这个方案数就得到最终所有情况的答案。
而每个点只会被后⾯的点操作，于是我们倒着 dp，记 \(dp_{i,j}\) 表示到了第 \(i\) 位，它后面的位置总共对它造成了 \(j\) 次 \(+1\) 的操作”的方案数，然后我们枚举第 \(i\) 位的初始值 \(x\)，如果可以操作那么⼀定可以在 \(i\) 处操作了 \(\lfloor \frac{x + j}{i} \rfloor\) 次操作，可以操作代表的是初始值 \(\leq i\)。那么最后怎么统计答案呢？发现 \(dp_{1,i}\)，也就是 \(1\) 被 \(+1\) 的次数为i时，总体是⼀共做了 \(i\) 次总和 \(-1\)，所以所有减去的 \(1\) 的总和就是 \(\sum dp_{1,i} \times i\)。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105,p=1e9+7;
int n,k,dp[N][N*N],ans=0;
int qpow(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
signed main() {
cin>>n>>k;
dp[k][0]=k,dp[k][1]=1;
for(int i=k; i>1; i--) {
for(int j=0; j<=k*k; j++) {
for(int l=0; l<i; l++) if(j+(l+j)/(i-1)<=k*k) (dp[i-1][j+(l+j)/(i-1)]+=dp[i][j])%=p;
(dp[i-1][j]+=dp[i][j]*(k-i+1)%p)%=p;
}
}
for(int i=1; i<=n; i++) (ans+=k*(k+1)/2*qpow(k+1,n-1)%p)%=p;
for(int i=0; i<=k*k; i++) (ans+=-dp[1][i]*i%p*qpow(k+1,n-k)%p+p)%=p;
cout<<ans;
return 0;
}
T3
原题：CF177G2。
对于 \(n \leq 28\)，直接暴力做就行。接下来讨论 \(n > 28\) 的情况。
对于一个字符串，设它在 \(f_i\) 的出现次数为 \(g_i\)，那么有 \(g_i = g_{i - 1} + g_{i - 2} + x\)，\(x\) 表示这个字符串在 \(f_i\) 出现次数减 \(f_{i - 1}\) 出现次数减 \(f_{i - 2}\) 出现次数，即跨越 \(f_{i - 1}\) 和 \(f_{i - 2}\) 的出现次数。观察一下，发现 \(i\) 为奇数时，\(f_i\) 可以被表示为 \(\cdots + f_{26} + f_{26} + \cdots\)，最中间的即为 \(f_{i - 1}\) 和 \(f_{i - 2}\) 的分界点；当 \(i\) 为偶数时，\(f_i\) 可以被表示为 \(\cdots + f_{27} + f_{26} + \cdots\)，分界点同理。由于 \(f_{26}\) 已经大于 \(10^5\) 了，所以 \(x\) 只分奇数和偶数两种取值，算出这两种取值按照上面的递推式矩阵快速幂优化即可。
暴力和算 \(x\) 我用了 ACM 解决。好像可以用其他的，应该是我赛时唐了。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,p=1e9+7;
string s[N];
int n,q,tot=0,ch[N][2],fl[N],cnt[N],id[N],head[N],ecnt=0;
struct node {int to,nxt;}e[N];
void addedge(int u,int v) {e[++ecnt]=(node){v,head[u]};head[u]=ecnt;}
struct matrix {
int c[6][6];
matrix operator*(const matrix &o) const {
matrix x;
memset(x.c,0,sizeof(x.c));
for(int i=1; i<=5; i++)
for(int j=1; j<=5; j++)
for(int k=1; k<=5; k++)
x.c[i][j]=(x.c[i][j]+c[i][k]*o.c[k][j]%p)%p;
return x;
}
}a,ans[N];
matrix qpow(matrix a,int b) {
matrix ans;
memset(ans.c,0,sizeof(ans.c));
for(int i=1; i<=5; i++) ans.c[i][i]=1;
while(b) {
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
void add(string s,int ii) {
int cur=0;
for(int i=0; i<s.size(); i++) {
int b=s[i]-'0';
if(!ch[cur][b]) ch[cur][b]=++tot;
cur=ch[cur][b];
}
id[ii]=cur;
}
void build_fail() {
queue<int> q;
for(int i=0; i<2; i++) if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=0; i<2; i++) {
if(ch[u][i]) fl[ch[u][i]]=ch[fl[u]][i],q.push(ch[u][i]);
else ch[u][i]=ch[fl[u]][i];
}
}
}
void query(string t) {
int cur=0;
for(int i=0; i<t.size(); i++) {
int b=t[i]-'0';
cur=ch[cur][b];
cnt[cur]++;
}
}
void dfs(int u) {
for(int i=head[u]; i; i=e[i].nxt) {
int v=e[i].to;
dfs(v);cnt[u]+=cnt[v];
}
}
string make(int lim) {
string s1="0",s2="1",s3;
for(int i=3; i<=lim; i++) {
s3=s2+s1;
s1=s2,s2=s3;
}
return s3;
}
void init1() {
a.c[1][1]=0,a.c[1][2]=0,a.c[1][3]=0,a.c[1][4]=0,a.c[1][5]=0;
a.c[2][1]=0,a.c[2][2]=1,a.c[2][3]=1,a.c[2][4]=0,a.c[2][5]=0;
a.c[3][1]=1,a.c[3][2]=1,a.c[3][3]=2,a.c[3][4]=0,a.c[3][5]=0;
a.c[4][1]=0,a.c[4][2]=1,a.c[4][3]=1,a.c[4][4]=1,a.c[4][5]=0;
a.c[5][1]=0,a.c[5][2]=0,a.c[5][3]=1,a.c[5][4]=0,a.c[5][5]=1;
}
void init2(string t,int ii) {
query(t);dfs(0);
for(int i=1; i<=q; i++) ans[i].c[1][ii]+=cnt[id[i]];
memset(cnt,0,sizeof(cnt));
}
signed main() {
freopen("fib.in","r",stdin);
freopen("fib.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>q;
for(int i=1; i<=q; i++) cin>>s[i],add(s[i],i);
build_fail();
for(int i=1; i<=tot; i++) addedge(fl[i],i);
if(n<=28) {
string t=make(n);
query(t);dfs(0);
for(int i=1; i<=q; i++) cout<<cnt[id[i]]<<'\n';
} else {
string t1=make(26),t2=make(27),t3=make(28);
init1(),init2(t1,1),init2(t2,2),init2(t3,3),init2(t1+t1,4),init2(t2+t1,5);
for(int i=1; i<=q; i++) ans[i].c[1][4]-=2*ans[i].c[1][1],ans[i].c[1][5]-=ans[i].c[1][1]+ans[i].c[1][2];
matrix tmp=qpow(a,(n-27)/2);
for(int i=1; i<=q; i++) {
ans[i]=ans[i]*tmp;
if(n&1) cout<<ans[i].c[1][2]<<'\n';
else cout<<ans[i].c[1][3]<<'\n';
}
}
return 0;
}
T4
原题：P6305。
洛谷题解讲的挺好，不写了，其实是懒得写。
代码：
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=4e5+5;
vector<int> ve;
int n,s,a[N],b[N],c[N],vis[N],vise[N],nxt[N],head[N],ecnt=0;
struct node {int to,nxt;}e[N];
void add(int u,int v) {e[++ecnt]=(node){v,head[u]};head[u]=ecnt;}
void dfs(int u) {
for(int& i=head[u]; i; i=e[i].nxt) {
int v=e[i].to;
if(vise[i]) continue;
vise[i]=true,dfs(v);
}
if(u<=n) ve.push_back(u),vis[u]=true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>s;
for(int i=1; i<=n; i++) cin>>a[i],b[i]=a[i];
sort(b+1,b+n+1);
int len=unique(b+1,b+n+1)-b-1;
for(int i=1; i<=n; i++) a[i]=lower_bound(b+1,b+len+1,a[i])-b,c[i]=a[i];
sort(c+1,c+n+1);
for(int i=1; i<=n; i++) {
if(a[i]==c[i]) continue;
add(i,n+a[i]);add(n+c[i],i);
}
vector<vector<int>> tmp;
for(int i=1; i<=n; i++) {
if(vis[i]||a[i]==c[i]) continue;
ve.clear();dfs(i);
ve.pop_back();s-=ve.size();
reverse(ve.begin(),ve.end());
tmp.push_back(ve);
}
if(s<0) return cout<<-1,0;
if(!tmp.size()) return cout<<0,0;
if(tmp.size()==1) {
cout<<1<<endl<<tmp[0].size()<<endl;
for(int i=0; i<tmp[0].size(); i++) cout<<tmp[0][i]<<" ";
return 0;
}
if(s>=tmp.size()) {
cout<<2<<endl;
cout<<tmp.size()<<endl;
for(int i=0; i<tmp.size(); i++) cout<<tmp[i][0]<<" ";
cout<<endl;
int sum=0;
for(int i=0; i<tmp.size(); i++) sum+=tmp[i].size();
cout<<sum<<endl;
for(int i=0; i<tmp.size(); i++) {
for(int j=1; j<tmp[i].size(); j++) nxt[tmp[i][j]]=tmp[i][(j+1)%tmp[i].size()];
nxt[tmp[i][0]]=tmp[(i-1+tmp.size())%tmp.size()][1];
}
int cur=tmp[0][0];
do cout<<cur<<" ",cur=nxt[cur]; while(cur!=tmp[0][0]);
} else {
cout<<tmp.size()-max(0,s-1)+(s>=2)<<endl;
if(s>=2) {
cout<<s<<endl;
for(int i=0; i<s; i++) cout<<tmp[i][0]<<" ";
cout<<endl;
int sum=0;
for(int i=0; i<s; i++) sum+=tmp[i].size();
cout<<sum<<endl;
for(int i=0; i<s; i++) {
for(int j=1; j<tmp[i].size(); j++) nxt[tmp[i][j]]=tmp[i][(j+1)%tmp[i].size()];
nxt[tmp[i][0]]=tmp[(i-1+s)%s][1];
}
int cur=tmp[0][0];
do cout<<cur<<" ",cur=nxt[cur]; while(cur!=tmp[0][0]);
cout<<endl;
}
for(int i=(s==1?0:s); i<tmp.size(); i++) {
cout<<tmp[i].size()<<endl;
for(int j=0; j<tmp[i].size(); j++) cout<<tmp[i][j]<<" ";
cout<<endl;
}
}
return 0;
}