\(T1\) : 宇宙飞船
题目大意：
给定飞船坐标，相邻飞船连绳，交换飞船使绳子不相交，捄最多有多少不用移动
思路：
没啥好说的，skyh都没A
性质很裸，构造合法序列，每一次只能选最大值（值指坐标）或最小值
因为要是当前选了次大或次小值，那么下次选最大最小值时一定会与当前绳相交
因此枚举每一个点作为合法序列的最后一个值
那么这个新构造出的序列就分为一个严格上升和严格下降的序列，且结尾都是当前枚举的最后一个值
如,\(n=6\)，枚举的最后一个值为\(4\)，那么前面一定有：\(1\) \(2\) \(3\)和 \(6\) \(5\)两个序列，可以不连续
因为每次必选最大最小值，所以选完最大值，最大值会-1，同理最小值+1
考虑构造的序列与当前序列的区别，如果有顺序不符严格上升下降的点就需要交换，没有就需要从这个点后面调过来
即顺序符合上升下降就可以不用留在原地
所以直接求出以当前点为结尾的最长上升子序列和最长下降子序列，相加-1即为答案
代码：
int n,m,a[maxn],ans,f[maxn],low[maxn],tot;
#define mid ((l+r)>>1)
int Binary(int l,int r,int key){
while(l<=r){
if(low[mid]>=key)l=mid+1;
else r=mid-1;
}
return l;
}
int main(){
freopen("spaceship.in","r",stdin);
freopen("spaceship.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)a[i]=read();
low[++tot]=a[1];
for(int i=2;i<=n;i++){
if(a[i]>=low[tot])low[++tot]=a[i],f[i]=tot;
else {
int id=lower_bound(low+1,low+1+tot,a[i])-low;
low[id]=a[i];f[i]=id;
}
}
memset(low,0,sizeof(low));
low[tot=1]=a[1];
for(int i=2;i<=n;i++){
if(a[i]<=low[tot])low[++tot]=a[i],f[i]+=tot-1;
else {
int id=Binary(1,tot,a[i]);
low[id]=a[i];
f[i]+=id-1;
}
ans=max(ans,f[i]);
}
cout<<ans<<endl;
return 0;
}
\(T2\)：路径计数
题目大意：
思路：
暴力做法是暴力建边跑拓扑
打表发现：
- 所有字符都相同方案数为：\(n\)
- 相邻字符都不同方案数为：\(2^n-1\)
墸一分析
相邻字符都不同，能走到的路径是类二叉树（这里最下层的字符虽然相同，但是路径不同），因为深度是\(n\)，所以方案数为:\(2^n-1\)
所有字符都相同，能走到的路径是链状的，所以是\(n\)
所以对于所有情况，算重的部分是相同字符串
用全集减去相同字符串当前的贡献加上相同字符串原本的贡献就是答案
即：
\[ans=2^n-1-柿子1+柿子2 \]柿子1是相同字符串当前的贡献，柿子2是相同字符串原本的贡献
考虑每一部分
第一部分：
先明确一个东西：
记当前串左边有\(x\)个字符，右边有\(y\)个字符，那么由整串\(s\)走到当前串的方案数为\((_x^{x+y})\)
证明：可以想象成走矩阵，每次可以左侧走一或右侧走一
所以考虑当前串每一个串的贡献，累加得到：
\[\sum_{i=0}^{len-1}\sum_{j=0}^{len-1-i}\binom{x+i+y+j}{x+i} \]\(i\)\(j\)分别表示左右向内延展的长度
发现每一项组合数下标都是\(x+i\)
应用杨辉三角的性质：
\[\sum_{i=0}^{n}\binom{x}{i}=\binom{x+1}{i+1} \]（证明：\(f_i^j=f_{i-1}^j+f_{i-1}^{j-1}\)，然后裂项相消）
所以化简为(用前缀和相减)：
\[\sum_{i=0}^{len-1}\left ( \binom{x+y+len}{x+1}-\binom{x+y+i}{x+1}\right ) \]第二部分：
当前相同串只有前后缀有贡献，贡献为前后缀长度
整个相同串的贡献为\(len\)，整串\(s\)走到相同串的方案数为\(\binom{x+y}{x}\)，总贡献为\(len\times \binom{x+y}{x}\)
考虑前后缀：
前缀\(x,x+len-i-1\)要从\(x-1,x+len-i-1\)转移过来，前缀贡献为\(len-i\)，方案数为到达\(x-1,x+len-i-1\)的方案数为\((len-i)\times \binom{x+y+i-1}{x-1}\)，后缀同理
代码：
/* cinput
aabbbbbaaabbbbbbbaaa
*/
#include<bits/stdc++.h>
#define re register
#define ll long long
#define gc getchar()
#define getch while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=gc;}
#define getnu while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=gc;}
using namespace std;
inline ll read(){ll s=0,f=1;char ch=gc;getch;getnu;return s*f;}
const int p=998244353;
const int N=5e5+10;
int ine[N],f[N],fac[N];
char s[N];
void pre(){
f[0]=fac[0]=ine[1]=1;
for(re int i=1;i<=N-5;i++)fac[i]=1ll*fac[i-1]*i%p;
for(re int i=2;i<=N-5;i++)ine[i]=1ll*(p-p/i)*ine[p%i]%p;
for(re int i=1;i<=N-5;i++)f[i]=1ll*f[i-1]*ine[i]%p;
}
ll qpow(ll a,ll b,ll res=1){
while(b){
if(b&1)res=res*a%p;
a=a*a%p;b>>=1;
}
return res;
}
ll C(ll n,ll m){
if(!m||n==m)return 1;
return 1ll*fac[n]*f[m]%p*f[n-m]%p;
}
int main(){
freopen("counting.in","r",stdin);
freopen("counting.out","w",stdout);
pre();
scanf("%s",s+1);
int n=strlen(s+1);
ll ans=qpow(2,n)-1;
for(int i=1;i<=n;){
int id=0;
for(int j=i+1;j<=n;j++)if(s[j]!=s[i]){id=j-1;break;}
if(!id)id=n;
int len=id-i+1;
if(len==1)continue;
int x=i-1,y=n-id;
ll sum=0;
for(int j=0;j<=len-1;j++)sum=((sum+C(x+y+len,x+j+1))%p-C(x+y+j,x+j+1)+p)%p;
ans=((ans-sum)%p+p)%p;
ans=(ans+len*C(x+y,x))%p;
for(int j=1;j<=len-1;j++)ans=(ans+1ll*(len-j)*((C(x+y+j-1,x-1)+C(x+y+j-1,y-1))%p)%p)%p;
i=id+1;
}
printf("%lld\n",ans);
}