A
发现一个数可以作为模数当且仅当该数<=(n-1)/2，然后取(n-1)/2的最高位然后是2^x-1即可
B
对于圆这种难处理的东西，我们可以用KD-Tree来维护，这个思维比较好想，但代码难写，先放着有时间填坑
C
数据范围是个坑人的玩意！
很容易知道环上的点度数都是2，而每个环没有重边，说明图中要是均为环，当且仅当每个点的度数都是偶数。而有数字的方格也是一个限制。对于奇偶性的限制，可以考虑解异或方程组，把每条边当成一个未知数即可。解方程可能会TLE，于是可以用bitset优化，时间复杂度O(n^3m^3/w)
#include<bits/stdc++.h> using namespace std; const int N=1e3,mod=998244353; int n,m,tot,num,idx[N][N],idy[N][N]; char s[N]; bitset<N>a[N]; int main() { int T;scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); tot=num=0; for(int i=1;i<=n;++i)for(int j=1;j<m;++j)idx[i][j]=++tot; for(int i=1;i<n;++i)for(int j=1;j<=m;++j)idy[i][j]=++tot; ++tot; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { a[++num].reset(); if(i>1)a[num][idy[i-1][j]]=1; if(j>1)a[num][idx[i][j-1]]=1; if(i<n)a[num][idy[i][j]]=1; if(j<m)a[num][idx[i][j]]=1; } for(int i=1;i<n;++i) { scanf("%s",s+1); for(int j=1;j<m;++j) if(s[j]!='.') { a[++num].reset(); a[num][idx[i][j]]=a[num][idx[i+1][j]]=a[num][idy[i][j]]=a[num][idy[i][j+1]]=1; a[num][tot]=s[j]-'0'; } } int pos=1; for(int j=1;j<tot;++j) { int x=0; for(int i=pos;i<=num;++i)if(a[i][j]){x=i;break;} if(!x)continue; if(x!=pos)swap(a[pos],a[x]); for(int i=1;i<=num;++i)if(i!=pos&&a[i][j])a[i]^=a[pos]; ++pos; } int ans=1; for(int i=pos;i<=num;++i)if(a[i].any()){ans=0;break;} for(int i=pos;i<tot;++i)ans=ans*2%mod; printf("%d ",ans); } }
E
如果x为质数向2连边，否则向其中一个约数连边。质数可以用线性筛处理，然后用前缀和统计。时间复杂度O(n)，代码略。
F
类似十二省联考异或粽子的写法，建立字典树，每个节点表示最后出现的位置，然后建立字典树前查询即可。
时间复杂度O(30n)
#include<bits/stdc++.h> using namespace std; const int N=1e5+7; int n,k,cnt,l,r,ch[N*30][2],pre[N*30]; void build(int x,int id) { int u=1,op; pre[u]=id; for(int i=29;~i;--i) { op=(x>>i)&1; if(!ch[u][op])ch[u][op]=++cnt; u=ch[u][op]; pre[u]=id; } } void find(int x,int id) { int u=1,mx=-1,op,pos; for(int i=29;~i;--i) { op=(x>>i)&1,pos=(k>>i)&1; if(!pos)mx=max(mx,pre[ch[u][op^1]]); u=ch[u][op^pos]; if(!u)break; } mx=max(mx,pre[u]); if(mx!=-1&&id-mx<r-l)l=mx,r=id; } int main() { int T;scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); pre[0]=-1; for(int i=1;i<=n*30+1;++i)ch[i][0]=ch[i][1]=0,pre[i]=-1; l=0,r=n+1,cnt=1; build(0,0); int now=0; for(int i=1,x;i<=n;++i) { scanf("%d",&x),now^=x; find(now,i); if(i<n)build(now,i); } if(r==n+1)puts("-1");else printf("%d %d ",l+1,r); } }
G
f[i]=(n-2)f[i-1]+(n-1)f[i-2]，推式子可以得到f[t]=((n-1)^t+(n-1)*(-1)^t)/n
然后分奇偶性讨论可以变成(n-1)^(2a)=b，使用BSGS即可解决
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; ll n,x,B; unordered_map<ll,ll>mp; ll qpow(ll a,ll b) { ll ret=1; while(b) { if(b&1)ret=ret*a%mod; a=a*a%mod,b>>=1; } return ret; } int main() { int T;scanf("%d",&T); B=sqrt(mod); while(T--) { scanf("%lld%lld",&n,&x); x=x*n%mod*qpow(n-1,mod-2)%mod; mp.clear(); mp[1]=0; ll f1=(x+mod-1)*(n-1)%mod,f2=(x+1)%mod,base=(n-1)*(n-1)%mod; if(f1==1){puts("0");continue;} if(f2==1){puts("1");continue;} ll p=1,ans=-1; for(int i=1;i<=B;i++) { p=p*base%mod; mp[p]=i; if(f1==p){ans=2*i;break;} if(f2==p){ans=2*i+1;break;} } if(ans!=-1){printf("%lld ",ans);continue;} p=qpow(p,mod-2); for(ll k=1,pw=p;k*B<mod;k++,pw=pw*p%mod) { if(mp.count(f1*pw%mod)){ans=2ll*(k*B+mp[f1*pw%mod]);break;} if(mp.count(f2*pw%mod)){ans=2ll*(k*B+mp[f2*pw%mod])+1;break;} } printf("%lld ",ans); } }
H
转化为0,1矩阵，每个位置1代表比上面小，然后用悬线法求最大01矩阵即可
#include<bits/stdc++.h> using namespace std; const int N=5005; int n,m,ans,tot,a[N][N],b[N][N],h[N],q[N]; int main() { int T;scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&a[i][j]); b[i][j]=(i==1)?0:(a[i][j]>=a[i-1][j]); } for(int i=1;i<=m;i++)h[i]=0; ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++)if(!b[i][j])h[j]=1;else h[j]++; tot=h[m+1]=0; for(int j=1;j<=m+1;j++) { while(tot&&h[q[tot]]>h[j]) { ans=max(ans,(j-q[tot-1]-1)*h[q[tot]]); --tot; } q[++tot]=j; } } printf("%d ",ans); } }
I
签到题，按照kruskal的加边方式，从小到大加边，注意考虑边权相同的情况即可
#include<bits/stdc++.h> using namespace std; const int N=1e5+7,M=5e5+7; struct edge{int x,y,z;}e[M]; int n,m,k,fa[N]; bool cmp(edge a,edge b){return a.z<b.z;} int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} int main() { int T;scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z); for(int i=1;i<=n;i++)fa[i]=i; sort(e+1,e+m+1,cmp); int num=n,D=1e9+7; bool flag=1; if(k==n)D=0; for(int i=1;i<=m&&D;i++) { int x=e[i].x,y=e[i].y,z=e[i].z; x=find(x),y=find(y); if(x!=y) { if(num==k+1)D=z; else if(num<=k) { if(z<=D)flag=0; break; } fa[x]=y,--num; } } if(!flag||D==1e9+7)puts("-1");else printf("%d ",D); } }
J
询问是1e5次，而且没有修改，所以是裸的莫队，代码略
持续更新中……