Solution

T1

首先，可以一眼看出这是一个完全图的一笔画问题。然后开始挖性质：

①根据欧拉图的性质，如果将我们一笔画中没有经过的边删去，那么剩下的节点的度数一定有$0$个或$2$个是奇数。

通过这个东西，我们可以挖出性质：

②如果$n$为奇数，可以发现这个完全图中所有节点的度数都是偶数，那么显然可以一笔画走完。答案为$C_n^2$。

③如果$n$为偶数，我们要考虑删去最少数量的边，使得剩下的图形可以一笔画走完。

由于我们要删去最少的边，又因为每删去一条边两端的节点的度数都会减去$1$，所以

④删去没有公共节点的$\frac{n-2}{2}$条边，此时剩下的各个节点的度数只有$2$个为奇数，可以一笔画。

于是本题就做完了——如果$n$为奇数，直接输出$C_n^2$；否则，输出$C_n^2-\frac{n-2}{2}$。

单次询问时间复杂度$O(1)$。

T2

首先，我们看到有几个Subtask的限制是$m=0$，于是我们就先思考$m=0$的情况。

定义$f_n$表示$m=0$时的期望步数。

首先，我们砍掉一只圣盾大头鱼的圣盾，进行了$1$次操作；然后分类讨论，如果第二步直接补掉了这个没有圣盾的可爱大头鱼，就转化为了$f_{n-1}$，概率为$\frac{1}{n}$；否则，转化为了$f_n$(但是有一只可爱的鱼鱼没有圣盾)，概率为$\frac{n-1}{n}$。

用式子表示就是$f_n=\frac{1}{n}(f_{n-1}+1)+\frac{n-1}{n}(f_n+1-1)+1$ 即$f_n=f_{n-1}+n+1$ 即$f_n={\sum }_{i=1}^{n}i+n$ 即$f_n=\frac{n(n+1)}{2}+n$。

期望得分$30$分。

---

处理完了$m=0$的情况，然后处理一波$m=1$的情况。

可以发现，$m=1$相当于是从$n=n+1,m=0$的情况走一步转移而来；例如$n=5,m=1$的情况由$n=6,m=0$的情况转移而来。

设$g_n$表示$m=1$的情况，则有$g_n=f_{n+1}-1=\frac{(n+1)(n+2)}{2}+n$

---

然后处理一般性的情况。

假设现在情况为$n,m$，那么我们有两种走向———干掉了一只无助的不带圣盾的大头鱼($m$减一)，转化为$n,m-1$并继续递归下去；还有一种可能是砍了一只可爱的圣盾大头鱼，使$n$变成$n+m-1$，$m$变成$1$，就转化为了上面$m=1$的情况，可以$O(1)$求出，这也是递归边界。

同时，我们一边递归，要一边下传出现这种情况的概率。注意逆元，并且在递归前要对$n$取模(否则会溢出)。

献上部分代码方便各位巨佬理解：

inline int work(int n,int m,int now,int depth) { if (m==1) return ((work_1(n)+depth)*now)%mod; int ans=0; ans=(ans+work(n+m-1,1,(now*(frac(n,n+m)))%mod,depth+1))%mod; ans=(ans+work(n,m-1,(now*(frac(m,n+m)))%mod,depth+1))%mod; return ans; }

这题太过分了，$T2$就出大期望题，做了我$1.5h$，差点自闭了……

T3

太菜了，比赛的忘记区间平移这个套路了……我太菜了……不然就切掉了……

首先，我们先二分找到一段前缀$[1,r]$，使得这段前缀恰好不小于$s$；即，如果前缀短一点这个值就小于$s$了，长一点就与$s$的差就更大了。显然，这段前缀的和要么是$s$，要么是$s+1$；如果都不是我吃屎。 我们先特判一下这段前缀的和为$s$的情况（直接输出），然后处理棘手的和为$s+1$的情况。

然后，我们开始向右平移这段区间。

我们不是要让这个和为$s$吗？每次向右平移一格，会少掉一个数，多了一个数。我们处理出从第一个位置开始的最长前缀$2$的长度$x$，从$r$开始的最长前缀$2$的长度$y$。

如果$x\ge y$，那么会是这样的一种情况： 即，整个区间向右平移$y$格。

