A. B-Suffix Array
题意
对于字符串t，有B函数B(t1 t2 … tk ) = b1 b2 … bk 。bi 是 i 前和 ti 相同的字符的最近的位置，如果没有就为0。求将以 t1 开头的每个B函数的结果按照字典序由小到大排序，并输出排序后的原来的编号。
题解
出题人的题解：
• Let C_i = min_{j > i and s_j = s_i} {j - i}
• The B-Suffix Array is equivalent to the suffix array of C_1 C_2 ... C_n
• The B-Suffix Array is equivalent to the suffix array of C_1 C_2 ... C_n
意思是：c[i]的值是索引i后面与s[i]相同的字符的最近的位置，该字符串的后缀数组就等价于c数组的后缀数组，这个结论只适用于只有两个字符的情况，所以题目字符也只有a与b两种。
为了防止两个字符串字典序相等的情况，在c数组的末尾加一个数组长度+1，这样也不会干扰原来的后缀的顺序；
如abaab的c数组为231556，c的后缀为：231556，31556，1556，556，56
所以，sa数组就是31245，反过来54213就是答案了。
另一种做法是不知道这个结论的情况下，可以看下这篇博客，讲的十分详细清楚：https://blog.csdn.net/weixin_43965698/article/details/107304525 。
大体的做法是将字符和 i 前与它相同的字符的最近的位置差记录在数组中，没有的话就为0，最后将这个数组每个数要+1，因为后缀数组最后要加一个=0的结尾。然后用后缀数组求出rank数组。
假设t=“aaaabaaab”, 则B(t)=011102114,前半段为01110。这样，每个后缀子串就都有一个T, B(T)=AD其中A=01..10，对于字典序排序，显然前半段的影响较大，那么将对A进行排序，再对A相同的D进行排序即可。求后缀数组得rank值后，则rank[i+∣Ai∣]即是Di的排名了。
代码
按照出题人的题解
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
//sa:字典序中排第i位的起始位置在str中第sa[i] sa[1~n]为有效值
//rnk:就是str第i个位置的后缀是在字典序排第几 rnk[0~n-1]为有效值
//height：字典序排i和i-1的后缀的最长公共前缀 height[2~n]为有效值，第二个到最后一个
const int INF=0x3f3f3f3f;
const int maxn = 1e6+100;
int wa[maxn],wb[maxn],wsf[maxn],wv[maxn],sa[maxn];
int rnk[maxn],height[maxn];
char s[maxn];
int r[maxn],n;
int cmp(int *r,int a,int b,int k)
{
return r[a]==r[b]&&r[a+k]==r[b+k];
}
void getsa(int *r,int *sa,int n,int m)//n为添加0后的总长
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0; i<m; i++) wsf[i]=0;
for(i=0; i<=n; i++) wsf[x[i]=r[i]]++;
for(i=1; i<m; i++) wsf[i]+=wsf[i-1];
for(i=n; i>=0; i--) sa[--wsf[x[i]]]=i;
p=1;
j=1;
for(; p<=n; j*=2,m=p){
for(p=0,i=n+1-j; i<=n; i++) y[p++]=i;
for(i=0; i<=n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0; i<=n; i++) wv[i]=x[y[i]];
for(i=0; i<m; i++) wsf[i]=0;
for(i=0; i<=n; i++) wsf[wv[i]]++;
for(i=1; i<m; i++) wsf[i]+=wsf[i-1];
for(i=n; i>=0; i--) sa[--wsf[wv[i]]]=y[i];
swap(x,y);
x[sa[0]]=0;
for(p=1,i=1; i<=n; i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++;
}
}
void getheight(int *r,int n)//n为添加0后的总长
{
int i,j,k=0;
for(i=1; i<=n; i++) rnk[sa[i]]=i;
for(i=0; i<n; i++){
if(k)
k--;
else
k=0;
j=sa[rnk[i]-1];
while(r[i+k]==r[j+k])
k++;
height[rnk[i]]=k;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while(cin>>n){
cin>>s;
int a=0,b=0;
for(int i=n-1;i>=0;i--){
if(s[i]=='a'){
if(!a) r[i]=n;
else r[i]=a-i;
a=i;
}
else{
if(!b) r[i]=n;
else r[i]=b-i;
b=i;
}
}
r[n++]=n;
r[n]=0;
getsa(r,sa,n,n+1);
for(int i=n-1;i>=1;i--) cout<<sa[i]+1<<' ';
cout<<endl;
}
return 0;
} 按照巨巨的思路 #include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
//sa:字典序中排第i位的起始位置在str中第sa[i] sa[1~n]为有效值
//rnk:就是str第i个位置的后缀是在字典序排第几 rnk[0~n-1]为有效值
//height：字典序排i和i-1的后缀的最长公共前缀 height[2~n]为有效值，第二个到最后一个
const int INF=0x3f3f3f3f;
const int maxn = 1e6+100;
int wa[maxn],wb[maxn],wsf[maxn],wv[maxn],sa[maxn];
int rnk[maxn],height[maxn];
char s[maxn];
int r[maxn],n;
int cmp(int *r,int a,int b,int k)
{
return r[a]==r[b]&&r[a+k]==r[b+k];
}
void getsa(int *r,int *sa,int n,int m)//n为添加0后的总长
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0; i<m; i++) wsf[i]=0;
for(i=0; i<=n; i++) wsf[x[i]=r[i]]++;
for(i=1; i<m; i++) wsf[i]+=wsf[i-1];
for(i=n; i>=0; i--) sa[--wsf[x[i]]]=i;
p=1;
j=1;
for(; p<=n; j*=2,m=p){
for(p=0,i=n+1-j; i<=n; i++) y[p++]=i;
for(i=0; i<=n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0; i<=n; i++) wv[i]=x[y[i]];
for(i=0; i<m; i++) wsf[i]=0;
for(i=0; i<=n; i++) wsf[wv[i]]++;
for(i=1; i<m; i++) wsf[i]+=wsf[i-1];
for(i=n; i>=0; i--) sa[--wsf[wv[i]]]=y[i];
swap(x,y);
x[sa[0]]=0;
for(p=1,i=1; i<=n; i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++;
for(i=1;i<=n;i++) rnk[sa[i]]=i;
}
}
struct node
{
int x,y;
}p[maxn];
bool cmp2(node a,node b)
{
if(a.y-a.x==b.y-b.x) return rnk[a.y+1]<rnk[b.y+1];
return a.y-a.x<b.y-b.x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while(cin>>n){
cin>>s;
int a=-1,b=-1;
for(int i=0;i<n;i++){
if(s[i]=='a'){
if(a<0) r[i]=0;
else r[i]=i-a;
a=i;
}
else{
if(b<0) r[i]=0;
else r[i]=i-b;
b=i;
}
}
for(int i=0;i<n;i++) r[i]++;
r[n]=0;
getsa(r,sa,n,n+10);
int x=n,y=n;
for(int i=n-1;i>=0;i--){
if(s[i]=='a'){
p[i]={i+1,y};
x=i;
}
else {
p[i]={i+1,x};
y=i;
}
}
rnk[n]=-1;
rnk[n+1]=-2;
sort(p,p+n,cmp2);
for(int i=0;i<n;i++) cout<<p[i].x<<' ';
cout<<endl;
}
return 0;
}
F. Infinite String Coparision
题意
给出两个字符串，比较它们的字典序。
题解
字典序有一个很简单的比较方法，如果两个字符串a和b，a+b>b+a那么说明a>b。按照这个方法就可以不用因为字符串的长度而去一直给字符串循环加长了。
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
string a,b;
while(cin>>a>>b){
string p=a+b,q=b+a;
if(p>q) cout<<">"<<endl;
if(p==q) cout<<"="<<endl;
if(p<q) cout<<"<"<<endl;
}
return 0;
}
J. Easy Integration
题意
给你n，
求这个积分，最后的结果分子是记为p，分母记为q。求（p*q-1）mod 998244353。
题解
比赛完看到巨巨说这是贝塔函数，我一搜还真是。
贝塔函数的递推公式：
但是菜鸡只会打表找规律。那么说说怎么找到的规律吧。
先把所有的分子分母都找到，这个要用到（x-1）^n=C(n,0)x^n(-1)^0+C(n,1)x^(n-1)(-1)^1+C(n,2)x^(n-2)(-1)^2+……+C(n,n)x^0(-1)^n ，(-1)^x 从0到n变成从n到0就变成了 (1-x)^n 的公式了。把分母都输出，发现分母是从(n+1)到(2n+1)连续的数，相乘就是 n! / (2n+1)! 。然后把分式通分，求出所有的分子相加，输出分子的和会发现分子就是 n! 。所以这个分式就是 n!*n! / (2n+1)! 。这里应该会用到费马小定理，拓展欧几里得也可以，我这里用的是费马小定理。
代码
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ft first
#define sd second
using namespace std;
ll fac[2000100],inv[2000100];
const ll mod=998244353;
const ll N=2e6+10;
ll a[1001000],b[1000100];
ll quick(ll a,ll b)
{
ll res=1;
a=a%mod;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res%mod;
}
void init()
{
fac[0]=inv[0]=inv[1]=1;
for(ll i=1;i<=N;i++)
fac[i]=fac[i-1]*i%mod;
for(ll i=2;i<=N;i++)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(ll i=1;i<=N;i++)
inv[i]=inv[i-1]*inv[i]%mod;
}
ll C(ll n,ll m)
{
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
ll n;
while(cin>>n){
/**打表找规律
ll p=0,q=1;
for(ll i=0;i<=n;i++){
a[i]=C(n,i);
b[i]=n-i+n+1;
a[i]%=mod;
b[i]%=mod;
if((n-i)&1) a[i]=-a[i];
q*=b[i];
q%=mod;
cout<<b[i]<<' ';
}
cout<<endl;
for(ll i=0;i<=n;i++){
p+=q*a[i]%mod*quick(b[i],mod-2);
p%=mod;
}
cout<<p<<endl;
ll x=__gcd(p,q);
p/=x,q/=x;
ll ans=(p*quick(q,mod-2))%mod;
cout<<ans<<endl;
**/
ll p=fac[n]*fac[n]%mod;
ll q=fac[2*n+1];
cout<<p*quick(q, mod-2)%mod<<endl;
}
return 0;
}
京公网安备 11010502036488号