首页 > 其他分享 >【考后总结】7 月多校国赛模拟赛 1

【考后总结】7 月多校国赛模拟赛 1

时间：2023-07-02 21:57:35浏览次数：34  
标签：校国赛 ch return 考后 int res pos maxn 模拟

7.2 冲刺国赛自测 9

T1 字符串

一个合法位置 \([l,r]\) 代表 \([1,x]\) 与 \([l,l+x-1]\) 相同，\([y,n]\) 与 \([r-y+1,r]\) 相同，类似 \(x\in \mathrm{Border}(l+x-1)\)。

对正反串做 KMP，建失配树，类似要求 \(x\) 子树和 \(y\) 子树的交，而 \((l+x-1)+1=(r-y+1)\) 所以正串失配树子树里节点 \(u\) 对应反串失配树子树里节点 \(n-u\)，二维数点即可。

点击查看代码 
int rt[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
    int ch[maxn*40][2],tot;
    int siz[maxn*40];
    inline void clear(){
        tot=0;
        memset(ch,0,sizeof(ch));
        memset(siz,0,sizeof(siz));
    }
    inline void new_node(int &pos){
        ch[++tot][0]=ch[pos][0],ch[tot][1]=ch[pos][1],siz[tot]=siz[pos];
        pos=tot;
    }
    void insert(int &pos,int l,int r,int p){
        new_node(pos);
        ++siz[pos];
        if(l==r) return;
        if(p<=mid) insert(ch[pos][0],l,mid,p);
        else insert(ch[pos][1],mid+1,r,p);
    }
    int query(int lpos,int rpos,int l,int r,int pl,int pr){
        if(pl<=l&&r<=pr) return siz[rpos]-siz[lpos];
        int res=0;
        if(pl<=mid) res+=query(ch[lpos][0],ch[rpos][0],l,mid,pl,pr);
        if(pr>mid) res+=query(ch[lpos][1],ch[rpos][1],mid+1,r,pl,pr);
        return res;
    }
#undef mid
}S;

int t;
int n,q;
char s1[maxn],s2[maxn];
int nxt1[maxn],nxt2[maxn];
vector<int> E1[maxn],E2[maxn];
int fa1[maxn],siz1[maxn],dfn1[maxn],dfncnt1;
int fa2[maxn],siz2[maxn],dfn2[maxn],dfncnt2;
int id[maxn];
inline void get_nxt(){
    nxt1[1]=0;
    E1[0].push_back(1);
    for(int i=2,j=0;i<=n;++i){
        while(j&&s1[i]!=s1[j+1]) j=nxt1[j];
        if(s1[i]==s1[j+1]) ++j;
        nxt1[i]=j;
        E1[j].push_back(i);
    }
    nxt2[1]=0;
    E2[0].push_back(1);
    for(int i=2,j=0;i<=n;++i){
        while(j&&s2[i]!=s2[j+1]) j=nxt2[j];
        if(s2[i]==s2[j+1]) ++j;
        nxt2[i]=j;
        E2[j].push_back(i);
    }
}
void dfs1(int u,int f){
    fa1[u]=f,siz1[u]=1;
    if(u) dfn1[u]=++dfncnt1,id[dfn1[u]]=u;
    for(int v:E1[u]){
        if(v==f) continue;
        dfs1(v,u);
        siz1[u]+=siz1[v];
    }
}
void dfs2(int u,int f){
    fa2[u]=f,siz2[u]=1;
    if(u) dfn2[u]=++dfncnt2;
    for(int v:E2[u]){
        if(v==f) continue;
        dfs2(v,u);
        siz2[u]+=siz2[v];
    }
}

int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    t=read();
    while(t--){
        n=read(),q=read();
        for(int i=0;i<=n;++i){
            nxt1[i]=nxt2[i]=0;
            E1[i].clear(),E2[i].clear();
            dfncnt1=dfncnt2=0;
            fa1[i]=siz1[i]=dfn1[i]=fa2[i]=siz2[i]=dfn2[i]=0;
        }
        S.clear();
        scanf("%s",s1+1);
        for(int i=1;i<=n;++i) s2[i]=s1[n-i+1];
        get_nxt();
        dfs1(0,0);
        dfs2(0,0);
        rt[0]=0;
        for(int i=1;i<=n;++i){
            int j=dfn2[n-id[i]];
            rt[i]=rt[i-1];
            if(j) S.insert(rt[i],1,n,j);
        }
        while(q--){
            int x=read(),y=read();
            printf("%d\n",S.query(rt[dfn1[x]-1],rt[dfn1[x]+siz1[x]-1],1,n,dfn2[y],dfn2[y]+siz2[y]-1));
        }
    }
    return 0;
}

