2.13 simulation summary

Preface

day9
170pts
expect ：100+100+20=220
actual ：70+100+0=170
rnk7

There are a lot of points qwq
If you get a full score, you can take paile …
T1 Add a superfluous thing , As a result, it was given for nothing 30
T3 Violent search T It fell off , We need to take a warning , In fact, just add a small optimization .

title

Minimum partition （divide）

It should be a scientific problem .
WQS Two point template question , Because this algorithm is not too cold ,A There are also many people .
Select the number according to >= Two points …
and , Don't be afraid that the number is not equal to $m$ When forced transfer ！ It was right to do nothing .
combination WQS The essence of is also reasonable , Just a few points fall on this straight line , It doesn't affect me to calculate the function value with intercept , If I force the last step to take $m$ A transfer , Will destroy the optimality , Get the wrong intercept .
Understanding is paramount .

Hexadecimal path （base）

Explosive liver code agricultural problem .
But it's really not too hard to think about , Use the chairman tree and line segment tree to simulate the high-precision addition and comparison .
But addition requires an interval flattening operation , The chairman tree with the lazy mark is really disgusting …
The complexity of time and space should be $O((n+m)\log n\log V)$, From the number of addition operations, the space seems to be only $O(m\log V)$, But because other query operations need pushdown, Drive more , So in fact, the spatial complexity is also two log Of .
The realization of the problem solution is to directly link the flattened interval to the corresponding node of an empty line segment tree , The space complexity can be optimized to single log.

Euler （eular）

It's really not that I stumble
KH This question really steps on the mark , Please take my knee ！

Mo did it quite clearly before , It's a pity that this problem didn't work out .
The main thing is that my brain is a little cramped , For multiple numbers lcm, Forgetting it can also be The maximum power of each prime factor .
Because Euler function is a product function , Consider enumerating each prime number separately $p$ The contribution of .
We have ：$\phi (p^k)=p^{k-1}(p-1)$
therefore $p$ The total contribution of this prime number must be $(p-1{)}^a{p}^b$ The appearance of .
First ,$p$ Must appear at least once , This sequence has $n^k-\lfloor \frac{n}{p}{\rfloor }^k$ individual .
therefore $p-1$ Power of contribution $a$ Namely $n^k-\lfloor \frac{n}{p}{\rfloor }^k$.
Then consider how to find $b$.
At the beginning, the contribution of all sequences is 0.
Set a sequence $p$ The highest number of times is $mx$, that $mx\ge w$ The sequence of should have $n^k-\lfloor \frac{n}{p^w}{\rfloor }^k$ individual .
We from 2 Start enumeration $w$, Then the contribution of the corresponding sequence is regarded as 1.
So one $mx=x$ Sequence , It will contribute $x-1$ Secondary contribution , Just in line with the meaning of the topic .（ This is also a common statistical skill ）

The greatest truths are the simplest , Graceful .
The total complexity is probably less than that of single log Of .

After reading this practice , The solution to the problem is …
But this min-max It's still handsome .
Then there is the conventional large-scale inversion .

Code

T1

