社区讨论

样例三看不懂,求解释

P14254分割(divide)参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mhj0l1lz
此快照首次捕获于
2025/11/03 18:45
4 个月前
此快照最后确认于
2025/11/03 18:45
4 个月前
查看原帖
我的代码跑样例三是8,我手摸也是8,但是是12
代码:
CPP
#include<bits/stdc++.h>
using namespace std;
#define File(x) (freopen(x".in","r",stdin),freopen(x".out","w",stdout))
#define Filein(x) (freopen(x".in","r",stdin))
#define int long long
const int N=1e6+5,inf=1e14,mod=998244353,inv2=499122177;
int qpow(int a,int b=mod-2){a=(a%mod+mod)%mod;int res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
int n,k;
int f[N],fav[N],ans;
vector<int>g[N];
int dep[N],len[N];
vector<int>p[N];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    len[u]=1;
    for(auto v:g[u])
        dfs(v,u),len[u]=max(len[u],len[v]+1);
    p[dep[u]].push_back(len[u]);
}
int C(int n,int m){
    if(m>n||n<0||m<0)return 0;
    return f[n]*f[n-m]%mod*fav[m]%mod;
}
void work(){
    cin>>n>>k;
    f[1]=f[0]=fav[0]=fav[1]=1;
    for(int i=2,p;i<=n;i++)
        cin>>p,g[p].push_back(i),f[i]=f[i-1]*i%mod,fav[i]=fav[i-1]*qpow(i)%mod;
    dfs(1,0);
    for(int i=1;i<=n;i++){
        int pz=p[i].size();
        if(pz<=k)continue;
        
        // for(auto i_:p[i])cout<<i_<<" ";cout<<"\n";
            
        int mi=inf,cnt=0;
        for(auto i_:p[i])
            if(i_<mi)mi=i_,cnt=1;
            else if(i_==mi)cnt++;
            
        // cout<<cnt<<"\n";
        if(cnt==1)continue;
        ans=(ans+cnt*(f[pz-1]*fav[pz-k]%mod+mod-f[pz-cnt]*fav[pz-cnt-k+1]%mod)%mod)%mod;
    }
    cout<<ans;
}
void clear(){}
signed main(){
    // File("_");
    int _=1;
    while(_--)work(),clear();
    return 0;
}
/*
*/

回复

3 条回复,欢迎继续交流。

正在加载回复...