T2 计树

魔幻转化是枚举 \(x\in [1,n)\)，令 \(p_i=[p_i>x]\)，求所有 \(p\) 中相邻位置不同的个数和就是答案，正确性在于 \(p_i=a,p_{i+1}=b\ (a<b)\) 时，\(p_i\neq p_{i+1}\) 恰好为 \(x\in [a,b)\)，贡献就是 \(b-a\)。

考虑 DP，目标是子树内构成 \(p\) 的子序列中某两个相邻不同的方案数，同时需要维护出每个位置上 \(0/1\) 的方案数，也需要维护出子树内方案总数。

设 \(f_u\) 为 \(u\) 子树内合法 \(p\) 序列方案数，\(g_{u,k,0/1}\) 为 \(u\) 子树内 \(p_k=0/1\) 的方案数，\(h_{u,k}\) 为 \(u\) 子树内 \(p_k\neq p_{k+1}\) 的方案数。

\(f\) 转移不断乘 \(f_v\) 和组合数即可。

\(g\) 转移讨论 \(k\) 来自已经合并过的子树或是 \(v\)，其余位置的排布方案乘组合数。

\(h\) 讨论同理，更复杂一点需要讨论 \(k\) 与 \(k+1\) 分别来自哪里，方案依旧是组合数。

转移精细实现复杂度是树上背包 \(O(n^2)\)。

根据题意，\(p\) 序列第一个元素一定是 \(u\)，所以 \(p_1\) 实际根据 \(x\) 固定，最后把 \(u\) 加进去时先向右平移，再算 \(1\) 处值即可。

点击查看代码 
inline int q_pow(int A,int B,int P){
    int res=1;
    while(B){
        if(B&1) res=1ll*res*A%P;
        A=1ll*A*A%P;
        B>>=1;
    }
    return res;
}

int n,rt;
vector<int> E[maxn];

int fact[maxn],inv_fact[maxn];
inline int C(int N,int M){
    if(N<M) return 0;
    return 1ll*fact[N]*inv_fact[M]%mod*inv_fact[N-M]%mod;
}

