T1 最短路

需要一个数据结构实现快速加一个 2 的幂和比较大小

考虑主席树维护二进制数，每个节点维护答案和第一个为 0 的位置

加 \(2^k\) 就从 k 往后找到第一个为 0 的位置改成 1，中间的位改为 0

比较大小线段树上二分就行了

T2 集合

要求一个集合 S ，满足 \(\prod_{i\in S}i!\) 为完全平方数

删的个数 <=3

若 n 为偶数，\(2^{\frac{n}{2}}\frac{n}{2}!\prod_{i=1}^{\frac{n}{2}}(2k-1)!^2\)

若 n/2 为偶数，只删 \(\frac{n}{2}!\) ，否则再删个 2!

若 n 为奇数，把 n 删了就是偶数了，所以 <=3

(但是实际上这个并不是最优策略)

所以依次判断 n ,n-1

判断 n-2 就每个质数随机赋权，然后用个 unordered_map 存异或和判断

剩下的就是 n-3 ，删 n，n/2, 2

(打表，发现 4|n 则答案是 n-1,然后把不是 4|n 的减到 4|n，就 65 了)

T3

只会 dp ，统一取模卡常能拿 35

然而我滚动数组最后没调出来，顺便 \(k=1\) 的也错了，剩 10 分

代码

T1