否则，$x＜y$，就这样啦： 即，整个区间向右平移$x$格，此时的左端点再向右一格使和减$1$。

综上所述，我们只需要： ①资瓷单点修改； ②资瓷查询从某个位置开始连续$2$的数量。

显然，我们可以通过二分套线段树或二分套树状数组求出，时间复杂度为$O(nlo{g}^{2}n)$。

但事实上毫无必要，我们直接数据结构内二分即可，时间复杂度为$O(nlogn)$。

唉，真的人傻了……

T4

我没有打算A掉这题，于是就挖了个性质然后上反演拿了$50$分。

如果$p(a,b)=1$，当且仅当： ①$\gcd (a,b)=1$，即$a,b$互质； ②$a$与$b$在膜$2$意义下不同余。

然后，我们写出式子:

${\sum }_{i=1}^n{\sum }_{j=1}^n[gcd(i,j)=1,imod2\ne jmod2]$

哎？这不是个莫反的套路式吗？开心地反演一波：

${\sum }_{i=1}^n{\sum }_{j=1}^n[gcd(i,j)=1,imod2\ne jmod2]$ ${\sum }_{i=1}^n{\sum }_{j=1}^n{\sum }_{d|gcd(i,j)}[imod2\ne jmod2]$ $={\sum }_{d=1}^n\mu (d)even(d)\times odd(d)$。

这里的$even(d)$表示，在$1-n$中所有$d$的倍数有多少个是偶数；$odd(d)$表示，在$1-n$中所有$d$的倍数有多少个是奇数。显然这两个函数都可以$O(1)$求出。

使用线性筛求出莫比乌斯函数后，本题可以$O(n)$做完。可惜的是，这样只有$50$分，而剩下的$50$分，由于我真的太菜了也不会了……QAQ

Code

T1

#include <bits/stdc++.h> #define int long long using namespace std; int t,n; inline int get_it(int k) { return (k*k-k)/2; } inline int read() { int s=0,w=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') w=-w; ch=getchar(); } while (ch>='0'&&ch<='9') { s=(s<<1)+(s<<3)+(ch^'0'); ch=getchar(); } return s*w; } signed main() { t=read(); while (t--) { n=read(); if (n&1) printf("%lld\n",get_it(n)); else printf("%lld\n",get_it(n)-n/2+1); } return 0; }

T2

#include <bits/stdc++.h> #define int long long using namespace std; const int mod=998244353; int n,m; int quick_power(int x,int y) { int res=1; for (;y;y=y>>1,x=(x*x)%mod) { if (y&1) res=(res*x)%mod; } return res; } int ny(int k) { return quick_power(k,mod-2); } int frac(int x,int y) { return (x*ny(y))%mod; } inline int work_1(int n) { n=(n+1)%mod; return (((n*n+n)%mod*ny(2))%mod+n-1)%mod; } inline int work(int n,int m,int now,int depth) { if (m==1) return ((work_1(n)+depth)*now)%mod; int ans=0; ans=(ans+work(n+m-1,1,(now*(frac(n,n+m)))%mod,depth+1))%mod; ans=(ans+work(n,m-1,(now*(frac(m,n+m)))%mod,depth+1))%mod; return ans; } signed main() { cin>>n>>m; n%=mod; if (m==0) { n%=mod; cout<<(((n*n+n)%mod*ny(2))%mod+n)%mod<<endl; return 0; } cout<<work(n,m,1,0)<<endl; return 0; }

T3

