随机过程

2024 CCPC网络预选赛 E

The 2024 CCPC Online Contest - Codeforces

题型分析

生日问题变式+trie树性质

题目描述&数据范围

题解

显然第 $i$ 层最多可以有 $M=min(n,26^i)$

下面讨论期望：

字典树上的一个节点代表一个前缀

假设第 $i$ 层的一个节点出现的概率是 $p$

由于同层节点之间相互独立，且第 $i$ 层最多能有 $26^i$ 个节点（可以相同）

则第 $i$ 层的期望节点数是 $p\cdot 26^i$

下面求 $p$

假设 $q$ 表示某个节点不出现的概率，则 $p=1-q$

对于一个字符串，某个长度为 $i$ 的前缀出现的概率是 $\frac{1}{26^i}$

那么这个前缀不出现的概率是 $1-\frac{1}{26^i}$

总共有 $n$ 个串，这个前缀在 $n$ 个字符串中都不出现的概率是 $q=(1-\frac{1}{26^i})^n$

所以最终答案为：

$\sum_{i=0}^{m}(1-(1-\frac{1}{26^i})^n)26^i$

代码

#include<bits/stdc++.h>
using namespace std;
#define IN inline
const int N=1e5+5;
const int mod=998244353;
struct Mint{
    int v;
    Mint():v(0){}
    Mint(long long x){v=static_cast<int>((-mod<=x&&x<mod)?x:x%mod);if(v<0)v+=mod;}
    friend Mint operator+(const Mint &a,const Mint &b){return (a.v+b.v)%mod;}
    friend Mint operator-(const Mint &a,const Mint &b){return (a.v-b.v+mod)%mod;}
    friend Mint operator*(const Mint &a,const Mint &b){
        return static_cast<int>(1ll * a.v*b.v%mod);
    }
    friend Mint operator/(const Mint &a,const Mint &b){
        return static_cast<int>(1ll*a.v*b.qpow(mod-2).v%mod);
    }
    friend ostream& operator<<(ostream &o,const Mint &t)cons{
		o<<t.x;
        return o;
    }
    Mint qpow(int x)const{
        long long res=1,a=v;
        while(x){
            if(x&1)res=res*a%mod;
            a=a*a%mod;
            x>>=1;
        }
        return Mint(res);
    }
};
using ll=Mint;
long long pw[N];
long long n, m;
void solve(){
    cin>>n>>m;
    ll sum=0,sum1=0;
    for(int i=0;i<=m;++i){
        sum=sum+(Mint(1)-(Mint(1)-Mint(1)/Mint(26).qpow(i)).qpow(n))*Mint(26).qpow(i);
    }
    long long res=1;
    for(int i=0;i<=m;++i){
        sum1=sum1+min(n,res);
        if(res<=n)res*=26;

    }
    cout<<sum1.v<<' ';
    cout<<sum.v<<'\n';
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}