Codeforces Round #580 (Div. 1)

https://codeforces.com/contest/1205

A. Almost Equal

Just construct it…it’s too much to say, let’s put a code.

#includeusing namespace std; void read(int &x) {x=0;int f=1;char ch=getchar(); for( ;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-' 0';x*=f;} void print(int x) {if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar( x%10+48);}void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair #define vec vector #define pb push_back#define mp make_pair#define fr first#define sc second #define FOR(i,l,r) for(int i=l,i##_r= r;i<=i##_r;i++) const int maxn = 1e6+10;const int inf = 1e9;const lf eps = 1e-8;const int mod = 1e9+7; int n,a[maxn]; int main() {read(n);if(!(n&1)) return puts("NO"),0; puts("YES"); for(int i=1,p=1;i<=n; i++,p^=1) if(p) a[i]=i; else a[i]=n*2-i+2; for(int i=1+n,p=1;i<=n* 2;i++,p^=1) if(p) a[i]=a[in]+1; else a[i]=a[in]-1; for(int i=1;i<=n* 2;i++) printf("%d ",a[i]);puts(""); re turn 0;}

B. Shortest Cycle

It is obvious that each digit can only have at most two digits. This digit is \(1\), otherwise we will get a ring with a minimum length of \(3\).

Then there are only \(100\) multiple points in total, directly \(\rm floyd\ ) Just find the smallest ring.

#includeusing namespace std; #define int long long void read(int &x) {x=0;int f=1;char ch=getchar (); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x* 10+ch-'0';x*=f;} void print(int x) {if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/ 10),putchar(x%10+48);}void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair#define vec vector #define pb push_back#define mp make_pair#define fr first#define sc second #define FOR(i,l,r) for(int i=l, i##_r=r;i<=i##_r;i++) const int maxn = 1e6+10;const int inf = 1e8;const lf eps = 1e-8;const int mod = 1e9+7; int dis[ 150][150],n,a[maxn],w[150][150]; int cmp(int a,int b) {return a>b;} signed main() {read(n); for(int i=1;i<=n;i++) read(a[i]); sort(a+1,a+n+1,cmp);while(n&&a[n]==0) n--; if( n>130) return puts("3"),0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]= w[i ][j]=inf; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((a[i]&a[j])&&i!= j) dis[i][j]=w[i][j]=1;//,printf("%d %d\n",i,j); int ans=inf; for(int k=1 ;k<=n;k++) {for(int i=1;i 
C. Palindromic Paths
 
A lot of details were not written out during the game. . . 
 
First of all, we can find that we can first process each point where \(i+j\) is an even number, and then assume that \((1,2)\) is \(0\), which can also process out \ (i+j\) is an odd number of points. 
 
If the picture obtained now is wrong, all odd points are reversed. 
 
We must be able to find a \(3\times 3\) rectangle on the main symmetry axis that satisfies the  \(s_{i,i}=1,s_{i+2,i+2}=0,i\%2=1\), where the rectangle is \ ((i,i)\sim (i+2,i+2)\), \(s\) represents the value of the current point. 
 
Then we turn the problem into \(n=3\). 
 
Then we ask \((1,1),(2,3)\) and \( (1,2),(3,3)\), and then just judge it casually (there are really many details...), please refer to the code for details. 
 
#includeusing namespace std; void read(int &x) {x=0;int f=1;char ch=getchar(); for( ;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-' 0';x*=f;} void print(int x) {if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar( x%10+48);}void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair #define vec vector #define pb push_back#define mp make_pair#define fr first#define sc second #define FOR(i,l,r) for(int i=l,i##_r= r;i<=i##_r;i++) const int maxn = 1e6+10;const int inf = 1e9;const lf eps = 1e-8;const int mod = 1e9+7; int s[55][55] ,n; int query(int x,int y,int xx,int yy) {printf("? %d %d %d %d\n",x,y,xx,yy);fflush(stdout); int bo;read(bo);return bo;} void get(int x,int y,int xx,int yy) {if(query(x,y,xx,yy)) s[xx][yy]=s[ x][y]; else s[xx][yy]=! s[x][y];} int main() {read(n); s[1][1]=1;int p=0; get(1,1,2,2),get(1, 1,1,3),get(1,1,3,1),get(2,2,3,3); get(1,2,3,2),get(1,2,2,3) ;s[2][1]=query(2,1,2,3)?s[2][3]:!s[2][3]; for(int i=4;i<=n;i++ ) for(int j=1;j<=3;j++) get(i-2,j,i,j); for(int i=1;i<=n;i++) for(int j=4;j <=n;j++) get(i,j-2,i,j); for(int i=1;i<=n;i+=2) {if(!(s[i][i]==1&&s [i+2][i+2]==0)) continue; if(query(i,i,i+1,i+2)) p=!s[i+1][i+2]; else if(query(i,i+1,i+2,i+2)) p=s[i][i+1]; else {if(s[i][i+1]==s[i+ 1][i+2]) p=s[i][i+1]==s[i][i+2]; else p=!s[i][i+1]; }break;} puts ("!"); for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) if((i+j-1)&1 ) printf("%d",s[i][j]); else printf("%d",s[i][j]^p); fflush(stdout); return 0;}
 < h2 id="d.-almost-all">D. Almost All