`#include <bits/stdc++.h> using namespace std; const int maxl=2000005;

inline int read() { char c=getchar(); int x=0; while(c<‘0’||c>‘9’) c=getchar(); while(c>=‘0’&&c<=‘9’) { x=(x<<3)+(x<<1)+c-‘0’; c=getchar(); } return x; } inline void write(int x) { int sta[10],tp=0; while(x) { sta[++tp]=x%10; x/=10; } while(tp) putchar(sta[tp–]+‘0’); }

int n,q,u,v,a[maxl]; char opt;

struct SEGMENT_TREE { int sumv,cnt1; }tree[maxl<<2];

void pushup(int rt) { tree[rt].sumv=tree[(rt<<1)].sumv+tree[(rt<<1)|1].sumv; tree[rt].cnt1=tree[(rt<<1)].cnt1+tree[(rt<<1)|1].cnt1; }

void build_tree(int l,int r,int rt) { if (l==r) { tree[rt].sumv=a[l],tree[rt].cnt1=(a[l]==1); return; } int mid=(l+r)>>1; build_tree(l,mid,(rt<<1)),build_tree(mid+1,r,(rt<<1)|1); pushup(rt); }

void change(int nl,int l,int r,int rt,int k) { if (lr) { tree[rt].cnt1=(k1),tree[rt].sumv=k; return; } int mid=(l+r)>>1; if (nl<=mid) change(nl,l,mid,(rt<<1),k); else change(nl,mid+1,r,(rt<<1)|1,k);

pushup(rt);

}

int query_sum(int nl,int nr,int l,int r,int rt) { if (nl<=l&&r<=nr) return tree[rt].sumv;

int mid=(l+r)>>1,tot=0; if (nl<=mid) tot=query_sum(nl,nr,l,mid,(rt<<1)); if (nr>mid) tot+=query_sum(nl,nr,mid+1,r,(rt<<1)|1); return tot;

}

int query_1(int nl,int nr,int l,int r,int rt) { if (nl<=l&&r<=nr) return tree[rt].cnt1;

int mid=(l+r)>>1,tot=0; if (nl<=mid) tot=query_1(nl,nr,l,mid,(rt<<1)); if (nr>mid) tot+=query_1(nl,nr,mid+1,r,(rt<<1)|1); return tot;

}

int binary_sum(int x) { int rt=1,l=1,r=n,res=n; while (l<r) { int mid=(l+r)>>1; if (tree[(rt<<1)].sumv>=x) res=mid,r=mid,rt=(rt<<1); else x-=tree[(rt<<1)].sumv,l=mid+1,rt=(rt<<1)|1; } if (tree[rt].sumv<=x) res=max(res,l); return res; }

int binary_1(int x) { int rt=1,l=1,r=n,res=n; while (l<r) { int mid=(l+r)>>1; if (tree[(rt<<1)].cnt1<=x) l=mid+1,x-=tree[(rt<<1)].cnt1,rt=(rt<<1)|1,res=mid; else r=mid,rt=(rt<<1); } if (tree[rt].cnt1<=x) res=max(res,l); return res; }

inline void print(int l,int r,int x) { if (l<=r&&1<=l&&l<=n&&1<=r&&r<=n&&query_sum(l,r,1,n,1)==x) { write(l); putchar(’ ‘); write®; putchar(’\n’); } else puts(“none”); }

int main() { n=read(); q=read(); for (int i=1;i<=n;i++) a[i]=read();

build_tree(1,n,1); while (q--) { opt=getchar(); while(opt!='A'&&opt!='C') opt=getchar(); if (opt=='C') { u=read(),v=read(); change(u,1,n,1,v),a[u]=v; } else { u=read(); int p=binary_sum(u); int tmp=query_sum(1,p,1,n,1); if (tmp==u) printf("%d %d\n",1,p); else { int cnt1,cnt2; if (a[1]==1) cnt1=0; else cnt1=binary_1(0); if (a[p]==1) cnt2=0; else cnt2=binary_1(query_1(1,p,1,n,1))-p+1; if (cnt1>=cnt2) print(cnt2+1,p+cnt2,u); else print(2+cnt1,p+cnt1,u); } } } return 0;

}`## T4

//50 pts #include <bits/stdc++.h> #define int unsigned long long #define rg register using namespace std; const int maxl=30000000; int t,n,pos=0; int judge[maxl+5],prime[maxl/3],m[maxl+5]; inline void init() { for (rg int i=1;i<=maxl;i++) m[i]=1; m[1]=1; for (rg int i=2;i<=maxl;i++) { if (judge[i]==0) m[i]=-1,prime[++pos]=i; for (int j=1;j<=pos;j++) { int now=prime[j]; if (i*now>maxl) break; judge[i*now]=1; if (i%now) m[i*now]=m[i]*m[now]; else { m[i*now]=0; break; } } } } signed main() { cin>>t; init(); while (t--) { cin>>n; int ans=0; for (int i=1;i<=n;i+=2) { int cnt=n/i; int res=(cnt/2)*(cnt-cnt/2); ans+=m[i]*res*2ull; } cout<<ans<<endl; } return 0; }