int siz[maxn];
int f[maxn],g[maxn][maxn][2],h[maxn][maxn],tmpg[maxn][2],tmph[maxn];
void dfs(int u,int fa,int x){
    f[u]=1;
    for(int v:E[u]){
        if(v==fa) continue;
        dfs(v,u,x);
        for(int i=1;i<=siz[u]+siz[v];++i) tmpg[i][0]=tmpg[i][1]=0,tmph[i]=0;
        for(int i=0;i<=siz[u];++i){
            for(int j=0;j<=siz[v];++j){
                if(i){
                    tmpg[i+j][0]=(tmpg[i+j][0]+1ll*g[u][i][0]*f[v]%mod*C(i+j-1,j)%mod*C(siz[u]+siz[v]-(i+j),siz[v]-j)%mod)%mod;
                    tmpg[i+j][1]=(tmpg[i+j][1]+1ll*g[u][i][1]*f[v]%mod*C(i+j-1,j)%mod*C(siz[u]+siz[v]-(i+j),siz[v]-j)%mod)%mod;
                }
                if(j){
                    tmpg[i+j][0]=(tmpg[i+j][0]+1ll*f[u]*g[v][j][0]%mod*C(i+j-1,j-1)%mod*C(siz[u]+siz[v]-(i+j),siz[v]-j)%mod)%mod;
                    tmpg[i+j][1]=(tmpg[i+j][1]+1ll*f[u]*g[v][j][1]%mod*C(i+j-1,j-1)%mod*C(siz[u]+siz[v]-(i+j),siz[v]-j)%mod)%mod;
                }
            }
        }
        for(int i=0;i<=siz[u];++i){
            for(int j=0;j<=siz[v];++j){
                if(i&&i<siz[u]){
                    tmph[i+j]=(tmph[i+j]+1ll*h[u][i]*f[v]%mod*C(i+j-1,j)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-j)%mod)%mod;
                }
                if(j&&j<siz[v]){
                    tmph[i+j]=(tmph[i+j]+1ll*f[u]*h[v][j]%mod*C(i+j-1,j-1)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-(j+1))%mod)%mod;
                }
                if(i&&j<siz[v]){
                    tmph[i+j]=(tmph[i+j]+1ll*g[u][i][0]*g[v][j+1][1]%mod*C(i+j-1,j)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-(j+1))%mod)%mod;
                    tmph[i+j]=(tmph[i+j]+1ll*g[u][i][1]*g[v][j+1][0]%mod*C(i+j-1,j)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-(j+1))%mod)%mod;
                }
                if(i<siz[u]&&j){
                    tmph[i+j]=(tmph[i+j]+1ll*g[u][i+1][0]*g[v][j][1]%mod*C(i+j-1,j-1)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-j)%mod)%mod;
                    tmph[i+j]=(tmph[i+j]+1ll*g[u][i+1][1]*g[v][j][0]%mod*C(i+j-1,j-1)%mod*C(siz[u]+siz[v]-(i+j+1),siz[v]-j)%mod)%mod;
                }
            }
        }
        f[u]=1ll*f[u]*f[v]%mod*C(siz[u]+siz[v],siz[v])%mod;
        siz[u]+=siz[v];
        for(int i=1;i<=siz[u];++i) g[u][i][0]=tmpg[i][0],g[u][i][1]=tmpg[i][1],h[u][i]=tmph[i];
    }
    ++siz[u];
    for(int i=siz[u];i>1;--i) g[u][i][0]=g[u][i-1][0],g[u][i][1]=g[u][i-1][1],h[u][i]=h[u][i-1];
    int now=(u>x);
    g[u][1][0]=g[u][1][1]=h[u][1]=0;
    g[u][1][now]=f[u];
    h[u][1]=g[u][2][now^1];
}

int ans;

int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n=read(),rt=read();
    fact[0]=1;
    for(int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%mod;
    inv_fact[0]=1,inv_fact[n]=q_pow(fact[n],mod-2,mod);
    for(int i=n-1;i>=1;--i) inv_fact[i]=1ll*inv_fact[i+1]*(i+1)%mod;
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        E[u].push_back(v);
        E[v].push_back(u);
    }
    for(int x=1;x<n;++x){
        memset(siz,0,sizeof(siz));
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        memset(h,0,sizeof(h));
        dfs(rt,0,x);
        for(int i=1;i<n;++i) ans=(ans+h[rt][i])%mod;
    }
    printf("%d\n",ans);
    return 0;
}

T3 数论

不妨把每个 \(p_i\) 和 \(a_j\) 全部拆开，改为 \(p_i\) 在 \(a_j\) 的次数是 \(c_{i,j}\) 且 \(\sum_{i,j} c_{i,j}=N\)。

答案就可以写成：

\[\sum_{\sum_{i,j} c_{i,j}=N}\prod_{i=1}^n\prod_{j=1}^m [c_{i,j}=0]+[c_{i,j}>0](p_i-1)p_i^{c_{i,j}-1} \]

\(\sum_{i,j} c_{i,j}=N\) 容易想到生成函数，那么 \(F_i(x)\) 对应质数 \(p_i\)，则：

\[F_i(x)=1+\sum_{k\ge 1} (p_i-1)p_i^{c_{i,j}-1} \]

求封闭形式，得到：

\[F_i(x)=\dfrac{1-x}{1-p_ix} \]

最终要求：

\[[x^N]\prod_{i=1}^n F_i(x)^m=[x^N]\left(\dfrac{\prod_{i=1}^n (1-x)}{\prod_{i=1}^n (1-p_ix)}\right)^m \]

可以分治乘+快速幂，最后得到一个形如 \([x^N]\dfrac{f(x)}{g(x)}\) 的结果，Bostan-Mori 算法解决，复杂度 \(O(n\log n\log N)\)。

点击查看代码 
inline int q_pow(int A,int B,int P){
    int res=1;
    while(B){
        if(B&1) res=1ll*res*A%P;
        A=1ll*A*A%P;
        B>>=1;
    }
    return res;
}

