记录编号	589935	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	收益	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	15.491 s
提交时间	2024-07-08 18:34:18	内存使用	134.57 MiB

#include<bits/stdc++.h>
using namespace std;
//const long long mod=1e9+7,x1=23333333,x2=6666666;
long long a[4000010],se,sval[4000010],ans,sum[4000010];
int n,k,h[4000010],v[4000010],ne[4000010],tot,fa[4000010];
void add(int x,int y)
{
    tot++;
    v[tot]=y;
    ne[tot]=h[x];
    h[x]=tot;
}
void dfs(int x)
{
    int xson=0;
    for(int i=h[x];i;i=ne[i])
    {
        int y=v[i];
        dfs(y);
        if(sval[y]>sval[x])
        {
            sval[x]=sval[y];
            xson=y;
        }
    }
    sval[x]+=a[x];
    fa[xson]=x;
    return;
}
bool cmp(long long x,long long y)
{
    return x>y;
}
int main()
{
	freopen("x.in","r",stdin);
    freopen("x.out","w",stdout);
    scanf("%d%d%lld",&n,&k,&se);
    a[1]=se;
    for(int i=2;i<=n;i++)
    {
        //cout<<i<<endl;
        a[i]=((a[i-1]*(long long)23333333)%(long long)1000000007+(long long)6666666)%(long long)1000000007;
        //p[a[i]]=i;
        //cout<<a[i]<<endl;
    }
    for(int i=2;i<=n;i++)
    {
        long long f=(a[i]^(long long)23333333)%((long long)i-1)+1;
        int f2=(int)f;
        add(f2,i);
    }
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    dfs(1);
    int lsum=0;
    for(int i=1;i<=n;i++)
    {
        if(fa[i]==i)
        {
            lsum++;
            sum[lsum]=sval[i];
            //cout<<sum[lsum]<<endl; 
        }
    }
    sort(sum+1,sum+lsum+1,cmp);
    for(int i=1;i<=k;i++)
    {
        ans+=sum[i];
    }
    printf("%lld",ans);
    return 0;
}