2020牛客暑期多校训练营(第一场)

7.12 开始就自闭的牛客1

A-B-Suffix Array

题意

定义数组 $B(s_1s_2…s_k)$ 。对于 $B_i$ 当存在 $j$ 满足 $j<i$ 且 $s_j=s_i$ 时有 $i-max(j)$ ,否则为0。给定串 $S$ ,求 $S$ 每个后缀的 $B$ 函数的字典序

思路

有排序考虑sa。构造一个 $C$ 函数,具体定义和 $B$ 差不多不过从末尾开始。通过 $C$ 函数的后缀排序得到答案。

坑点

多组数据,记得清空

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 1e5 + 5;
const int mod = 998244353;
int s[maxn],len,qwq;
int sa[maxn],rk[maxn];
int height[maxn];
int t1[maxn],t2[maxn],c[maxn];
int best[20][maxn];
char ss[maxn];
void getsa(int *s,int n,int m){
int *x=t1,*y=t2;
rep(i,0,m) c[i]=0;
rep(i,0,n) c[x[i]=s[i]]++;
rep(i,1,m) c[i]+=c[i-1];
dep(i,n-1,0) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1){
int p=0;
rep(i,n-k,n) y[p++]=i;
rep(i,0,n) if(sa[i]>=k) y[p++]=sa[i]-k;
rep(i,0,m) c[i]=0;
rep(i,0,n) c[x[y[i]]]++;
rep(i,1,m) c[i]+=c[i-1];
dep(i,n-1,0) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1; x[sa[0]]=0;
rep(i,1,n) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
if(p>=n) break; m=p;
} rep(i,1,n) rk[sa[i]]=i;
}
struct node{ int f,s,id; }p[maxn];
int cmp(node a,node b){
return a.f==b.f?a.s<b.s:a.f<b.f;
}
int solve(){
scs(ss+1); int a=-1,b=-1;
mst(rk,0); mst(s,0); mst(sa,0);
rep(i,1,len+1){
if(ss[i]=='a') s[i]=a>=0?i-a+1:1,a=i;
else s[i]=b>=0?i-b+1:1,b=i;
} getsa(s+1,len+1,len+1);
a=-1,b=-1; dep(i,len,1){
if(ss[i]=='a') p[i]=b>=0?(node){b-i,rk[b],i}:(node){len-i+1,-1,i},a=i;
else p[i]=a>=0?(node){a-i,rk[a],i}:(node){len-i+1,-1,i},b=i;
} sort(p+1,p+len+1,cmp);
rep(i,1,len+1) pf("%d ",p[i].id);
return pf("\n");
}
int main(){
while(~sc(len)) solve();
}

J-Easy Integration

题意

积分

思路

找规律 式子 $C_{2*n+1}^n *(n+1)$ ;

考点

公式推导 模逆元 组合数

坑点

预处理数组要开两倍(对不起对不起对不起)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
#define pf printf
#define scl(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
const int mod = 998244353;
ll qpow(ll a,ll b,ll mod){
ll ans=1; while(b){
if(b&1) ans=ans*a%mod;
b>>=1; a=a*a%mod;
} return ans;
}
ll n,jc[maxn],inv[maxn];
ll C(int s,int x){
return 1ll*jc[x]*inv[s]%mod*inv[x-s]%mod;
}
int main(){
jc[0]=inv[0]=1; rep(i,1,maxn) jc[i]=1ll*jc[i-1]*i%mod;
inv[maxn-1]=qpow(jc[maxn-1],mod-2,mod);
dep(i,maxn-2,1) inv[i]=1ll*inv[i+1]*(i+1)%mod;
while(~sc(n)) pf("%lld\n",qpow(1ll*(n+1)*C(n,2*n+1)%mod,mod-2,mod));
}