int rev[maxn];
int base,w[maxn];
struct Poly{
    const static int g=3;
    const static int inv_g=332748118;
    int deg;
    vector<ull> f;
    ull& operator[](const int &i){return f[i];}
    ull operator[](const int &i)const{return f[i];}
    inline void set(int L){deg=L;f.resize(L);}
    inline void clear(int L,int R){for(int i=L;i<=R;++i)f[i]=0;}
    inline void output(int L){for(int i=0;i<L;++i)printf("%llu ",f[i]);printf("\n");}
    inline void NTT(int L,bool type){
        set(L);
        for(int i=1;i<L;++i){
            rev[i]=(rev[i>>1]>>1)+(i&1?L>>1:0);
            if(i<rev[i]) swap(f[i],f[rev[i]]);
        }
        for(int d=1;d<L;d<<=1){
            base=q_pow(type?g:inv_g,(mod-1)/(2*d),mod);
            w[0]=1;
            for(int i=1;i<d;++i) w[i]=1ll*w[i-1]*base%mod;
            for(int i=0;i<L;i+=d<<1){
                for(int j=0;j<d;++j){
                    ull x=f[i+j],y=f[i+d+j]*w[j]%mod;
                    f[i+j]=x+y,f[i+d+j]=x-y+mod;
                }
            }
        }
        for(int i=0;i<L;++i) f[i]%=mod;
        if(!type){
            int inv_L=q_pow(L,mod-2,mod);
            for(int i=0;i<L;++i) f[i]=f[i]*inv_L%mod;
        }
    }
    inline Poly Pow(int k){
        Poly res=(*this),base=(*this);
        --k;
        int L=deg;
        while(k){
            L<<=1;
            base.NTT(L,1);
            if(k&1){
                res.NTT(L,1);
                for(int i=0;i<L;++i) res[i]=res[i]*base[i]%mod;
                res.NTT(L,0);
            }
            for(int i=0;i<L;++i) base[i]=base[i]*base[i]%mod;
            base.NTT(L,0);
            k>>=1;
        }
        return res;
    }
};

int a[maxn];

Poly Conquer(int l,int r){
    if(l==r){
        Poly F;
        F.set(2);
        F[0]=1ull,F[1]=(ull)mod-a[l];
        return F;
    }
    int mid=(l+r)>>1;
    Poly F=Conquer(l,mid),G=Conquer(mid+1,r);
    int L=1;
    while(L<=(r-l+1)) L<<=1;
    Poly H;
    H.set(L);
    F.NTT(L,1),G.NTT(L,1);
    for(int i=0;i<L;++i) H[i]=F[i]*G[i]%mod;
    H.NTT(L,0);
    return H;
}

inline void Bostan_Mori(int N,Poly F,Poly G){
    int L=F.deg;
    Poly H,A,B;
    F.set(L<<1),G.set(L<<1),H.set(L<<1),A.set(L<<1),B.set(L<<1);
    while(N){
        H=G;
        for(int i=1;i<L;i+=2) H[i]=mod-H[i];
        F.NTT(L<<1,1),G.NTT(L<<1,1),H.NTT(L<<1,1);
        for(int i=0;i<L<<1;++i) A[i]=F[i]*H[i]%mod,B[i]=G[i]*H[i]%mod;
        A.NTT(L<<1,0),B.NTT(L<<1,0);
        for(int i=0;i<L;++i) B[i]=B[i*2];
        for(int i=0;i<L;++i) A[i]=A[2*i+(N&1)];
        A.clear(L,(L<<1)-1),B.clear(L,(L<<1)-1);
        F=A,G=B;
        N>>=1;
    }
    printf("%llu\n",F[0]*q_pow((int)G[0],mod-2,mod)%mod);
}

int N,n,m;
int p[maxn];

int main(){
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
    N=read(),n=read(),m=read();
    for(int i=1;i<=n;++i) p[i]=read();
    Poly F,G;
    for(int i=1;i<=n;++i) a[i]=1;
    F=Conquer(1,n);
    F=F.Pow(m);
    for(int i=1;i<=n;++i) a[i]=p[i];
    G=Conquer(1,n);
    G=G.Pow(m);
    Bostan_Mori(N,F,G);
    return 0;
}

标签：校国赛,ch,return,考后,int,res,pos,maxn,模拟
From： https://www.cnblogs.com/SoyTony/p/Multiple_School_Simulation_Problems_of_NOI_in_July_1.htm

