NB题解

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define LL __int128
using namespace std;
const int N=303,M=603,Vm=90003,mod=998244353;
const ll Mod=mod;
const LL inf=1e37;
char sk[107];
int U[M],V[M],n,m;
ll W[M];
struct frc{
	LL vl;
	int c;
};
bool operator<(const frc&x,const frc&y){
	return x.vl*y.c<y.vl*x.c;
}
bool operator==(const frc&x,const frc&y){
	return x.vl*y.c==y.vl*x.c;
}
template<class T>inline void ckmn(T&a,const T&b){
	if(b<a)a=b;
}
LL f[N][N],tmpr[N][N];
frc disr[N];
int modv[N];
LL readmx(char *s,LL mx){
	LL ans=0;
	for(;*s;++s)ans=min(ans*10+((*s)^48),inf);
	return ans;
}
ll readmod(char*s,ll mod){
	ll ans=0;
	for(;*s;++s)ans=(ans*10+((*s)^48))%mod;
	return ans;
}
void chkr(int u,int t){
	if(tmpr[t][u]<inf)ckmn(disr[u],(frc){
		tmpr[t][u],t
	});
}
struct pii{
	LL A,vl;
	int c;
};
LL K;
pii g[N][N];
inline pii addp(const pii&a,ll b){
	return{a.A,a.vl+(LL)b*a.c,a.c};
}
inline bool operator<(const pii&x,const pii&y){
	LL va=x.A*y.c-y.A*x.c,vb=y.vl*x.c-x.vl*y.c;
	if(!va)return vb>0;
	if(va>0){
		if(vb<=0||K==inf)return 0;
		return K<=(vb-1)/va;
	}
	va=-va;
	vb=-vb;
	if(vb<=0||K==inf)return 1;
	return K>vb/va;
}
void man(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T>>T;
	while(T--){
		cin>>n>>m>>sk;
		K=readmx(sk,inf);
		for(int i=1;i<=m;++i)cin>>U[i]>>V[i]>>W[i];
		int mx=n*n;
		if(K<=mx+mx)mx=K;
		f[0][1]=0;
		for(int i=2;i<=n;++i)f[0][i]=inf;
		for(int i=1;i<=mx;++i){
			LL*cur=f[i%n],*las=f[(i-1)%n];
			fill(cur+1,cur+n+1,inf);
			for(int j=1;j<=m;++j)ckmn(cur[V[j]],las[U[j]]+W[j]);
		}
		if(K==mx){
			for(int i=1;i<=n;++i)cout<<(f[mx%n][i]<inf?(int)(f[mx%n][i]%mod):-1)<<' ';
			cout<<endl;
			continue;
		}
		for(int u=1;u<=n;++u){
			disr[u]={1,0};
			fill(tmpr[1]+1,tmpr[1]+n+1,inf);
			for(int j=1;j<=m;++j)if(U[j]==u)ckmn<LL>(tmpr[1][V[j]],W[j]);
			chkr(u,1);
			for(int i=2;i<=n;++i){
				fill(tmpr[i]+1,tmpr[i]+n+1,inf);
				for(int j=1;j<=m;++j)ckmn(tmpr[i][V[j]],tmpr[i-1][U[j]]+W[j]);
				chkr(u,i);
			}
		}
		for(int i=1;i<=n;++i) modv[i]=readmod(sk,i);
		for(int i=0;i<n;++i)fill(g[i]+1,g[i]+n+1,(pii){1,0,0});
		for(int u=1;u<=n;++u){
			if(disr[u].c){
				const int r=disr[u].c;
				for(int ii=0;ii<n;++ii)if(f[(n-ii)%n][u]<inf){
						int jj=-(modv[r]-2*n*n+ii)%r;
						if(jj<0)jj+=r;
						LL disii=f[(n-ii)%n][u],vfs=disii*r-(2*n*n-ii-jj)*disr[u].vl;
						ckmn(g[(n-jj)%n][u],(pii){disr[u].vl,vfs,r});
					}
			}
		}
		for(int i=n*n-1;~i;--i){
			pii*cur=g[i%n],*las=g[(i+1)%n];
			if(i<=n*n-n)fill(cur+1,cur+n+1,(pii){1,0,0});
			for(int j=1;j<=m;++j)ckmn(cur[V[j]],addp(las[U[j]],W[j]));
		}
		for(int i=1;i<=n;++i)
			if(!g[0][i].c)cout<<"-1 ";
			else{
				const int r=g[0][i].c;
				ll mmod=Mod*r,avl=g[0][i].A%mmod;
				int ans=(((LL)readmod(sk,mmod)*avl+g[0][i].vl%mmod+mmod)%mmod)/r;
				cout<<ans<<' ';
			}
		cout<<endl;
	}
}
int main(){int a,b;cin>>a>>b;cout<<a+b;}