社区讨论
样例三看不懂,求解释
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 条回复,欢迎继续交流。
正在加载回复...