相关文章

  • springboot+token+redis，模拟登录
    登录测试的controller：loginTest.javapackagecom.example.demo.controller;importcom.example.demo.po.ResponseBean;importorg.springframework.data.redis.core.RedisTemplate;importorg.springframework.web.bind.annotation.*;importjavax.annotation.Resource;i......
  • 模拟题
    P1054[NOIP2005提高组]等价表达式如果我们计算表达式的每一项的系数，再逐一比较，难度较大。所以，我们可以将每个柿子带入10个数，算出10个结果。如果10个结果都相等，就认为两个柿子等价。在计算一个有括号，加减乘幂运算的表达式时，如果直接求解的话，难度仍然较大。但是利用它的优先级......
  • 6.28 模拟赛小记
    大脑宕机了！错误已更正，感谢提醒！---[更好的阅读体验？]()---A.木棍切割1我现在很难解释我的做法，只能说n^3大标之后就很容易推出柿子了。现在还不知道怎么证明正确性qwq以及如果模拟赛你去洛谷找原，找到的不是这个，是木棍切割2，如果看看题面的话就不会掉进坑里。```cpp#include<......
  • LINQ问题：模拟并发冲突时遇到的问题(LINQ to SQL)
    问题描述此问题是通过的网友交流获得解决的，首先对参与和关注此问题的网友表示感谢，特别是foren_whb给予了热心地、直接地帮助！谢谢你们！望日后继续进行着广泛地深入的交流！虽然说，谁也不想遇到并发冲突这种情况，但这却是一个必然会发生的事情，因此，学习掌握它的解决办法还是很有必要的。我......
  • 2023冲刺国赛模拟 28.1
    T3函数首先存在结论\(f(a+2C)=f(a)+2C\)。简单证明，设\(b=2f(a)-a+1\)，那么\(f(b)=f(a)+C\)，设\(d=2f(b)-b+1\)，那么\(f(d)=f(a)+2C\)，同时：\[\begin{aligned}d&=2f(b)-b+1\\&=2f(a)+2C-2f(a)+a-1+1\\&=a+2C\end{aligned}\]根据结论可以知道，我们可以将函数\(f......
  • assert断言与const修饰指针的妙用（模拟实现strcpy函数）
     assert断言目录assert断言的妙用：头文件：使用方法：const修饰指针的妙用主要用法const在*左边const在*右边断言和const修饰指针的应用模拟实现C语言strcpy函数  1、若字符串str1,str2有空指针怎么办？  2.str2改变了怎么办？assert断言的妙用：头文件：#include<assert.h>使用方法：当......
  • 冲刺国赛模拟 28
    一天两个小时踹了两回机箱还把我五道题题解踹没了，我不好说什么。论坛数学版看到一道高消dp的题，第一反应是这是个马尔可夫链可以列矩阵求逆嗯解。我是不是魔怔了。\[%>特别是当两者科技树点的都很歪而且歪的方向不同的时候。——H_Kaguyain13.5%你在影射什么我不好说。\]k......
  • 狂收 3.2k star！百度开源压测工具，可模拟几十亿的并发场景，太强悍了！
    dperf是一款基于DPDK的100Gbps网络性能和负载测试软件，能够每秒建立千万级的HTTP连接、亿级别的并发请求和数百Gbps的吞吐量。优点性能强大：基于DPDK，使用一台普通x86服务器就可以产生巨大的流量：千万级的HTTP每秒新建连接数，数百Gbps的带宽，几十亿的并发连接数统......
  • 2023冲刺国赛模拟 27.1
    话说我的习惯是一套题全部改完后才写题解，然而上次的题解停留在\(20.1\)，这足以看出近两日的颓废现状。由于昨天晚上做了个噩梦，所以今天的题解先扯点别的。目前初步鉴定噩梦是由FateZero中Caster的行为引起的。比较显然Caster及其御主都是以他人的痛苦为乐的人。在现代......
  • matlab仿真逆变器故障模拟 牵引逆变器IGBT故障模拟系统
    matlab仿真逆变器故障模拟牵引逆变器IGBT故障模拟系统原创文章，转载请说明出处，资料来源：http://imgcs.cn/5c/629480936977.html......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99