It’s a god-like question. . Anyway, I didn’t expect
First consider the sub-problem. Assuming that we now have a \(n\) number of points, how to make up the \([0,n-1]\). 
Then suppose that the root node has \(k\) sons respectively as \(x_1..x_k\ ), then for a certain son \(x_p\) attach \(1+\sum_ {i=1}^{p-1}sz_{x_i}\) weight, and then recursively do sub-problems just fine, the correctness is obvious. 
Then if we can find a point, and then divide the sons of this point into two parts, suppose the sum of the previous \(sz\) is \(a\), the next one is \(b\), we can make up \(ab+a-1\) values, because we can multiply the latter part by \(a+1\) span>. 
The maximum number is obviously to be \(a,b\) as close as possible, so if we select a point, then every time we Combining the youngest two sons must be optimal. 
It can be found that if we choose the center of gravity, we can maximize this thing:

If there is currently \(4\) Sons, and each is smaller than \(n/2\), then it’s obviously legal. 
If there are only three, the largest one will be greater than \(n/3\) and less than \( n/2\), it is legal to merge two small ones. 

#includeusing namespace std; void read(int &x) {x=0;int f=1;char ch=getchar( ); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10 +ch-'0';x*=f;} void print(int x) {if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10 ),putchar(x%10+48);}void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair#define vec vector #define pb push_back#define mp make_pair#define fr first#define sc second #define FOR(i,l,r) for(int i=l,i ##_r=r;i<=i##_r;i++) const int maxn = 1e6+10;const int inf = 1e9;const lf eps = 1e-8;const int mod = 1e9+7; int rt,f [maxn],sz[maxn],head[maxn],tot,n;struct edge{int to,nxt;}e[maxn<<1]; void ins(int u,int v) {e[++tot ]=(edge){v,head[u]},head[u]=tot;} void get_rt(int x,int fa) {sz[x]=1; for(int i=head[x];i ;i=e[i].nxt) if(e[i].to!=fa) get_rt(e[i].to,x),sz[x]+=sz[e[i].to], f[x]=max(f[x],sz[e[i].to]); f[x]=max (f[x],n-sz[x]); if(f[x]> q; int fa[maxn];int find (int x) {return fa[x]==x? x:fa[x]=find(fa[x]);} void put_ans(int x,int fa,int t) {int p=1; for( int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) {printf("%d %d %lld\n",x,e[i ].to,1ll*p*t); put_ans(e[i].to,x,t);p+=sz[e[i].to]; }} int main() {read(n); if (n==1) return 0; if(n==2) return puts("1 2 1"),0; for(int i=1;i<=n;i++) fa[i]=i; for (int x,y,i=1;i2) {int x=q.top().sc,a=q.top().fr ;q.pop(); int y=q.top().sc,b=q.top().fr;q.pop(); fa[find(y)]=find(x); q.push (mp(a+b,x));} int a=q.top().sc,s=-q.top().fr;q.pop(); int b=q.top().sc ;q.pop();//if(n==400) write(s); int p=1; for(int i=head[x];i;i=e[i].nxt) if(find(e[i].to)==a) {printf("%d %d %d\n",x,e[i].to,p); put_ans(e[i].to, x,1),p+=sz[e[i].to];} p=1; for(int i=head[x];i;i=e[i].nxt) if(find(e[i ].to)==b) {printf("%d %d %lld\n",x,e[i].to,1ll*p*(s+1)); put_ans(e[i].to ,x,s+1),p+=sz[e[i].to];} return 0;}
E. Expected Value Again< /h2> 

