/* ljc20020730出的HGOI20190407的模拟赛。 考试结果比预期难的不少,可能是由于本来计划5h的比赛打了4h吧。 就当普及组模拟赛好了... 难度大概4紫吧(弱省省选难度) 出境 小F 命题ljc20020730 */
杭高互测比赛,这次轮到我出题。
题目是Typing Competition Round #1
出题人是ljc20020730(捂脸)
这是第一次出题,就出了一些毒瘤题目,下次一定会改进的2333!!!
(虽说Task2会有一点点小锅...,但比起某Task3都没STD的模拟赛来说还是良心了不少)
下面将以出题人的角度评析这场比赛,如果有不足还请dalao多多指教。
题目概括:
求树上每个点的最长链$D_i$,m组询问,对于连续区间$[l,r]subseteq [1,n]$
需满足$Max_{i=l}^{r} D_i - Max_{i=l}^{r} D_i leq Q$
最大化$r-l+1$的值。
Sol : 事实上,这道题目出在Task1并不合适,并不小清新。
首先需要特判第一个点,就是没有乡村的时候特判输出0否则会输出1
其次,对于$ O(n) $求全局最长链可以做Dp,设f[u][0]为子树最长链,f[u][1]为子树次长链
设f[u][2]为从父亲转移过来的最长链,考虑儿子更新父亲(显然f[u][0],f[u][1]可以dfs求出)
$ f[u][2]=Dist{u,v}+Max(f[u][1],f[u][2]) $[v 是 u最长链经过的点]
$ f[u][2]=Dist{u,v}+Max(f[u][0],f[u][2])$ [v 非 u最长链经过的点]
然后对于每个点$D_i = Max(f[i][2],f[i][0])$ 即可
对于部分链的点貌似需要手打栈,其实只需要把根换成$frac{n}{2}$即可通过
通过计算时间复杂度发现对于区间Max值需要O(1)(由于有nm次询问) 所以打了ST表维护就行
使用类似于单调队列的方法可以做到询问复杂度$O(nm)$
总时间复杂度为$O(n +n log_2 n + nm)$,足以通过所有数据。
# include <cstring> # include <cstdio> # include <cmath> # define fp(i,s,t) for(int i=s;i<=t;i++) using namespace std; const int N=50000+10; const int Bit=16; struct rec{ int pre,to,w; }a[N<<1]; int cmin[N][17],cmax[N][17],mark[N],g[N],f[N][3],lg2[N]; bool vis[N]; int tot,head[N]; int n,m,root; inline int max(int a,int b){return (a>b)?a:b;} inline int min(int a,int b){return (a>b)?b:a;} inline int read() { int X=0,w=0; char c=0; while(c<'0'||c>'9') {w|=c=='-';c=getchar();} while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar(); return w?-X:X; } inline void write(int x) { if (x>9) write(x/10); putchar('0'+x%10); } inline void adde(int u,int v,int w) { a[++tot].pre=head[u]; a[tot].to=v; a[tot].w=w; head[u]=tot; } void dfs1(int u) { vis[u]=1; for (int i=head[u];i;i=a[i].pre){ int v=a[i].to; if (vis[v]) continue; dfs1(v); if (f[v][0]+a[i].w>f[u][0]) { mark[u]=v; f[u][1]=f[u][0]; f[u][0]=f[v][0]+a[i].w; } else if (f[v][0]+a[i].w>f[u][1]) { f[u][1]=f[v][0]+a[i].w; } } } void dfs2(int u) { vis[u]=1; for (int i=head[u];i;i=a[i].pre){ int v=a[i].to; if (vis[v]) continue; if (mark[u]==v) f[v][2]=a[i].w+max(f[u][2],f[u][1]); else f[v][2]=a[i].w+max(f[u][2],f[u][0]); dfs2(v); } } void buildRMQ() { memset(cmin,0x3f,sizeof(cmin)); for (int i=1;i<=n;i++) cmax[i][0]=cmin[i][0]=g[i]; for (int i=1;(1<<i)<=n;i++) fp(j,1,n) cmax[j][i]=max(cmax[j][i-1],cmax[j+(1<<(i-1))][i-1]), cmin[j][i]=min(cmin[j][i-1],cmin[j+(1<<(i-1))][i-1]); } int query(int l,int r) { int k=lg2[r-l+1]; return max(cmax[l][k],cmax[r-(1<<k)+1][k])-min(cmin[l][k],cmin[r-(1<<k)+1][k]); } int main() { freopen("travel.in","r",stdin); freopen("travel.out","w",stdout); n=read();m=read(); root=n>>1; if (n==1) { fp(i,1,m) printf("0 "); return 0; } fp(i,1,n) lg2[i]=log2(i); fp(i,1,n-1) { int u=read(),v=read(),w=read(); adde(u,v,w); adde(v,u,w); } dfs1(root); memset(vis,false,sizeof(vis)); dfs2(root); fp(i,1,n) g[i]=max(f[i][0],f[i][2]); buildRMQ(); while (m--) { int q=read(),l=1,ans=0; for (int i=1;i<=n;i++) { while (l<i&&query(l,i)>q) l++; ans=max(i-l+1,ans); } write(ans); putchar(' '); } return 0; }
考试时最高分96分原因是没有特判第一个点...
题目概括:
对于一个RP++语言要求支持
for i = p to q
a = b + c
if a = b then(所有格式严格只会出现$a,b,c$三个字母)
Sol : 细节题目:只需要模拟就可以过75分。
事实上我们会发现多数for循环是没有意义的,分三类讨论即可
1. 赋值 a = b + c套循环
2.累加 a = a + b 套循环
3.乘2 a=a+a套循环
所以可以O(1)处理上面操作。
而对于if 套for 直接拆成if + for按照上面处理即可
而对于for 套 if的情况会发现要么处理对if条件没有影响,此时只需要把if 套在for 外面就行 按照上面处理
要么处理对if条件有影响,但由于a,b,c是大于等于1的所以必然只影响一次,所以直接把for拆掉做if 即可(此处需要判断for 的成立性)
注意处理for循环的时候的倒序循环不需要做处理就行,复杂度可以做到O(length)
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #define int unsigned long long #define ull unsigned long long using namespace std; struct rec { int opt; string a1, a2, a3; } t[10005]; ull a, b, c; int n; string s[10005]; bool pdc(char x) { if (x == 'a' || x == 'b' || x == 'c') return 1; else return 0; } ull val(char x) { if (x == 'a') return a; else if (x == 'b') return b; else if (x == 'c') return c; } ull pow(ull x, int n) { ull ans = 1; while (n) { if (n & 1) ans = ans * x; n >>= 1; x = x * x; } return ans; } inline void give(char ch1, char ch2, char ch3) { if (ch1 == 'a' && ch2 == 'a' && ch3 == 'a') a = a + a; else if (ch1 == 'a' && ch2 == 'a' && ch3 == 'b') a = a + b; else if (ch1 == 'a' && ch2 == 'a' && ch3 == 'c') a = a + c; else if (ch1 == 'a' && ch2 == 'b' && ch3 == 'a') a = b + a; else if (ch1 == 'a' && ch2 == 'b' && ch3 == 'b') a = b + b; else if (ch1 == 'a' && ch2 == 'b' && ch3 == 'c') a = b + c; else if (ch1 == 'a' && ch2 == 'c' && ch3 == 'a') a = c + a; else if (ch1 == 'a' && ch2 == 'c' && ch3 == 'b') a = c + b; else if (ch1 == 'a' && ch2 == 'c' && ch3 == 'c') a = c + c; else if (ch1 == 'b' && ch2 == 'a' && ch3 == 'a') b = a + a; else if (ch1 == 'b' && ch2 == 'a' && ch3 == 'b') b = a + b; else if (ch1 == 'b' && ch2 == 'a' && ch3 == 'c') b = a + c; else if (ch1 == 'b' && ch2 == 'b' && ch3 == 'a') b = b + a; else if (ch1 == 'b' && ch2 == 'b' && ch3 == 'b') b = b + b; else if (ch1 == 'b' && ch2 == 'b' && ch3 == 'c') b = b + c; else if (ch1 == 'b' && ch2 == 'c' && ch3 == 'a') b = c + a; else if (ch1 == 'b' && ch2 == 'c' && ch3 == 'b') b = c + b; else if (ch1 == 'b' && ch2 == 'c' && ch3 == 'c') b = c + c; else if (ch1 == 'c' && ch2 == 'a' && ch3 == 'a') c = a + a; else if (ch1 == 'c' && ch2 == 'a' && ch3 == 'b') c = a + b; else if (ch1 == 'c' && ch2 == 'a' && ch3 == 'c') c = a + c; else if (ch1 == 'c' && ch2 == 'b' && ch3 == 'a') c = b + a; else if (ch1 == 'c' && ch2 == 'b' && ch3 == 'b') c = b + b; else if (ch1 == 'c' && ch2 == 'b' && ch3 == 'c') c = b + c; else if (ch1 == 'c' && ch2 == 'c' && ch3 == 'a') c = c + a; else if (ch1 == 'c' && ch2 == 'c' && ch3 == 'b') c = c + b; else if (ch1 == 'c' && ch2 == 'c' && ch3 == 'c') c = c + c; } inline void workf(char ch1, char ch2, int k) { if (ch1 == 'a' && ch2 == 'a') a = a * pow(2, k); else if (ch1 == 'a' && ch2 == 'b') a = a + k * b; else if (ch1 == 'a' && ch2 == 'c') a = a + k * c; else if (ch1 == 'b' && ch2 == 'a') b = b + k * a; else if (ch1 == 'b' && ch2 == 'b') b = b * pow(2, k); else if (ch1 == 'b' && ch2 == 'c') b = b + k * c; else if (ch1 == 'c' && ch2 == 'a') c = c + k * a; else if (ch1 == 'c' && ch2 == 'b') c = c + k * b; else if (ch1 == 'c' && ch2 == 'c') c = c * pow(2, k); } string aa1; bool fun1() { string a = aa1; int i, len = a.length(); for (i = 0; i < len; i++) if (pdc(a[i])) break; char c1 = a[i]; for (i = i + 1; i < len; i++) if (pdc(a[i])) break; char c2 = a[i]; return val(c1) == val(c2); } string aa2; int fun2() { string a = aa2; int l = 0, r = 0, i, len = a.length(); for (i = 0; i < len; i++) if (a[i] >= '0' && a[i] <= '9') break; for (; i < len; i++) if (a[i] >= '0' && a[i] <= '9') l = (int)l * 10 + a[i] - '0'; else break; for (i = i + 1; i < len; i++) if (a[i] >= '0' && a[i] <= '9') break; for (; i < len; i++) if (a[i] >= '0' && a[i] <= '9') r = (int)r * 10 + a[i] - '0'; else break; int zero = 0; if (l < r) return r - l + 1; else return 0; } bool relation() { int i, len = aa1.length(); for (i = 0; i < len; i++) if (pdc(aa1[i])) break; char c1 = aa1[i]; for (i = i + 1; i < len; i++) if (pdc(aa1[i])) break; char c2 = aa1[i]; len = aa2.length(); for (i = 0; i < len; i++) if (pdc(aa2[i])) break; char c3 = aa2[i]; if (c1 == c3 || c2 == c3) return 1; else return 0; } void work1(int id) { aa1 = t[id].a1; if (!fun1()) return; string a = t[id].a2; int i, len = a.length(); for (i = 0; i < len; i++) if (pdc(a[i])) break; char c1 = a[i]; for (i = i + 1; i < len; i++) if (pdc(a[i])) break; char c2 = a[i]; for (i = i + 1; i < len; i++) if (pdc(a[i])) break; char c3 = a[i]; give(c1, c2, c3); } void work2(int id) { aa2 = t[id].a1; int times = fun2(); if (times<=0) return; string a = t[id].a2; int i, len = a.length(); for (i = 0; i < len; i++) if (pdc(a[i])) break; char c1 = a[i]; for (i = i + 1; i < len; i++) if (pdc(a[i])) break; char c2 = a[i]; for (i = i + 1; i < len; i++) if (pdc(a[i])) break; char c3 = a[i]; if (c2 == c1) workf(c1, c3, times); else if (c3 == c1) workf(c1, c2, times); else give(c1, c2, c3); } void work0(int id) { aa1 = t[id].a1; if (!fun1()) return; t[id].a1 = t[id].a2; t[id].a2 = t[id].a3; work2(id); } void work3(int id) { string a = t[id].a1; int i, len = a.length(); for (i = 0; i < len; i++) if (pdc(a[i])) break; char c1 = a[i]; for (i = i + 1; i < len; i++) if (pdc(a[i])) break; char c2 = a[i]; for (i = i + 1; i < len; i++) if (pdc(a[i])) break; char c3 = a[i]; give(c1, c2, c3); } signed main() { cin >> a >> b >> c >> n; getchar(); for (int i = 1; i <= n; i++) getline(cin, s[i]); int i = 1, cnt = 0; while (i <= n) { if (s[i][0] == 'f') { if (pdc(s[i + 1][0])) { aa2=s[i]; if (fun2()<=0) {i+=2; continue; } t[++cnt] = (rec){ 2, s[i], s[i + 1] }; i += 2; } else { aa2=s[i]; if (fun2()<=0) { i+=3; continue; } aa1 = s[i + 1]; aa2 = s[i + 2]; if (relation()) { t[++cnt] = (rec){ 1, s[i + 1], s[i + 2] }; } else { t[++cnt] = (rec){ 0, s[i + 1], s[i], s[i + 2] }; } i += 3; } } else if (s[i][0] == 'i') { if (pdc(s[i + 1][0])) { t[++cnt] = (rec){ 1, s[i], s[i + 1] }; i += 2; } else { aa2=s[i+1]; if (fun2()<=0) {i+=3; continue; } t[++cnt] = (rec){ 0, s[i], s[i + 1], s[i + 2] }; i += 3; } } else { t[++cnt] = (rec){ 3, s[i] }; i++; } } n = cnt; for (int i = 1; i <= n; i++) { if (t[i].opt == 0) work0(i); else if (t[i].opt == 1) work1(i); else if (t[i].opt == 2) work2(i); else work3(i); } cout << a << " " << b << " " << c << ' '; return 0; }
考场上最高分是65分,原因是没有处理好一些细节和for循环的优化。
考试时应该是最不可做的题目,为了卡一些选手的时间才放的这道题。
所以遇到毒瘤的模拟题数个0 0 0得分可能比一些选手的分高(心态不能崩!!!)
Sol:概括题目显然非常不必要,这道题应该能一眼看出来是线段树+树链剖分的题目。
树链剖分不必多说,考虑线段树维护的信息。
显然,区间平均值直接维护区间和即可,但是方差并不能直接维护。
经过推倒我们可以发现
显然只需要维护一个区间平方和即可,所以当维护一个区间+d的时候
套树剖以后复杂度是$O(n log_2 ^2 n)$
# include <bits/stdc++.h> # define Eps (1e-7) using namespace std; const int N=1e5+10; struct node{ int l,r; double sum,sqr,add; }t[N<<2]; int n,m; inline int read() { int X=0,w=0; char c=0; while(c<'0'||c>'9') {w|=c=='-';c=getchar();} while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar(); return w?-X:X; } double val[N],tmp[N]; struct rec{ int pre,to; }a[N<<1]; int head[N],tot,cntw,top[N]; int size[N],fa[N],w[N],old[N],dep[N],son[N]; void adde(int u,int v) { a[++tot].pre=head[u]; a[tot].to=v; head[u]=tot; } # define ls (x<<1) # define rs ((x<<1)+1) void build(int x,int l,int r) { t[x].l=l; t[x].r=r; if (l==r) { t[x].sum=val[l]; t[x].sqr=val[l]*val[l]; return; } int mid=l+r>>1; build(ls,l,mid); build(rs,mid+1,r); t[x].sum=t[ls].sum+t[rs].sum; t[x].sqr=t[ls].sqr+t[rs].sqr; } void down(int x) { if (fabs(t[x].add)<=Eps) return; double tag=t[x].add; t[x].add=0.0; t[ls].sqr=t[ls].sqr+2*tag*t[ls].sum+1.0*(t[ls].r-t[ls].l+1)*tag*tag; t[rs].sqr=t[rs].sqr+2*tag*t[rs].sum+1.0*(t[rs].r-t[rs].l+1)*tag*tag; t[ls].sum=t[ls].sum+1.0*(t[ls].r-t[ls].l+1)*tag; t[rs].sum=t[rs].sum+1.0*(t[rs].r-t[rs].l+1)*tag; t[ls].add=t[ls].add+tag; t[rs].add=t[rs].add+tag; } void modify(int x,int pos,double d) { if (t[x].l==t[x].r) { t[x].sum=d; t[x].sqr=d*d; return; } down(x); int mid=(t[x].l+t[x].r)>>1; if (pos<=mid) modify(ls,pos,d); else modify(rs,pos,d); t[x].sum=t[ls].sum+t[rs].sum; t[x].sqr=t[ls].sqr+t[rs].sqr; } void update(int x,int opl,int opr,double d) { if (opl<=t[x].l&&t[x].r<=opr) { t[x].sqr=t[x].sqr+2*(t[x].sum)*d+1.0*(t[x].r-t[x].l+1)*d*d; t[x].sum=t[x].sum+1.0*(t[x].r-t[x].l+1)*d; t[x].add=t[x].add+d; return; } down(x); int mid=(t[x].l+t[x].r)>>1; if (opl<=mid) update(ls,opl,opr,d); if (opr>mid) update(rs,opl,opr,d); t[x].sum=t[ls].sum+t[rs].sum; t[x].sqr=t[ls].sqr+t[rs].sqr; } double query_sum(int x,int opl,int opr) { if (opl<=t[x].l&&t[x].r<=opr) return t[x].sum; down(x); int mid=(t[x].l+t[x].r)>>1; double ret=0.0; if (opl<=mid) ret=ret+query_sum(ls,opl,opr); if (opr>mid) ret=ret+query_sum(rs,opl,opr); return ret; } double query_sqr(int x,int opl,int opr) { if (opl<=t[x].l&&t[x].r<=opr) return t[x].sqr; down(x); int mid=(t[x].l+t[x].r)>>1; double ret=0.0; if (opl<=mid) ret=ret+query_sqr(ls,opl,opr); if (opr>mid) ret=ret+query_sqr(rs,opl,opr); return ret; } void dfs1(int u,int fath,int depth) { fa[u]=fath;dep[u]=depth;size[u]=1; for (int i=head[u];i;i=a[i].pre){ int v=a[i].to; if (v==fath) continue; dfs1(v,u,depth+1); size[u]+=size[v]; if (size[son[u]]<size[v]) son[u]=v; } } void dfs2(int u,int tp) { w[u]=++cntw;top[u]=tp; old[cntw]=u; if (son[u]!=0) dfs2(son[u],tp); for (int i=head[u];i;i=a[i].pre){ int v=a[i].to; if (v==fa[u]||v==son[u]) continue; dfs2(v,v); } } double ans1,ans2; void query(int u,int v) { int f1=top[u],f2=top[v],num=0; double ret_sum=0.0,ret_sqr=0.0; while (f1!=f2) { if (dep[f1]<dep[f2]) swap(f1,f2),swap(u,v); num+=(w[u]-w[f1]+1); ret_sum=ret_sum+query_sum(1,w[f1],w[u]); ret_sqr=ret_sqr+query_sqr(1,w[f1],w[u]); u=fa[f1]; f1=top[u]; } if (dep[u]>dep[v]) swap(u,v); num+=(w[v]-w[u]+1); ret_sum=ret_sum+query_sum(1,w[u],w[v]); ret_sqr=ret_sqr+query_sqr(1,w[u],w[v]); ans1=ret_sum/(1.0*num); ans2=ret_sqr/(1.0*num)-(ans1*ans1); } signed main() { freopen("lemontree.in","r",stdin); freopen("lemontree.out","w",stdout); n=read(); for (int i=2;i<=n;i++){ int u=read(),v=read(); adde(u,v); adde(v,u); } dfs1(1,0,0); dfs2(1,0); for (int i=1;i<=n;i++) scanf("%lf",&tmp[i]); for (int i=1;i<=n;i++) val[i]=tmp[old[i]]; build(1,1,n); int op; double x,y; while(~scanf("%d%lf%lf",&op,&x,&y)) { int u,v; double d; if (op==1) { u=(int)x; d=1.0*y; modify(1,w[u],d); } else if (op==2) { u=(int)x; d=(double)y; update(1,w[u],w[u]+size[u]-1,d); } else if (op==3) { u=(int)x; v=(int)y; query(u,v); printf("%.5lf ",ans1); } else if (op==4) { u=(int)x;v=(int)y; if (u==v) { puts("0.000"); continue;} query(u,v); printf("%.5lf ",ans2); } } return 0; }
考试时hjc得分最高拿到44分,原因是使用的cin,读入被卡了
关于cin他已经死了...
剩下的人全部打了2分的部分分什么情况(dfs都不会了么...)
题意概括:
对于第一问50pts询问一个序列的所有子序列bit-and和bit-or 的和各是多少。
对于第二问50pts询问n个盒子里装有奖品,m个人等概率随机 选择奖品,选完之后空盒子放回,求奖品剩余数期望。
Sol:
第一小问:求按位and连续子序列和
对于位运算的题目按位考虑,对于每一位,只有连续为1的区间对 答案产生贡献。
假设第k位上某段连续区间长为len,那么贡献值是$ frac{len imes (len+1)}{2} imes 2 ^k $ 累加所有位的贡献即可。
第二小问:求按位or连续子序列和
只有连续为0的区间对答案产生负贡献,
假设第k位上某段连续区间长为len,
那么贡献值是$ −frac{len imes (len+1)}{ 2} imes 2 ^k $
补集转换即可。
总复杂度$ O(n log_2 n) $
对于第二个问题直接推公式,
对于每个奖品不被选中的概率是$frac{n-1}{n}$
所以对于m个人都没选这个奖品的概率是$(frac{n-1}{n})^m$
所以剩余奖品的期望是$n imes (frac{n-1}{n})^m $
是在mod p=998244353意义下运算,所以直接求逆元
$ (n-1)^m imes (n^{-1})^m imes n $
对于指数部分直接扩展欧拉定理降幂即可,对于大整数求逆部分考虑性质
若a关于b同余那么a,b必然有相同的逆元。
证明如下: 设$a equiv b (mod p)$ 那么必然 $acequiv bc (mod p)$
若c是a的逆元那么$ac equiv 1 (mod p )$那么必然$bc equiv 1 (mod p )$
由逆元的唯一性可证。(事实上可以通过费马小定理求逆元感性理解)
所以根本不需使用高精度复杂度$O(length + 2 log_2 p)$
# include <cstdio> # include <iostream> # define int long long using namespace std; const int mp=998244353; const int N=5e5+10; int res1,res2,pw[32]; inline void read(int Mo,int Phi) { int x=0,X=0,f=0; char c=0; while (!(c>='0'&&c<='9')) c=getchar(); while (c>='0'&&c<='9') { x=(x<<1)+(x<<3)+c-'0';if (x>=Phi)f=1; x%=Phi; X=(X<<1)+(X<<3)+c-'0';X%=Mo; c=getchar(); } res1=X,res2=x+(f==1?Phi:0); } inline int Read() { int X=0,w=0; char c=0; while(c<'0'||c>'9') {w|=c=='-';c=getchar();} while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar(); return w?-X:X; } int a[N],n; int workA() { int ans=0; for (int i=31;~i;i--) { int ret=0; for (int j=1;j<=n;j++) if ((a[j]>>i)&1) ret++; else { ans=(ans+ret*(1+ret)/2%mp*pw[i]%mp)%mp; ret=0; } ans=(ans+ret*(1+ret)/2%mp*pw[i]%mp)%mp; } return ans%mp; } int workB() { int ans=0; for (int i=31;~i;i--) { int ret=0; ans=(ans+n*(1+n)/2%mp*pw[i]%mp)%mp; for (int j=1;j<=n;j++) if ((a[j]>>i)&1) { ans=((ans%mp-(ret*(1+ret)/2%mp*pw[i]%mp))%mp+mp)%mp; ret=0; }else ret++; ans=((ans%mp-(ret*(1+ret)/2%mp*pw[i]%mp))%mp+mp)%mp; } return ans%mp; } int Pow(int x,int n,int p) { int ans=1; for (;n;n>>=1,x=x*x%p) if (n&1) ans=ans*x%p; return ans%p; } int work2() { read(mp,mp-1); int n0=res1,n1=(n0+mp-1)%mp,inv_n=Pow(n0,mp-2,mp); read(mp,mp-1); int m=res2; int ans=Pow(n1,m,mp)*Pow(inv_n,m,mp)%mp*n0%mp; return ans; } signed main() { freopen("future.in","r",stdin); freopen("future.out","w",stdout); n=Read(); pw[0]=1; for (int i=1;i<=31;i++) pw[i]=pw[i-1]*2%mp; for (int i=1;i<=n;i++) a[i]=Read(); cout<<workA()<<' '<<workB()<<' '<<work2()<<' '; return 0; }
最后,考场的评测结果大概是长这样子的。。。
Hjc最巨了!!!