#include<bits/stdc++.h>
using namespace std;
#define ll __int128
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
    
	ll x(0),f(1);char c=getchar();
	while(!isdigit(c)){
    if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void write(ll x){
    
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=2e5+100;

int n,m;

#define X(o) (2*s[o])
#define Y(o) (dp[o]+s[o]*s[o]-2*p*s[o])

ll s[N],dp[N],p;
int num[N],q[N],st,ed;

void solve(ll w,int op=0){
    
	q[st=ed=1]=0;
	for(int i=1;i<=n;i++){
    
		while(st<ed&&s[i]*(X(q[st+1])-X(q[st]))>=(Y(q[st+1])-Y(q[st]))) ++st;
		int j=q[st];
		dp[i]=dp[j]+(s[i]-s[j]+p)*(s[i]-s[j]+p)+w;
		num[i]=num[j]+1;
		while(st<ed&&(Y(i)-Y(q[ed]))*(X(q[ed])-X(q[ed-1]))<=
		(Y(q[ed])-Y(q[ed-1]))*(X(i)-X(q[ed]))) --ed;
		q[++ed]=i;
		//printf("i=%d j=%d dp=%lld (%lld %lld)\n",i,j,dp[i],X(i),Y(i));
		//for(int j=st;j<=ed;j++) printf("%d:(%lld %lld) ",q[j],X(q[j]),Y(q[j]));
		//puts("\n");
	}
	//printf("w=%lld num=%d dp=%lld\n",w,num[n],dp[n]);
	return;
}

signed main(){
    
	freopen("divide.in","r",stdin);
	freopen("divide.out","w",stdout);
	n=read();m=read();p=read();
	for(int i=1;i<=n;i++) s[i]=read()+s[i-1];
	
	//solve(308);return 0;
	
	ll st=-1e16,ed=1e16;
	while(st<ed){
    
		ll mid=(st+ed+1)>>1;
		solve(mid);
		if(num[n]>=m) st=mid;
		else ed=mid-1;
	}
	solve(st,1);
	write(dp[n]-m*st);
	return 0;
}
/* 5 aabba */

T2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
    
	ll x(0),f(1);char c=getchar();
	while(!isdigit(c)){
    if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void write(ll x){
    
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=2e5+100;
const int mod=1e9+7;

int n,m,s,t,o;

struct node{
    
	int to,nxt,w;
}p[N<<1];
int fi[N],cnt;
inline void addline(int x,int y,int w){
    
	p[++cnt]=(node){
    y,fi[x],w};fi[x]=cnt;
}
int pre[N],a[N],num;
void print(int x){
    
	if(pre[x]) print(pre[x]);
	a[++num]=x;
}
ll dis[N];
ull mi[N];
int u[N],v[N],ww[N];
int vis[N];
#define pr pair<ll,int>
#define mkp make_pair
priority_queue<pr,vector<pr>,greater<pr> >q;

void bf(){
    
	mi[0]=1;
	for(int i=1;i<=o;i++) mi[i]=mi[i-1]<<1;
	for(int i=1;i<=m;i++){
    
		addline(u[i],v[i],mi[ww[i]]);
		addline(v[i],u[i],mi[ww[i]]);
	}
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;q.push(mkp(0,s));
	while(!q.empty()){
    
		int now=q.top().second;q.pop();
		if(vis[now]) continue;
		vis[now]=1;
		for(int i=fi[now];~i;i=p[i].nxt){
    
			int to=p[i].to;
			if(dis[to]>dis[now]+p[i].w){
    
				dis[to]=dis[now]+p[i].w;
				q.push(mkp(dis[to],to));
				pre[to]=now;
			}
		}
	}
	if(pre[t]||s==t){
    
		printf("%lld\n",dis[t]%mod);
		print(t);
		printf("%d\n",num);
		for(int i=1;i<=num;i++) printf("%d ",a[i]);
		puts("");
	}
	else puts("-1");
	return;
}

ull hh[N][2];
#define mid ((l+r)>>1)
const int key=3;
struct tree{
    
	int ls,rs,sum,laz;
	ull h;
}tr[N*200];
int tot;
inline void pushup(int k,int l,int r){
    
	tr[k].sum=tr[tr[k].ls].sum+tr[tr[k].rs].sum;
	tr[k].h=tr[tr[k].rs].h*mi[mid-l+1]+tr[tr[k].ls].h;
	return;
}
inline int copy(int x){
    
	tr[++tot]=tr[x];
	return tot;
}
inline void add(int &k,int l,int r,int w){
    
	k=copy(k);
	tr[k].sum=(r-l+1)*w;tr[k].laz=w;
	tr[k].h=hh[r-l+1][w];
	return;
}
inline void pushdown(int k,int l,int r){
    
	if(l==r) return;
	int o=tr[k].laz;tr[k].laz=-1;
	if(o==-1) return;
	add(tr[k].ls,l,mid,o);add(tr[k].rs,mid+1,r,o);
	return;
}
void build(int &k,int l,int r,int w){
    
	k=copy(0);
	if(l==r){
    
		tr[k].sum=tr[k].h=w;
		hh[r-l+1][w]=tr[k].h;
		return;
	}
	build(tr[k].ls,l,mid,w);
	build(tr[k].rs,mid+1,r,w);
	pushup(k,l,r);
	hh[r-l+1][w]=tr[k].h;
	return;
}
int findsuf(int k,int l,int r,int pl){
    
	if(tr[k].sum==r-l+1) return r-pl+1;
	if(l==r) return 0;
	pushdown(k,l,r);
	if(pl>mid) return findsuf(tr[k].rs,mid+1,r,pl);
	else{
    
		int res=findsuf(tr[k].ls,l,mid,pl);
		if(res==mid-pl+1) return res+findsuf(tr[k].rs,mid+1,r,mid+1);
		else return res;
	}
}
void upd(int &k,int l,int r,int x,int y,int w){
    
	//printf("upd: (%d %d) (%d %d) w=%d\n",l,r,x,y,w);
	if(x>y) return;
	if(x<=l&&r<=y){
    
		add(k,l,r,w);return;
	}
	pushdown(k,l,r);
	k=copy(k);
	if(x<=mid) upd(tr[k].ls,l,mid,x,y,w);
	if(y>mid) upd(tr[k].rs,mid+1,r,x,y,w);
	pushup(k,l,r);
	return;
}
bool cmp(int x,int y,int l,int r){
    // x<y ? 1:0
	if(tr[x].h==tr[y].h) return 0;
	if(l==r) return tr[x].sum<tr[y].sum;
	pushdown(x,l,r);pushdown(y,l,r);
	if(tr[tr[x].rs].h!=tr[tr[y].rs].h) return cmp(tr[x].rs,tr[y].rs,mid+1,r);
	else return cmp(tr[x].ls,tr[y].ls,l,mid);
}
struct bign{
    
	int rt;
	void plus(int w){
    
		int len=findsuf(rt,1,o,w);
		upd(rt,1,o,w,w+len-1,0);upd(rt,1,o,w+len,w+len,1);
		return;
	}
	bool operator < (const bign &oth)const{
    
		return cmp(rt,oth.rt,1,o);
	}
}d[N];
struct Dis{
    
	bign dis;
	int id;
	bool operator < (const Dis &oth)const{
    
		if(tr[dis.rt].h==tr[oth.dis.rt].h) return id>oth.id;
		else return oth.dis<dis;
	}
};
priority_queue<Dis>que;
ll ans,mi2[N];
void calc(int k,int l,int r){
    
	if(l==r){
    
		ans=(ans+tr[k].sum*mi2[l-1])%mod;
		return;
	}
	pushdown(k,l,r);
	calc(tr[k].ls,l,mid);calc(tr[k].rs,mid+1,r);
	return;
}
void solve(){
    
	o+=20;
	mi2[0]=1;
	for(int i=1;i<=o;i++) mi2[i]=(mi2[i-1]<<1)%mod;
	mi[0]=1;
	for(int i=1;i<=o;i++) mi[i]=mi[i-1]*key;
	for(int i=1;i<=m;i++){
    
		++ww[i];
		addline(u[i],v[i],ww[i]);
		addline(v[i],u[i],ww[i]);
	}
	build(d[0].rt,1,o,1);//rt[0]=inf
	for(int i=1;i<=n;i++) d[i].rt=d[0].rt;
	build(d[s].rt,1,o,0);
	que.push((Dis){
    d[s],s});
	while(!que.empty()){
    
		int now=que.top().id;que.pop();
		if(vis[now]) continue;
		vis[now]=1;
		for(int i=fi[now];~i;i=p[i].nxt){
    
			int to=p[i].to,w=p[i].w;
			bign res=d[now];res.plus(w);
			if(res<d[to]){
    
				d[to]=res;
				que.push((Dis){
    d[to],to});
				pre[to]=now;
			}
		}
	}
	if(!pre[t]&&s!=t) puts("-1");
	else{
    
		calc(d[t].rt,1,o);
		//debug("dis=%lld\n",ans);
		printf("%lld\n",ans);
		print(t);
		printf("%d\n",num);
		for(int i=1;i<=num;i++) printf("%d ",a[i]);
	}
	return;
}

signed main(){
    
	freopen("base.in","r",stdin);
	freopen("base.out","w",stdout);
	//printf("%d\n",sizeof(tr)/1024/1024);
	memset(fi,-1,sizeof(fi));cnt=-1;
	tr[0].laz=-1;
	n=read();m=read();s=read();t=read();
	for(int i=1;i<=m;i++){
    
		u[i]=read();v[i]=read();ww[i]=read();
		o=max(o,ww[i]);
	}
	if(o<=20) bf();
	else solve();
	//solve();
	return 0;
}
/* 5 aabba */

T3

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
    
	ll x(0),f(1);char c=getchar();
	while(!isdigit(c)){
    if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void write(ll x){
    
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=2e6+100;
const int mod=1e9+7;

inline ll ksm(ll x,ll k,ll mod){
    
	ll res(1);
	while(k){
    
		if(k&1) res=res*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return res;
}

int n,k;
int prime[N],vis[N],tot;
void init(int n){
    
	++n;
	for(int i=2;i<=n;i++){
    
		if(!vis[i]){
    
			prime[++tot]=i;
		}
		for(int j=1;j<=tot&&prime[j]<=n/i;j++){
    
			int now=prime[j];
			vis[i*now]=1;
			if(i%now==0) break;
		}
	}
	return;
}

signed main(){
    
	freopen("euler.in","r",stdin);
	freopen("euler.out","w",stdout);
	n=read();k=read();
	init(max(k,n));
	ll ans(1);
	for(int o=1;o<=tot;o++){
    
		ll p=prime[o];
		ans=ans*ksm(p-1,ksm(n,k,mod-1)+(mod-1)-ksm(n-n/p,k,mod-1),mod)%mod;
		ll now=p*p;
		while(now<=n){
    
			ans=ans*ksm(p,ksm(n,k,mod-1)+mod-1-ksm(n-n/now,k,mod-1),mod)%mod;
			now*=p;
		}
	}
	printf("%lld\n",ans);
	return 0;
}
/* 5 aabba */

summary

Today, I feel that the overall topic is easier .
But there are a little too many points , and T3 It's a pity , In fact, I haven't thought about the practice of considering each prime number separately …
（ Now on the topic “ Feeling ” It's better , Can't do the problem see solution Basically, there are “ Actually, I thought ” The process of .）
But still dare to push and think .
Dare to think creatively , Try multi line thinking when you encounter obstacles .
in addition , Today's rhythm is still good .
Come on tomorrow ！awa