记录编号	589783	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	收益	最终得分	100
用户昵称	darkMoon	是否通过	通过
代码语言	C++	运行时间	21.868 s
提交时间	2024-07-07 17:28:09	内存使用	203.91 MiB

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
#define fin cin
#define fout cout
// ifstream fin("x.in");
// ofstream fout("x.out");
auto mread = [](){
    int x;
    fin >> x;
    return x;
};
const int N = 4e6 + 5;
int n = mread(), k = mread(), seed = mread(), a[N], f[N], fa[N], ans, to[N], e[N];
vector<int> v[N];
void dfs(int x){
    int p = 0, ma = -1;
    for(int y : v[x]){
        dfs(y);
        if(f[y] > ma)
        ma = f[y], p = y;
        f[x] = max(f[x], f[y]);
    }
    to[x] = p;
    f[x] += a[x];
    // printf("--- %lld %lld\n", x, to[x]);
    return;
}
void down(int x){
    if(f[x] == 0)
    return;
    if(to[x]){
        // printf("*** %lld\n", to[x]);
        down(to[x]);
        f[to[x]] = 0;
    }
    return;
}
signed main(){
    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;
        v[fa[i]].push_back(i);
    }
    dfs(1);
    for(int i = 1; i <= n; i ++){
        down(i);
    }
    sort(f + 1, f + 1 + n, [](int a, int b){
        return a > b;
    });
    k = min(k, n);
    for(int i = 1; i <= k; i ++)
    ans += f[i];
    fout << ans;
    return 0;
}