记录编号	589796	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3184.收益	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	19.830 s
提交时间	2024-07-07 22:45:55	内存使用	280.39 MiB

#include <bits/stdc++.h>
using namespace std;
 
const int N = 4000010;
 
long long n,k,ans[N],tot,seed,a[N],v[N],fa[N],g[N],h[N],res;//a存节点权值v存这条链的权值和fa存父亲节点g存选择哪个儿子h存会被父亲选择 
vector<long long>e[N];
 
void dfs(int idx){
    h[idx]=idx;
        v[idx]+=a[idx];
    if(e[idx].size()==0){  
        return ;
    }
    long long maxx=0,max_i=0;
    for(int i=0;i<e[idx].size();i++){
        int y=e[idx][i];
//        v[y]=v[idx];
        dfs(y);
        if(v[y]>maxx)maxx=v[y],max_i=y;
    }
    v[idx]+=v[max_i];
//    v[max_i]=0;
    g[idx]=max_i;
    h[max_i]=idx;
}
 
bool cmp(long long x,long long y){
    return x>y;
}
 
int main(){
    freopen("x.in","r",stdin);
    freopen("x.out","w",stdout);
    scanf("%lld%lld%lld",&n,&k,&seed);
    a[1]=seed;
    for(int i=2;i<=n;i++){
        a[i]=(a[i-1]*23333333+6666666)%1000000007;
        fa[i]=(a[i]^23333333)%(i-1)+1;
        e[fa[i]].push_back(i);
//        cout<<a[i]<<" ";
    }
    dfs(1); 
//    sort(v+1,v+1+n,cmp);
//    for(int i=1;i<=n;i++)cout<<v[i]<<' ';
//    cout<<endl;
    for(int i=1;i<=n;i++){
        if(h[i]==i){
            tot++;
            ans[tot]=v[i];
        }
    }
    sort(ans+1,ans+1+tot,cmp);
    for(int i=1;i<=k;i++){
        res+=ans[i];
//        cout<<res<<' ';
    }
    printf("%lld",res);
    return 0;
}