前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2020牛客暑期多校训练营(第一场)

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

作者头像
wenzhuan
发布2022-08-15 12:26:04
3020
发布2022-08-15 12:26:04
举报
文章被收录于专栏:你会烧尽还是结冰

7.12 开始就自闭的牛客1

A-B-Suffix Array

题意

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

思路

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

坑点

多组数据,记得清空

代码

代码语言:javascript
复制
#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) ;

考点

公式推导 模逆元 组合数

坑点

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

代码

代码语言:javascript
复制
#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));
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • A-B-Suffix Array
  • J-Easy Integration
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档