# 2021 Niuke summer multi school training camp 2

## C.Draw Grids

Meaning: n × m points, both sides operate in turn. Each round can select two points connected horizontally or vertically. It is required that a closed polygon cannot be formed. The person who cannot operate first loses the game

Analysis: firstly, the condition that a closed polygon cannot be formed is transformed into that a ring cannot be generated in the graph, then n × m points can only be connected to N at most × m-1 edge and must be connected to n × m-1 edge (no strict proof, intuition)

Therefore, the answer can be determined by the parity of the total number of points

code:

#include <cstdio>
using namespace std;

int main(){
int n,m;
scanf("%d%d",&n,&m);
if(n*m%2==0) printf("YES");
else printf("NO");
return 0;
}



## D.Er Ba Game

Give five conditions and judge which side wins according to the conditions...

code:

#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
int T;
scanf("%d",&T);
while(T--){
int a[3],b[3],ret[3];
scanf("%d%d%d%d",&a[1],&b[1],&a[2],&b[2]);
for(int i=1;i<=2;i++){
if(a[i]>b[i]) swap(a[i],b[i]);
if(a[i]==2&&b[i]==8) ret[i]=1;
else if(a[i]==b[i])  ret[i]=2;
else ret[i]=3;
}
if(ret[1]<ret[2]) printf("first\n");
else if(ret[2]<ret[1]) printf("second\n");
else if(ret[1]==1) printf("tie\n");
else if(ret[1]==2){
if(a[1]>a[2]) printf("first\n");
else if(a[2]>a[1]) printf("second\n");
else printf("tie\n");
}
else if((a[1]+b[1])%10>(a[2]+b[2])%10) printf("first\n");
else if((a[1]+b[1])%10<(a[2]+b[2])%10) printf("second\n");
else if(b[1]>b[2]) printf("first\n");
else if(b[1]<b[2]) printf("second\n");
else printf("tie\n");
}
return 0;
}



## F.Girlfriend

Find the volume intersection of two spheres

Analysis: it is not difficult to see from the title that it is Apollo nice sphere, and the larger the k, the smaller the sphere, so the title is converted to the intersection of the volumes of two spheres

The answer is divided into two parts:
1) The center and radius of the ball are obtained from the problem conditions
2) Sphere volume (set of templates)

Pushing formulas is very troublesome, it is easy to make some small mistakes, and it is painful to check...

code:

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

const double PI=acos(-1.0);
typedef struct{
double x,y,z;
}Point;  //spot

typedef struct{
Point p;    //Ball center
}Ball;

double pow3(double x){return x*x*x;}
double dis(Point A,Point B){
return sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y)+(B.z-A.z)*(B.z-A.z));
}

Ball fun(Point A,Point B,int k){
Ball ret; Point s;
ret.r=dis(A,B)/(k+1)/(k-1)*k;
s.x=((k*B.x+A.x)/(k+1)+(k*B.x-A.x)/(k-1))/2;
s.y=((k*B.y+A.y)/(k+1)+(k*B.y-A.y)/(k-1))/2;
s.z=((k*B.z+A.z)/(k+1)+(k*B.z-A.z)/(k-1))/2;
ret.p=s;
return ret;
}

double intersection(Ball A,Ball B){
double d=dis(A.p,B.p);
if(d>=A.r+B.r) return 0.0;
if(d<=fabs(A.r-B.r)) return 4.0/3.0*PI*pow3(min(A.r,B.r));
double v=0;
double cos=(A.r*A.r+d*d-B.r*B.r)/(2.00*d*A.r);
double h=A.r*(1.00-cos);
v+=(1.00/3.00)*PI*(3.00*A.r-h)*h*h;
cos=(B.r*B.r+d*d-A.r*A.r)/(2.00*d*B.r);
h=B.r*(1.00-cos);
v+=(1.00/3.00)*PI*(3.00*B.r-h)*h*h;
return v;
}

int main(){
int T;
scanf("%d",&T);
while(T--){
Point A,B,C,D;
int k1,k2;
scanf("%lf%lf%lf",&A.x,&A.y,&A.z);
scanf("%lf%lf%lf",&B.x,&B.y,&B.z);
scanf("%lf%lf%lf",&C.x,&C.y,&C.z);
scanf("%lf%lf%lf",&D.x,&D.y,&D.z);
scanf("%d%d",&k1,&k2);
Ball b1=fun(A,B,k1);
Ball b2=fun(C,D,k2);
double ans=intersection(b1,b2);
printf("%.7lf\n",ans);
}
return 0;
}



## I.Penguins

Meaning: two penguins walk the maze at the same time. The U/D operation will make two penguins move up / down at the same time, and the L/R will make two penguins move in the opposite direction, which will be offset when encountering obstacles

Emm can search for the shortest circuit, but it looks like trouble...
await a vacancy or job opening

## K.Stack

Given the stack size of a monotone stack at several times, construct a legal sequence (the sequence is a permutation)

## J.Product of GCDs

Given n numbers, find the product of gcd values of all subsets of N numbers with length k

Pre knowledge:

• Recursive combination number: C(i,j)=C(i-1,j)+C(i-1,j-1)
• Prime sieve
• Finding the value of Euler function
• Counting
• Euler power reduction

The knowledge requirements of combinatorial mathematics + number theory are relatively high

The contribution is calculated according to the quality factor, and the quality factor is considered p t p^t pt's contribution:

Suppose there is n u m [ t ] num[t] num[t] number contains factor p t p^{t} pt (will contain factor) p t + 1 , p t + 2 p^{t+1},p^{t+2} The number of pt+1, pt+2, etc. are also included in the statistics), so the scheme of selecting k numbers from them is C ( n u m [ t ] , k ) C(num[t],k) C(num[t],k)； That is to say, yes C ( n u m [ t ] , k ) C(num[t],k) C(num[t],k) scheme selects k numbers so that gcd of k numbers is p t p^{t} Multiple of pt

But this scheme includes gcd as p t + 1 , p t + 2 p^{t+1},p^{t+2} For the scheme of multiple of pt+1, pt+2, etc., if you want the gcd of k numbers to be exactly p c p^c The number of PCs is obviously C ( n u m [ t ] , k ) − C ( n u m [ t + 1 ] , k ) C(num[t],k)-C(num[t+1],k) C(num[t],k) − C(num[t+1],k) (differential)

that p t p^t The contribution of pt is p t C ( n u m [ t ] , k ) − C ( n u m [ t + 1 ] , k ) {p^t}^{C(num[t],k)-C(num[t+1],k)} ptC(num[t],k)−C(num[t+1],k)

Further, the contribution of prime number p is:

p 1 ∗ C ( n u m [ 1 ] , k ) − C ( n u m [ 2 ] , k ) ∗ p 2 ∗ C ( n u m [ 2 ] , k ) − C ( n u m [ 3 ] , k ) ⋅ ⋅ ⋅ p^{1*C(num[1],k)-C(num[2],k)}*p^{2*C(num[2],k)-C(num[3],k)}\cdot\cdot\cdot p1∗C(num[1],k)−C(num[2],k)∗p2∗C(num[2],k)−C(num[3],k)⋅⋅⋅

Simplified

p C ( n u m [ 1 ] , k ) + C ( n u m [ 2 ] , k ) + C ( n u m [ 3 ] , k ) + ⋅ ⋅ ⋅ ) p^{C(num[1],k)+C(num[2],k)+C(num[3],k)+\cdot\cdot\cdot)} pC(num[1],k)+C(num[2],k)+C(num[3],k)+⋅⋅⋅)

The combinatorial number is a very fast-growing number, so it is obviously necessary to reduce the power by Euler's power reduction

This question is very frequent and has poor comments

Pit point: fast multiplication will timeout, need to use__ int128 save time

code:

#include<cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1e7+5;

int n,k;
long long  p;
long long  a[40005];
long long  c[40005][35];
long long  num[80005];
long long  Prime[maxn],cnt;
bool Isprime[maxn];

void getPrime(){
for(int i=2;i<=10000000;i++) Isprime[i]=1;
for(int i=2;i<=10000000;i++){
if(Isprime[i]) Prime[++cnt]=i;
for(int j=1;j<=cnt&&i*Prime[j]<=10000000;j++){
Isprime[i*Prime[j]]=0;
if(i%Prime[j]==0) break;
}
}
}

long long  Euler(long long  N){  //Finding the value of Euler function
long long  ret=N;
for(int i=1;i<cnt&&Prime[i]*Prime[i]<=N;i++)
if(N%Prime[i]==0){
ret=ret/Prime[i]*(Prime[i]-1);
while(N%Prime[i]==0) N/=Prime[i];
}
if(N>1)   ret=ret/N*(N-1);
return ret;
}

long long  qpow(long long base,long long  power,long long  mod){
__int128 ans=1;
while(power){
if(power&1) ans=ans*base%mod;
base=(__int128)base*base%mod;
power=power>>1;
}
return ans;
}
int main(){
getPrime();
int T;
scanf("%d",&T);
while(T--){
long long  mx=0;
scanf("%d%d%lld",&n,&k,&p);
for(int i=1;i<=80000;i++) num[i]=0;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
num[a[i]]++;
mx=max(mx,a[i]);
}
long long mod=Euler(p);
c[0][0]=1;
for(int i=1;i<=n;i++){
c[i][0]=1;
for(int j=1;j<=min(i,k);j++){
c[i][j]=c[i-1][j-1]+c[i-1][j];
if(c[i][j]>=mod){
c[i][j]=c[i][j]%mod+mod;
}
}
}
long long  ans=1;
for(int i=1;Prime[i]<=mx;i++){
for(long long  j=Prime[i];j<=mx;j*=Prime[i]){
long long  temp=0;
for(long long  k=j;k<=mx;k+=j) temp+=num[k];
if(temp<k) break;
ans=(__int128)ans*qpow(Prime[i],c[temp][k],p)%p;
}
}
printf("%lld\n",ans);
}
return 0;
}



Added by MartinAW on Sat, 15 Jan 2022 06:13:53 +0200