2020-2021:teams:legal_string:组队训练比赛记录:contest4
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/19 20:02] jxm2001 创建 |
2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/25 00:00] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | [[https://ac.nowcoder.com/acm/contest/11166|比赛链接]] | + | [[https://ac.nowcoder.com/acm/contest/11253|比赛链接]] |
| ====== 题解 ====== | ====== 题解 ====== | ||
| + | |||
| + | ===== A. Arithmetic Progression ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个序列，问有多少连续子串从小到大排列后可以构成等差序列。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 给定一个序列 $a_1,a_2\cdots a_n$，则 $\max(a_i)-\min(a_i)\ge (n-1)\times \text{gcd}(a_2-a_1,a_3-a_2\cdots a_n-a_{n-1})$。 | ||
| + | |||
| + | 等号成立充要条件为 $a_1,a_2\cdots a_n$ 从小到大排列后可以构成等差序列。具体见 [[..:jxm2001:other:结论_3#等差序列判定|证明]]。 | ||
| + | |||
| + | 于是问题转化为统计有多少区间满足 $\max(a[l\sim r])-\min(a[l\sim r])=(r-l)\text{gcd}(a_{l+1}-a_l\cdots a_r-a_{r-1})$。 | ||
| + | |||
| + | 考虑构造序列 $b_i=\max(a[i\sim r])-\min(a[i\sim r])+i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$。 | ||
| + | |||
| + | 线段树维护区间最小值和最小值个数，对固定的 $r$，统计 $[i,r](i\lt r)$ 贡献时，枚举 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间。 | ||
| + | |||
| + | 对每个区间将 $b_i=r\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的数值个数计入贡献。 | ||
| + | |||
| + | 易知 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间最多只有 $O(\log v)$ 个，于是总询问次数 $O(n\log v)$。 | ||
| + | |||
| + | 然后移动 $r$ 更新区间，需要维护 $\max(a[l\sim r]),\min(a[l\sim r]),i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的变化。 | ||
| + | |||
| + | 对 $\max(a[l\sim r]),\min(a[l\sim r])$ 的变化可以用单调栈维护，总更新次数 $O(n)$。 | ||
| + | |||
| + | 对 $i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的变化，可以维护 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的段。 | ||
| + | |||
| + | 每次 $r$ 变化时暴力遍历 $O(\log v)$ 个段，每个段的值发生变化时暴力遍历整个段更新。 | ||
| + | |||
| + | 由于每个位置的 $\text{gcd}$ 值最多变化 $O(\log v)$ 次，所以总更新次数 $O(n\log v)$。 | ||
| + | |||
| + | 于是线段树只需要支持区间加操作和区间查询操作，总时间复杂度 $O(n\log n\log v)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5; | ||
| + | struct Node{ | ||
| + | LL v; | ||
| + | int cnt; | ||
| + | Node operator + (const Node &b)const{ | ||
| + | Node c; | ||
| + | if(v==b.v)c.v=v,c.cnt=cnt+b.cnt; | ||
| + | else if(v<b.v)c=*this; | ||
| + | else c=b; | ||
| + | return c; | ||
| + | } | ||
| + | }s[MAXN<<2]; | ||
| + | LL tag[MAXN<<2]; | ||
| + | int lef[MAXN<<2],rig[MAXN<<2]; | ||
| + | void push_up(int k){ | ||
| + | s[k]=s[k<<1]+s[k<<1|1]; | ||
| + | } | ||
| + | void push_add(int k,LL v){ | ||
| + | s[k].v+=v; | ||
| + | tag[k]+=v; | ||
| + | } | ||
| + | void push_down(int k){ | ||
| + | if(tag[k]){ | ||
| + | push_add(k<<1,tag[k]); | ||
| + | push_add(k<<1|1,tag[k]); | ||
| + | tag[k]=0; | ||
| + | } | ||
| + | } | ||
| + | void build(int k,int L,int R){ | ||
| + | lef[k]=L,rig[k]=R,tag[k]=0; | ||
| + | if(L==R){ | ||
| + | s[k].v=0; | ||
| + | s[k].cnt=1; | ||
| + | return; | ||
| + | } | ||
| + | int M=L+R>>1; | ||
| + | build(k<<1,L,M); | ||
| + | build(k<<1|1,M+1,R); | ||
| + | push_up(k); | ||
| + | } | ||
| + | void update(int k,int L,int R,LL v){ | ||
| + | if(L<=lef[k]&&rig[k]<=R){ | ||
| + | push_add(k,v); | ||
| + | return; | ||
| + | } | ||
| + | push_down(k); | ||
| + | int mid=lef[k]+rig[k]>>1; | ||
| + | if(mid>=L) | ||
| + | update(k<<1,L,R,v); | ||
| + | if(mid<R) | ||
| + | update(k<<1|1,L,R,v); | ||
| + | push_up(k); | ||
| + | } | ||
| + | Node query(int k,int L,int R){ | ||
| + | if(L<=lef[k]&&rig[k]<=R) | ||
| + | return s[k]; | ||
| + | push_down(k); | ||
| + | int mid=lef[k]+rig[k]>>1; | ||
| + | if(mid>=R) | ||
| + | return query(k<<1,L,R); | ||
| + | else if(mid<L) | ||
| + | return query(k<<1|1,L,R); | ||
| + | else | ||
| + | return query(k<<1,L,R)+query(k<<1|1,L,R); | ||
| + | } | ||
| + | int gcd(int a,int b){ | ||
| + | while(b){ | ||
| + | int t=b; | ||
| + | b=a%b; | ||
| + | a=t; | ||
| + | } | ||
| + | return a; | ||
| + | } | ||
| + | int a[MAXN],st1[MAXN],st2[MAXN]; | ||
| + | pair<int,int> st3[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int T=read_int(); | ||
| + | while(T--){ | ||
| + | int n=read_int(); | ||
| + | _rep(i,1,n)a[i]=read_int(); | ||
| + | build(1,1,n); | ||
| + | LL ans=n; | ||
| + | int top1=0,top2=0,top3=0; | ||
| + | _rep(i,1,n){ | ||
| + | while(top1&&a[st1[top1]]<=a[i]){ | ||
| + | update(1,st1[top1-1]+1,st1[top1],a[i]-a[st1[top1]]); | ||
| + | top1--; | ||
| + | } | ||
| + | st1[++top1]=i; | ||
| + | while(top2&&a[st2[top2]]>=a[i]){ | ||
| + | update(1,st2[top2-1]+1,st2[top2],a[st2[top2]]-a[i]); | ||
| + | top2--; | ||
| + | } | ||
| + | st2[++top2]=i; | ||
| + | if(i==1)continue; | ||
| + | st3[++top3]=make_pair(abs(a[i]-a[i-1]),i-1); | ||
| + | update(1,i-1,i-1,1LL*(i-1)*st3[top3].first); | ||
| + | for(int j=top3-1;j;j--){ | ||
| + | if(st3[j+1].first%st3[j].first!=0){ | ||
| + | int temp=st3[j].first; | ||
| + | st3[j].first=gcd(st3[j].first,st3[j+1].first); | ||
| + | _rep(k,st3[j-1].second+1,st3[j].second) | ||
| + | update(1,k,k,1LL*k*(st3[j].first-temp)); | ||
| + | } | ||
| + | } | ||
| + | int temp=0; | ||
| + | _rep(j,1,top3){ | ||
| + | if(st3[j].first==st3[temp].first) | ||
| + | st3[temp].second=st3[j].second; | ||
| + | else | ||
| + | st3[++temp]=st3[j]; | ||
| + | } | ||
| + | top3=temp; | ||
| + | _rep(j,1,top3){ | ||
| + | Node temp=query(1,st3[j-1].second+1,st3[j].second); | ||
| + | if(temp.v==1LL*i*st3[j].first) | ||
| + | ans+=temp.cnt; | ||
| + | } | ||
| + | } | ||
| + | enter(ans); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== B. Cannon ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定上下两行格点的数量，规定一个操作是对于其中一行，选择一个点，模仿中国象棋里的炮的攻击规则，中间有且只有一个点，跳到另一个点，然后消失一个点，问所有这种事件的发生数，分有限制和没有限制。有限制指对第一行操作若干步（可以是 $0$ ），然后对第二行操作，之后不能退回到第一行。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 显然如果一行有 $n$ 个点，操作一次的方案数是 $2×(n-2)$ 。之后剩余 $n-1$ 个点，方案数是 $2×(n-3)$ 。所以可以知道 $n$ 个炮操作 $m$ 次的方案数是 $2^{m}{\frac {(n-2)!} {(n-2-m)!}}$ ，为了方便起见我们把 $x-=2,y-=2$ 。于是转变为求$2^{k} \sum {\frac {k!} {i!(k-i)!}} {\frac {n!} {(n-i)!}} {\frac {m!} {(m-(k-i))!}}$ 和 $2^{k} \sum {\frac {n!} {(n-i)!}} {\frac {m!} {(m-(k-i))!}}$ 两个子问题。 | ||
| + | |||
| + | 对于第一个子问题，我们发现可以把 $k!$ 提出来，之后对于里面的式子，可以变成两个组合数的乘积，再利用组合数的常用结论，可以推出其等于 $2^{k}k!C(n+m,k)$ ，这个式子可以通过预处理 $2$ 的方幂，阶乘以及阶乘的逆来 $O(1)$ 求得，于是总共复杂度 $O(n+m)$ 。 | ||
| + | |||
| + | 对于第二个子问题， $2^{k} \sum {\frac {n!} {(n-i)!}} {\frac {m!} {(m-(k-i))!}} = 2^{k} \sum {\frac {n!m!} {(n+m-k)!}} {\frac {(n+m-k)!} {(n-i)!(m-(k-i))!}} = 2^{k} {\frac {n!m!} {(n+m-k)!}} \sum_{i=k-m}^{n} C(n+m-k,i)$ | ||
| + | |||
| + | 虽然没有直接的结论，但是这个可以用步移算法来解决。 | ||
| + | |||
| + | 设 $S(n,m) = \sum_{i=0}^{m} C(n,i)$ ， | ||
| + | |||
| + | 则 $S(n,m+1) = S(n,m) + C(n,m+1),S(n,m-1) = S(n,m) - C(n,m),S(n+1,m) = 2S(n,m) - C(n,m)$ | ||
| + | |||
| + | 于是相当于一个前缀和的问题，然后我们已知的是 $0$ 步的方法是 $1$ ，然后通过枚举 $k$ 我们发现， 减数之间存在关系可以用上述关系式求出下一项的减数，被减数也一样，于是复杂度也是 $O(n+m)$ 。 | ||
| + | |||
| + | 总结：最难的还是推式子，其次是想起来步移算法（可能只有我会想不起来...）。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | |||
| + | const ll maxn=1e7+10; | ||
| + | const ll mod=1e9+9; | ||
| + | ll x,y; | ||
| + | ll jc[maxn],inv[maxn],ec[maxn]; | ||
| + | |||
| + | ll C(int n,int m) { | ||
| + | if(n<m||m<0) return 0; | ||
| + | return jc[n]*inv[m]%mod*inv[n-m]%mod; | ||
| + | } | ||
| + | int main() { | ||
| + | scanf("%lld %lld",&x,&y); | ||
| + | inv[0]=jc[1]=inv[1]=jc[0]=ec[0]=1; | ||
| + | ec[1]=2; | ||
| + | for(int i=2;i<=x+y;i++) { | ||
| + | ec[i]=ec[i-1]*2%mod; | ||
| + | jc[i]=jc[i-1]*i%mod; | ||
| + | inv[i]=(mod-mod/i)*inv[mod%i]%mod; | ||
| + | } | ||
| + | for(int i=2;i<=x+y;i++) inv[i]=inv[i-1]*inv[i]%mod; | ||
| + | ll ans1=0; | ||
| + | for(int i=0;i<=x+y-4;i++) { | ||
| + | ans1=ans1^(ec[i]*jc[i]%mod*C(x+y-4,i)%mod); | ||
| + | } | ||
| + | printf("%lld ",ans1); | ||
| + | ll tmp1=1,tmp2=0; | ||
| + | ll ans2=0; | ||
| + | x-=2;y-=2; | ||
| + | ll tt=jc[x]*jc[y]%mod; | ||
| + | for(int i=0;i<=x+y;i++) { | ||
| + | ans2=ans2^((ec[x+y-i]*tt%mod*inv[i]%mod*(tmp1-tmp2)%mod+mod)%mod); | ||
| + | tmp1=(tmp1*2%mod-C(i,x)+mod)%mod; | ||
| + | //tmp2=(tmp2*2%mod-C(i,x-i-1)*2%mod-C(i,x-i-2)+mod*2)%mod; | ||
| + | tmp2=(tmp2*2%mod+C(i,i-y))%mod; | ||
| + | } | ||
| + | printf("%lld\n",ans2); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | ===== G. League of Legends ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $n$ 条线段，要求将线段分为 $k$ 组，使得每组的线段交非空，最大化每组组的线段交之和。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 首先假定所有线没有互相包含的关系，将所有线段 $[l_i,r_i)$ 按 $r_i$ 从大到小排列，设 $\text{dp}(i,j)$ 表示将 $j$ 条线段分到 前 $i$ 组得到的答案。 | ||
| + | |||
| + | 将第 $j+1$ 到 $k$ 条线段分到同一组，如果 $l_k\gt r_{j+1}$，则线段交非空且 $\text{dp}(i-1,j)$ 合法，不难得到如下状态转移 | ||
| + | |||
| + | $$ | ||
| + | \text{dp}(i,k)\gets \text{dp}(i-1,j)+l_k-r_{j+1} | ||
| + | $$ | ||
| + | |||
| + | 由于所有线没有互相包含的关系且 $r_i$ 递减，不难发现 $l_i$ 也递减。 | ||
| + | |||
| + | 因此对 $i\gt j$，如果 $l_k\le r_{i+1}$，则一定有 $l_k\le r_{j+1}$。同时如果 $l_j\le r_{k+1}$，则 $l_i\le r_{k+1}$，所以决策具有单调性。 | ||
| + | |||
| + | 于是每个 $i$，$O(n)$ 单调队列维护所有合法 $\text{dp}(i-1,j)-r_{j+1}$ 即可。总时间复杂度 $O(nk)$。 | ||
| + | |||
| + | 接下来考虑某些可以包含其他线段的线段，首先将任何一条线段放入一个已经存在的组一定使得答案不增。 | ||
| + | |||
| + | 而如果要将一条包含其他线段的线段放入一个已经存在的组，则将它放入一个被它包含的线段所在的组一定使得答案不减，是最佳选择。 | ||
| + | |||
| + | 因此对满足上述条件的线段只有两种最优选择，一种是放入已经存在的组，这样对答案无贡献。一种是创建一个组，这样贡献为该线段长度。 | ||
| + | |||
| + | 于是可以处理完所有不包含其他线段的线段，然后枚举他们分成的组数 $i$，然后取前 $k-i$ 条包含其他线段的线段独立建组构成答案。 | ||
| + | |||
| + | 至于如果判定一条线段是否包含其他线段，可以将所有线段按 $r_i$ 第一关键字从大到小排序 $l_i$ 第二关键字从小到大排序，然后维护最小右端点。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5e3+5,inf=1e9; | ||
| + | struct Seg{ | ||
| + | int l,r; | ||
| + | bool operator < (const Seg &b)const{ | ||
| + | return l>b.l||(l==b.l&&r<b.r); | ||
| + | } | ||
| + | }seg[MAXN],a[MAXN]; | ||
| + | int len[MAXN],dp[MAXN][MAXN]; | ||
| + | pair<int,int> que[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),k=read_int(); | ||
| + | _for(i,0,n){ | ||
| + | seg[i].l=read_int(); | ||
| + | seg[i].r=read_int(); | ||
| + | } | ||
| + | sort(seg,seg+n); | ||
| + | int minr=inf,n1=0,n2=0; | ||
| + | _for(i,0,n){ | ||
| + | if(seg[i].r<minr){ | ||
| + | minr=seg[i].r; | ||
| + | a[++n1]=seg[i]; | ||
| + | } | ||
| + | else | ||
| + | len[++n2]=seg[i].r-seg[i].l; | ||
| + | } | ||
| + | mem(dp,-1); | ||
| + | dp[0][0]=0; | ||
| + | _rep(i,1,k){ | ||
| + | int head=0,tail=-1; | ||
| + | _rep(j,1,n1){ | ||
| + | if(~dp[i-1][j-1]){ | ||
| + | pair<int,int> t=make_pair(dp[i-1][j-1]-a[j].l,-a[j].l); | ||
| + | while(head<=tail&&que[tail]<t)tail--; | ||
| + | que[++tail]=t; | ||
| + | } | ||
| + | while(head<=tail&&a[j].r+que[head].second<=0)head++; | ||
| + | if(head<=tail) | ||
| + | dp[i][j]=que[head].first+a[j].r; | ||
| + | } | ||
| + | } | ||
| + | sort(len+1,len+n2+1,greater<int>()); | ||
| + | _rep(i,1,n2)len[i]+=len[i-1]; | ||
| + | int ans=0; | ||
| + | _rep(i,0,min(n2,k)){ | ||
| + | if(~dp[k-i][n1]) | ||
| + | ans=max(ans,dp[k-i][n1]+len[i]); | ||
| + | } | ||
| + | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== J. Product of GCDs ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给 $S$ 个数字，让你求出所有子集大小为 $k$ 的集合中的数的最大公因数之积。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 我们可以分成质数来考虑这个问题，分别统计不同数字在整个序列中有多少个数能除开它，这个操作是可以 $mlogm$ 完成的，其中 $m$ 是数字大小范围。 | ||
| + | |||
| + | 当我们统计出不同质数的方幂在序列中被除开的个数时，我们可以用组合数求出来有多少个集合的最大公约数能够除开这个数，并且统计这个集合的次数恰好等于这个质数的方幂数，我们将所有次数加在一起，是一个质数在最后答案出现的次数，先求出 $P$ 的欧拉函数，用次数取模，最后用快速幂算一下，将所有这些答案乘起来就是最后的答案了，又因为我们算的是乘法并且每次的质数不一样，所以保证了正确性。 | ||
| + | |||
| + | 其中我们需要预处理出 $P$ 的所有素因子（为了求欧拉函数值），处理出序列中有多少个数字能除开范围内的任意一个数字。处理出组合数对欧拉函数值取模，最后统计答案就是找所有的素数，看他们的方幂出现的次数，相加，对欧拉函数值取模，最后再快速幂乘起来，就可以愉悦 $AC$ 本题了。 | ||
| + | |||
| + | 当然，如果觉得慢可以用 $Pollard\_rho$ 来加速分解质因数过程，这样筛的时候就没必要筛到根号 $P$ 了，效率会快很多，如下面第二份代码所示。 | ||
| + | |||
| + | <hidden 代码1> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | |||
| + | inline int read() { | ||
| + | int X=0,w=1; | ||
| + | char c=getchar(); | ||
| + | while (c<'0'||c>'9') { | ||
| + | if (c=='-') w=-1; | ||
| + | c=getchar(); | ||
| + | } | ||
| + | while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar(); | ||
| + | return X*w; | ||
| + | } | ||
| + | inline void write(int x){ | ||
| + | char c[21],len=0; | ||
| + | if(!x)return putchar('0'),void(); | ||
| + | if(x<0)x=-x,putchar('-'); | ||
| + | while(x)c[++len]=x%10,x/=10; | ||
| + | while(len)putchar(c[len--]+48); | ||
| + | } | ||
| + | |||
| + | inline ll quick_mul(ll a,ll b,ll p){ | ||
| + | return (ll)((__int128)a*b%p); | ||
| + | } | ||
| + | inline ll quick_power(ll a,ll b,ll p){ | ||
| + | ll ret=1; | ||
| + | while(b){ | ||
| + | if(b&1) ret=quick_mul(ret,a,p); | ||
| + | a=quick_mul(a,a,p); | ||
| + | b>>=1; | ||
| + | } | ||
| + | while(ret<0) ret+=p; | ||
| + | return ret%p; | ||
| + | } | ||
| + | |||
| + | const int maxn=80000+5,maxs=40000+5,maxk=30+2,D=1e7+10,PD=1e6+3; | ||
| + | int T,S,k; | ||
| + | ll P; | ||
| + | int sum[maxn],prime[PD],ps; | ||
| + | long long C[maxs][maxk]; | ||
| + | bool isPrime[D]; | ||
| + | inline void initial() { | ||
| + | memset(isPrime, 1, sizeof(isPrime)); | ||
| + | for (int i = 2; i < D; ++i) { | ||
| + | if (isPrime[i]) { | ||
| + | prime[ps++]=i; | ||
| + | for (int j = i + i; j < D; j += i) { | ||
| + | isPrime[j] = false; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() { | ||
| + | initial(); | ||
| + | T=read(); | ||
| + | while(T--) { | ||
| + | S=read(); k=read(); scanf("%lld",&P); | ||
| + | for(int i=0;i<maxn;i++) sum[i]=0; | ||
| + | for(int i=0,tmp; i<S; i++) { | ||
| + | tmp=read(); | ||
| + | sum[tmp]++; | ||
| + | } | ||
| + | for(int i=2; i<maxn; i++) { | ||
| + | for(int j=i+i; j<maxn; j+=i) { | ||
| + | sum[i]+=sum[j]; | ||
| + | } | ||
| + | } | ||
| + | long long tmp=P,phi_ans=1; | ||
| + | for(int i=0; i<ps; i++) { | ||
| + | if(tmp%prime[i]==0) { | ||
| + | phi_ans=phi_ans*(prime[i]-1); | ||
| + | tmp/=prime[i]; | ||
| + | while(!(tmp%prime[i])) { | ||
| + | tmp/=prime[i]; | ||
| + | phi_ans*=prime[i]; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | if(tmp>1) phi_ans=phi_ans*(tmp-1); | ||
| + | for(int i=0; i<=S; i++) { | ||
| + | C[i][0]=1; | ||
| + | for(int j=1; j<=i&&j<=k; j++) { | ||
| + | C[i][j] = C[i-1][j] + C[i-1][j-1]; | ||
| + | while(C[i][j]>=phi_ans+phi_ans) C[i][j]-=phi_ans; | ||
| + | } | ||
| + | } | ||
| + | long long num; | ||
| + | ll ans=1; | ||
| + | for(int i=2; i<maxn; i++) { | ||
| + | if(isPrime[i]) { | ||
| + | num=0; | ||
| + | for(ll j=i; j<maxn; j*=i) { | ||
| + | num+=C[sum[j]][k]; | ||
| + | while(num>=phi_ans+phi_ans) num-=phi_ans; | ||
| + | } | ||
| + | ans=quick_mul(ans,quick_power(i,num,P),P); | ||
| + | //printf("%d %d %lld\n",i,num,ans); | ||
| + | } | ||
| + | } | ||
| + | printf("%lld\n",ans); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | |||
| + | |||
| + | <hidden 代码2> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | |||
| + | const int maxn=80000+5,maxs=40000+5,maxk=30+2; | ||
| + | int T,S,k; | ||
| + | ll P,maxv; | ||
| + | int sum[maxn],prime[maxn],ps; | ||
| + | long long C[maxs][maxk]; | ||
| + | bool isPrime[maxn]; | ||
| + | inline void initial() { | ||
| + | memset(isPrime, 1, sizeof(isPrime)); | ||
| + | for (int i = 2; i < maxn; ++i) { | ||
| + | if (isPrime[i]) { | ||
| + | prime[ps++]=i; | ||
| + | for (int j = i + i; j < maxn; j += i) { | ||
| + | isPrime[j] = false; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | inline int read() { | ||
| + | int X=0,w=1; | ||
| + | char c=getchar(); | ||
| + | while (c<'0'||c>'9') { | ||
| + | if (c=='-') w=-1; | ||
| + | c=getchar(); | ||
| + | } | ||
| + | while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar(); | ||
| + | return X*w; | ||
| + | } | ||
| + | inline void write(int x) { | ||
| + | char c[21],len=0; | ||
| + | if(!x)return putchar('0'),void(); | ||
| + | if(x<0)x=-x,putchar('-'); | ||
| + | while(x)c[++len]=x%10,x/=10; | ||
| + | while(len)putchar(c[len--]+48); | ||
| + | } | ||
| + | |||
| + | inline ll quick_mul(ll a,ll b,ll p) { | ||
| + | return (ll)((__int128)a*b%p); | ||
| + | } | ||
| + | inline ll quick_power(ll a,ll b,ll p) { | ||
| + | ll ret=1; | ||
| + | while(b) { | ||
| + | if(b&1) ret=quick_mul(ret,a,p); | ||
| + | a=quick_mul(a,a,p); | ||
| + | b>>=1; | ||
| + | } | ||
| + | while(ret<0) ret+=p; | ||
| + | return ret%p; | ||
| + | } | ||
| + | struct Pollard_rho { | ||
| + | bool check(ll a,ll n,ll x,ll t) { | ||
| + | ll ans=quick_power(a,x,n); | ||
| + | ll aans=ans; | ||
| + | for(int i=1; i<=t; i++) { | ||
| + | ans=quick_mul(ans,ans,n); | ||
| + | if(ans==1&&aans!=1&&aans!=n-1) return true; | ||
| + | aans=ans; | ||
| + | } | ||
| + | if(ans!=1) return true; | ||
| + | return false; | ||
| + | } | ||
| + | bool Miller_Rabin(ll n) { | ||
| + | if(n<2) return false; | ||
| + | if(n==2) return true; | ||
| + | if(!(n&1)) return false; | ||
| + | ll x=n-1,t=0; | ||
| + | while(!(x&1)) { | ||
| + | x>>=1; | ||
| + | t++; | ||
| + | } | ||
| + | for(int i=0; i<20; i++) { | ||
| + | ll a=rand()%(n-1)+1; | ||
| + | if(check(a,n,x,t)) return false; | ||
| + | } | ||
| + | return true; | ||
| + | } | ||
| + | ll gcd(ll x,ll y) { | ||
| + | if(!x) return y; | ||
| + | if(!y) return x; | ||
| + | if(x<0) x=-x; | ||
| + | if(y<0) y=-y; | ||
| + | ll t=__builtin_ctzll(x|y); | ||
| + | x>>=__builtin_ctzll(x); | ||
| + | do { | ||
| + | y>>=__builtin_ctzll(y); | ||
| + | if(x>y) swap(x,y); | ||
| + | y-=x; | ||
| + | } while(y); | ||
| + | return x<<t; | ||
| + | } | ||
| + | ll pollard_rho(ll x,ll c) { | ||
| + | ll ci=1,k=2; | ||
| + | srand(time(NULL)); | ||
| + | ll x0=rand()%(x-1)+1; | ||
| + | ll y=x0,t=1; | ||
| + | while(1) { | ||
| + | ci++; | ||
| + | x0=(quick_mul(x0,x0,x)+c)%x; | ||
| + | t=quick_mul(y-x0,t,x); | ||
| + | if(!t||!(y^x0)) return x; | ||
| + | if(ci==k) { | ||
| + | ll d=gcd(t,x); | ||
| + | if(d!=1) return d; | ||
| + | y=x0; | ||
| + | k<<=1; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | void findfac(ll n,ll k) { | ||
| + | if(n==1) return; | ||
| + | if(Miller_Rabin(n)) { | ||
| + | if(n>maxv) maxv=n; | ||
| + | return; | ||
| + | } | ||
| + | ll p=n,c=k; | ||
| + | while(p>=n) { | ||
| + | p=pollard_rho(p,c--); | ||
| + | } | ||
| + | findfac(p,k); | ||
| + | findfac(n/p,k); | ||
| + | } | ||
| + | }pr; | ||
| + | |||
| + | int main() { | ||
| + | initial(); | ||
| + | T=read(); | ||
| + | while(T--) { | ||
| + | S=read(); | ||
| + | k=read(); | ||
| + | scanf("%lld",&P); | ||
| + | for(int i=0; i<maxn; i++) sum[i]=0; | ||
| + | for(int i=0,tmp; i<S; i++) { | ||
| + | tmp=read(); | ||
| + | sum[tmp]++; | ||
| + | } | ||
| + | for(int i=2; i<maxn; i++) { | ||
| + | for(int j=i+i; j<maxn; j+=i) { | ||
| + | sum[i]+=sum[j]; | ||
| + | } | ||
| + | } | ||
| + | long long tmp=P,phi_ans=1; | ||
| + | maxv=0; | ||
| + | while(tmp!=1) { | ||
| + | pr.findfac(tmp,324757); | ||
| + | tmp/=maxv; | ||
| + | phi_ans*=(maxv-1); | ||
| + | while(tmp%maxv==0) { | ||
| + | tmp/=maxv; | ||
| + | phi_ans*=maxv; | ||
| + | } | ||
| + | maxv=0; | ||
| + | } | ||
| + | for(int i=0; i<=S; i++) { | ||
| + | C[i][0]=1; | ||
| + | for(int j=1; j<=i&&j<=k; j++) { | ||
| + | C[i][j] = C[i-1][j] + C[i-1][j-1]; | ||
| + | while(C[i][j]>=phi_ans+phi_ans) C[i][j]-=phi_ans; | ||
| + | } | ||
| + | } | ||
| + | long long num; | ||
| + | ll ans=1; | ||
| + | for(int i=2; i<maxn; i++) { | ||
| + | if(isPrime[i]) { | ||
| + | num=0; | ||
| + | for(ll j=i; j<maxn; j*=i) { | ||
| + | num+=C[sum[j]][k]; | ||
| + | while(num>=phi_ans+phi_ans) num-=phi_ans; | ||
| + | } | ||
| + | ans=quick_mul(ans,quick_power(i,num,P),P); | ||
| + | } | ||
| + | } | ||
| + | printf("%lld\n",ans); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | |||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== L. WeChat Walk ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一张图 $n$ 个点 $m$ 条边。每个点初始权值为 $0$，接下来 $q$ 个单位时间，每个单位时间仅增加一个点的权值。 | ||
| + | |||
| + | 当一个点的权值严格大于所有与自己相邻的点时，这个点成为冠军。问每个点作为冠军的时间。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 考虑分块，设分块大小为 $S\sim O(\sqrt n)$。每个点 $u$ 维护自己作为冠军的开始时间，当一个点不再是冠军时加入答案。 | ||
| + | |||
| + | 称度数不大于 $S$ 的点为一类点，其余点为二类点。 | ||
| + | |||
| + | 对于一类点，暴力遍历相邻的点判断自己是否称为冠军顺便更新相邻的点即可。 | ||
| + | |||
| + | 对于二类点 $u$，先考虑如何更新相邻点的冠军，考虑维护 $S(u,w)$ 表示与 $u$ 相邻且权值等于 $w$ 的点的集合。 | ||
| + | |||
| + | 设 $u$ 权值更新前为 $w_1$，更新后为 $w_2$，不难发现更新 $u$ 只会导致权值位于 $(w_1,w_2]$ 之间的点的冠军情况发生变化，于是暴力扫描即可。 | ||
| + | |||
| + | 最后需要判定 $u$ 是否为冠军，考虑维护 $\text{maxw}(u)$ 表示与 $u$ 相邻的点的最大权值。 | ||
| + | |||
| + | 于是只需要在更新所有类型点权值时暴力遍历相邻的二类点并更新他们即可。 | ||
| + | |||
| + | 由于二类点最多只有 $O(\sqrt n)$ 个，所以每次更新最多使得 $\sum |S(u,w)|$ 增加 $O(\sqrt n)$。于是总时间复杂度 $O(n\sqrt n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=2e5+5,MAXS=505,MAXW=1e4+5; | ||
| + | vector<int> g[MAXN],g2[MAXN],g3[MAXS][MAXW]; | ||
| + | int ans[MAXN],val[MAXN],last[MAXN],maxw[MAXN],bmap[MAXN],bsz; | ||
| + | void update(int u,int v,int t){ | ||
| + | if(last[v]!=-1&&val[v]<=val[u]){ | ||
| + | ans[v]+=t-last[v]; | ||
| + | last[v]=-1; | ||
| + | } | ||
| + | if(g[v].size()>bsz){ | ||
| + | maxw[v]=max(maxw[v],val[u]); | ||
| + | g3[bmap[v]][val[u]].push_back(u); | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(),q=read_int(),bcnt=0; | ||
| + | bsz=sqrt(n)+1; | ||
| + | _for(i,0,m){ | ||
| + | int u=read_int(),v=read_int(); | ||
| + | g[u].push_back(v); | ||
| + | g[v].push_back(u); | ||
| + | } | ||
| + | _rep(u,1,n){ | ||
| + | if(g[u].size()>bsz){ | ||
| + | bmap[u]=bcnt++; | ||
| + | _for(i,0,g[u].size()){ | ||
| + | int v=g[u][i]; | ||
| + | if(g[v].size()>bsz) | ||
| + | g2[u].push_back(v); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | mem(last,-1); | ||
| + | _rep(tim,1,q){ | ||
| + | int u=read_int(),w=read_int(); | ||
| + | val[u]+=w; | ||
| + | if(g[u].size()<=bsz){ | ||
| + | if(last[u]==-1) | ||
| + | last[u]=tim; | ||
| + | _for(i,0,g[u].size()){ | ||
| + | int v=g[u][i]; | ||
| + | if(val[v]>=val[u]) | ||
| + | last[u]=-1; | ||
| + | update(u,v,tim); | ||
| + | } | ||
| + | } | ||
| + | else{ | ||
| + | if(val[u]>maxw[u]&&last[u]==-1) | ||
| + | last[u]=tim; | ||
| + | _for(i,0,g2[u].size()){ | ||
| + | int v=g2[u][i]; | ||
| + | update(u,v,tim); | ||
| + | } | ||
| + | int idx=bmap[u]; | ||
| + | _rep(k,val[u]-w+1,val[u]){ | ||
| + | _for(i,0,g3[idx][k].size()){ | ||
| + | int v=g3[idx][k][i]; | ||
| + | update(u,v,tim); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | _rep(u,1,n){ | ||
| + | if(last[u]!=-1) | ||
| + | ans[u]+=q-last[u]; | ||
| + | enter(ans[u]); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| ====== 赛后总结 ====== | ====== 赛后总结 ====== | ||
| jxm：过了签到后就一直debug，先给自己de，然后帮队友de，<del>后来de不下去直接重写了一份</del>。再后来就开始罚坐了，甚至没把所有题看完，或许下次应该在罚坐的时候把所有题先看一遍？ | jxm：过了签到后就一直debug，先给自己de，然后帮队友de，<del>后来de不下去直接重写了一份</del>。再后来就开始罚坐了，甚至没把所有题看完，或许下次应该在罚坐的时候把所有题先看一遍？ | ||
| + | |||
| + | wzb：罚时场被干碎了，下次不能这么莽的... | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest4.1626696167.txt.gz · 最后更改: 2021/07/19 20:02 由 jxm2001