Obviously, it can be found that if the string \(s\) has a length of \(i\) Answer, then if and only if \(s\) has a length of \(|s|-i\)< /span> The loop section. 
Let \(p_x(s)\) indicate whether \(s\) is there The loop section with a length of \(x\), some of which are \(1\), otherwise it is \(0\). 
Then the answer can be written as \(E((p_1(s)+p_2(s)+\cdots +p_{n-1}(s))^2 )\). 
Then, according to the expected linearity, the answer is:
\[ \sum_{i=1}^{n} \sum_{j=1}^{n}E(p_i(s)p_j(s)) \]
That is to say for a \ (i,j\), if \(s\) also has a length of \(i,j\) The loop section of  will contribute a plan to the expectation. If we connect all the positions that must be equal to each other, we will give the expectation a \(k^{cnt-n} \)’s contribution, where \(cnt\) is the number of connected blocks. 
It is assumed here that \(i>j\), otherwise it is the same. 
Then we can divide these \(n\) positions into \(i\)The group is written as a ring, which is the remaining series of $\bmod i $. 
Then the relationship and processing of \(i\) are finished, we need to connect edges on this ring, which is \(x\) Connect edges to \((x+j) \bmod i\). 
If \(i+j\leqslant n\), then every point on the ring can be connected to the back, which will obviously form a \(\gcd(i,j)\) connected blocks. 
Otherwise, only the first \(nj\) points can be connected to the ring. We consider how many rings can be formed, assuming there is \(c\), then the answer is \(n-(ni)-(nj)+c=i+j-n+c\ ). 
Draw a picture and you will know that the starting point of the first connected edge is \(i-\gcd(i,j)+1\), so a total of \(\max(0,nj-(i-\gcd(i,j)+1)+1)\) will be connected. 
Then the answer is \(\max(i+j-n,\gcd(i,j))\). 
Then integrate the above things, the answer to the question is:
 \[ \sum_{i=1}^{n}\sum_{j= 1}^{n}k^{\max(i+jn,\gcd(i,j))-n} \]
 Then it’s just a miracle to work hard In fact, the following calculation is not the point, let's talk about it a little bit. 
Consider the enumeration \(\gcd(i,j)\) and \(i+j\ ) Value:
 \[ k^{-n}\sum_{d=1}^{n-1}\sum_{s=1}^{ 2n-2}k^{\max(sn,d)}cnt_{d,s} \]
 Definition of \(cnt\) (Note that the following are all divisible):
 \[ l=\max(1,\lceil(s-n+1)/d\rceil),r=\min(( n-1)/d,s/d-1)\cnt_{d,s}=\sum_{i=l}^{r}[\gcd(i,s/di)=1]\\]
 Reverse it:
 \[ cnt_{d,s}=\sum_{i=l}^{r}\sum_{t|i,t| s/d}\mu(t)\cnt_{d,s}=\sum_{t|s/d}\mu(t)(\frac{r}{t}-\frac{l-1}{t }) \]
 Just take it with you. 
\(cnt\)A total of \(O(n\log n)\)one, one line at a time\(cnt\) requires \(O(n\log n)\) , So the total complexity is probably \(O(n\log ^2 n)\). 
#includeusing namespace std; void read(int &x) {x=0;int f=1;char ch=getchar(); for( ;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-' 0';x*=f;} void print(int x) {if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar( x%10+48);}void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair #define vec vector #define pb push_back#define mp make_pair#define fr first#define sc second #define FOR(i,l,r) for(int i=l,i##_r= r;i<=i##_r;i++) const int maxn = 2e5+10;const int inf = 1e9;const lf eps = 1e-8;const int mod = 1e9+7; int n,k,pri[maxn ],tot,mu[maxn],vis[maxn],pw[maxn],cnt[maxn]; void sieve() {mu[1]=1; for(int i=2;i>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod; return res;} int main() {read(n),read(k);sieve(); pw[0]=1;int ans=0; for(int i=1;i<=n;i++) pw[ i]=1ll*pw[i-1]*k%mod; for(int d=1;d<=n-1;d++) {int m=(2*n-2)/d; for(int t =1;t<=m;t++) for(int s=t;s<=m;s+=t) cnt[s]+=mu[t]*(min(s-1,(n-1)/ d)/t-max(0,(s*dn)/d)/t); for(int s=1;s<=m;s++) ans=(ans+1ll*pw[max(s*dn, d)]*cnt[s]%mod)%mod; for(int i=0;i<=m+2;i++) cnt[i]=0; }ans=1ll*ans*qpow(qpow(k, n),mod-2)%mod; write(ans); return 0;}
F. Beauty of a Permutation
It’s too amazing to write...it seems to be a new black technology, called the analysis tree.