记录编号	590923	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	收益	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	14.511 s
提交时间	2024-07-12 21:49:34	内存使用	80.43 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define ui unsigned int
#define db double
#define in inline
#define re register
#define F(i,a,b) for(int i = a;i <= b;i++)
#define D(i,a,b) for(int i = a;i >= b;i--)
const int N = 4e6+10;
const double eps = 1e-9,inf = 1e8;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<3) + (x<<1) + c-'0';
    return x * f;
}

int n,m;
ll val[N];
struct edge{
	int ver,nx;
}e[N<<1];
int hd[N],tot;
void link(int x,int y){e[++tot] = {y,hd[x]},hd[x] = tot;}


priority_queue<ll>q;
ll d[N];
int son[N];
void dfs1(int x){
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		dfs1(y);
		d[x] = max(d[x],d[y]);
		if(!son[x] || d[y] > d[son[x]])son[x] = y;
	}
	d[x] += val[x];
}
void dfs2(int x,int t){
	if(x == t)q.push(d[x]);
	if(!son[x])return;
	dfs2(son[x],t);
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y != son[x])dfs2(y,y);
	}
}


int main(){
    freopen("x.in","r",stdin);
    freopen("x.out","w",stdout);
	n = read(),m = read(),val[1] = read();
	for(int i = 2;i <= n;i++){
		val[i] = (val[i-1] * 23333333ll + 6666666) % 1000000007;
		link((val[i] ^ 23333333) % (i - 1) + 1,i);
	}
	dfs1(1),dfs2(1,1);
	ll ans = 0;
	while(!q.empty() && m)ans += q.top(),q.pop(),m--;
	printf("%lld\n",ans);


    return cerr<<endl<<"Time:"<<clock()<<"ms"<<endl,0;
     
}