#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define il inline
#define li tre[i].lc
#define lj tre[j].lc
#define ri tre[i].rc
#define rj tre[j].rc
const int N=2e5+20,M=2e5+20;
const int mod=1e9+7;
bool jud[N];
int n,m,s,t;
int tot,d[N];
int first[N],cnt;
int mi[N],sum[N];
struct tree{
	bool jd;
	int loc,ans;
	int lc,rc;
	bool lazy;
}tre[(int)(1.1e7)];
void pushdown(int i,int l,int r){
	if(l==r)return;
	tre[++tot]=tre[li];li=tot;
	tre[++tot]=tre[ri];ri=tot;
	tre[li].loc=l,tre[ri].loc=((l+r)>>1)+1;
	tre[li].jd=tre[ri].jd=tre[li].ans=tre[ri].ans=0;
	tre[li].lazy=tre[ri].lazy=1;
	tre[i].lazy=0;
}
bool cmp(int i,int j,int l,int r,bool jd1,bool jd2){
	if(!jd1&&!jd2)return 0;
	if(l==r)return jd1*tre[i].jd<jd2*tre[j].jd;
	int mid=(l+r)>>1;
	if((!tre[i].lazy)*jd1*tre[ri].ans!=(!tre[j].lazy)*jd2*tre[rj].ans)
		return cmp(ri,rj,mid+1,r,jd1&(!tre[i].lazy),jd2&(!tre[j].lazy));
	else return cmp(li,lj,l,mid,jd1&(!tre[i].lazy),jd2&(!tre[j].lazy));
}
struct qxxx{
	int v,next,w;qxxx(){}
	qxxx(int v_,int next_,int w_){v=v_,next=next_,w=w_;}
}cc[2*N];
struct val_{
	int x,id;val_(){}
	val_(int x_,int id_){x=x_,id=id_;}
	friend bool operator<(val_ a,val_ b){
		return !cmp(a.id,b.id,1,M,1,1);
	}
};
priority_queue<val_>dui;
il int min_(int x,int y){return x>y?y:x;}
il void qxx(int u,int v,int w){
	cc[++cnt]=(qxxx){v,first[u],w};
	first[u]=cnt;
}
il int read(){
	int s=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
void update(int i){
	tre[i].jd=tre[li].jd&tre[ri].jd;
	tre[i].ans=(tre[li].ans+tre[ri].ans)%mod;
	tre[i].loc=min_(tre[li].loc,tre[ri].loc);
}
void chg(int &i,int l,int r,int L,int R,bool jd){
	if(L>R)return;
	tre[++tot]=tre[i],i=tot;
	if(tre[i].lazy)pushdown(i,l,r);
	if(l>=L&&r<=R){
		tre[i].jd=jd;
		tre[i].ans=jd*(sum[r]-sum[l-1]+mod)%mod;
		tre[i].loc=jd?M:l;
		tre[i].lazy=!jd;
		return;
	}int mid=(l+r)>>1;
	if(L<=mid)chg(tre[i].lc,l,mid,L,R,jd);
	if(R>mid)chg(tre[i].rc,mid+1,r,L,R,jd);
	update(i);
}
int qry(int &i,int l,int r,int L,int R){
	if(tre[i].lazy)pushdown(i,l,r);
	if(l>=L&&r<=R)return tre[i].loc;
	int mid=(l+r)>>1,ans=M;
	if(L<=mid)ans=min_(ans,qry(tre[i].lc,l,mid,L,R));
	if(R>mid)ans=min_(ans,qry(tre[i].rc,mid+1,r,L,R));
	return ans;
}
void build(int &i,int &j,int l,int r){
	i=++tot;j=++tot;if(l==r){
		tre[i]=(tree){l==M,l,l==M?mi[M-1]*2%mod:0};
		tre[j]=(tree){0,l,0};
		return;
	}int mid=(l+r)>>1;
	build(tre[i].lc,tre[j].lc,l,mid);
	build(tre[i].rc,tre[j].rc,mid+1,r);
	update(i);update(j);
}
void dij(){
	build(d[0],d[s],1,M);
	for(int i=1;i<=n;++i)if(s!=i)d[i]=d[0];
	int x,now,k,sl;dui.push(val_(s,d[s]));
	while(dui.size()){
		x=dui.top().x;dui.pop();
		if(jud[x])continue;jud[x]=1;
		for(int v,i=first[x];i;i=cc[i].next){
			v=cc[i].v;now=d[x];
			k=qry(now,1,M,cc[i].w,M);sl=tot;
			chg(now,1,M,k,k,1),chg(now,1,M,cc[i].w,k-1,0);
			if(!cmp(d[v],now,1,M,1,1))dui.push(val_(v,d[v]=now));
			else tot=sl;
		}
	}
}
signed main(){
	freopen("hellagur.in","r",stdin),freopen("hellagur.out","w",stdout);
	mi[0]=sum[0]=1;
	for(int i=1;i<N;++i){
		mi[i]=mi[i-1]*2%mod;
		sum[i]=(sum[i-1]+mi[i])%mod;
	}n=read(),m=read();
	for(int x,y,z,i=1;i<=m;++i){
		x=read(),y=read(),z=read();
		qxx(x,y,z);qxx(y,x,z);
	}s=read(),t=read();if(s==t){cout<<0<<endl;return 0;}
	dij();printf("%d\n",d[t]!=1?tre[d[t]].ans:-1);
}

T2

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
#define pr pair<int,bool>
#define fi first
#define se second
#define mkp make_pair
#define ull unsigned long long
const int N=1e6+11;
const ull mod=998244353;
bool fp[N];
int n;
ull mi[N],val[N];
int p[N],num;
vector<pr>vct[N];
namespace ans1{
	bool now[25];
	vector<int>sta,ans;
	bool vt[25][25];
	void solve(){
		for(int i=2;i<=n;++i){
			memcpy(vt[i],vt[i-1],sizeof(vt[i]));
			for(pr x : vct[i])vt[i][x.fi]^=x.se;
		}
		for(int jd,i=1;i<(1<<n);++i){
			memset(now,0,sizeof(now));sta.clear();
			for(int j=1;j<=n;++j)if((1<<j-1)&i){
				sta.push_back(j);
				for(int k=1;p[k]<=n;++k)now[p[k]]^=vt[j][p[k]];
			}jd=1;for(int j=1;j<=n;++j)jd&=(now[j]==0);
			if(sta.size()<=ans.size()||!jd)continue;
			swap(ans,sta);
		}cout<<ans.size()<<endl;for(int v : ans)cout<<v<<" ";cout<<endl;
	}
};
namespace ans2{
	ull hs;
	ull sum[N];
	unordered_map<ull,vector<int> >mp;
	void solve(){
		for(int i=(n&1)+2;i<=n;i+=2)hs^=val[i];
		if(!hs){cout<<n<<endl;for(int i=1;i<=n;++i)cout<<i<<" ";cout<<endl;return;}
		for(int i=2;i<=n;++i)sum[i]=val[i]^sum[i-1],mp[sum[i]].push_back(i);
		for(int i=2;i<=n;++i){
			if(hs==sum[i]){
				cout<<n-1<<endl;
				for(int j=1;j<i;++j)cout<<j<<" ";
				for(int j=i+1;j<=n;++j)cout<<j<<" ";
				cout<<endl;return;
			}
		}
		for(int i=2;i<=n;++i){
			ull k=hs^sum[i];
			if(mp.find(k)!=mp.end()){
				for(int v : mp[k])if(v!=i){
					cout<<n-2<<endl;
					for(int j=1;j<=n;++j)if(j!=v&&j!=i)cout<<j<<" ";
					cout<<endl;return;
				}
			}
		}cout<<n-3<<endl;
		for(int i=1;i<=n;++i)if(i!=2&&i!=n&&i!=n/2)cout<<i<<" ";cout<<endl;
	}
};
void pre(){
	uniform_int_distribution<unsigned long long> range(1,~(0llu));
	default_random_engine e(rand());
	fp[0]=fp[1]=1;
	for(int i=2;i<N;++i){
		if(!fp[i])p[++num]=i,vct[i].push_back(mkp(i,1)),val[i]=range(e);
		for(int tmp,j=1;j<=num&&p[j]*i<N;++j){
			fp[tmp=i*p[j]]=1;vct[tmp]=vct[i];
			val[tmp]=val[i]^val[p[j]];
			if(i%p[j]==0){vct[tmp][vct[tmp].size()-1].se^=1;break;}
			else vct[tmp].push_back(mkp(p[j],1));
		}
	}
}
signed main(){
	freopen("mountain.in","r",stdin),freopen("mountain.out","w",stdout);
	pre();cin>>n;
	for(int i=mi[0]=1;i<N;++i)mi[i]=mi[i-1]*mod;
	if(n<=20)ans1::solve();else ans2::solve();
}