冲刺省选2月17日 (互测)

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
#include
#include
#include
#include
#include
#include
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>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_queuedui;
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

#include
using namespace std;
#define il inline
#define int long long
#define pr pair
#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;
vectorvct[N];
namespace ans1{
	bool now[25];
	vectorsta,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< >mp;
	void solve(){
		for(int i=(n&1)+2;i<=n;i+=2)hs^=val[i];
		if(!hs){cout< range(1,~(0llu));
	default_random_engine e(rand());
	fp[0]=fp[1]=1;
	for(int i=2;i>n;
	for(int i=mi[0]=1;i