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
double r; //radius
}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;
}