2023.08.10杭电多校第八场
solved:3
rank:
C.Congruences
题意：对于每组数据给定M个pi和qi，pi为两两不同的质数，N为所有pi的积，问是否存在最小的正整数x使得 x^pi在模N的意义下与qi同余，如果存在输出x,否则输出-1;
显然x^pi在模N的意义下与qi同余可以推出x^pi在模pi的意义下与qi同余，此外，由于pi为质数，故由费马小定理可得,x^pi在模pi的意义下与x同余，因此原问题可转化为给定M个pi和qi，问是否存在最小的正整数x使得x在模pi的意义下与qi同余 ，用中国剩余定理计算即可，注意要开int128；
又因x^pi^在模N的意义下与qi同余可以推出x^pi^在模pi的意义下与qi同余的逆命题不成立，故在算出来结果后还需对每一组pi和qi判断是否成立；
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 typedef __int128_t int128; 5 ll read(){ 6 char ch=getchar();ll x=0,f=1; 7 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 8 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 9 return x*f; 10 } 11 const int maxn=1000000+11; 12 ll T,M,N,x; 13 ll p[maxn],q[maxn]; 14 ll p2[maxn],q2[maxn],t[maxn]; 15 ll quickpow(int128 a,ll b,ll Mod){ 16 ll ret=1; 17 while(b){ 18 if(b&1)ret=(int128)ret*a%Mod; 19 a=(int128)a*a%Mod; 20 b>>=1; 21 } 22 return ret; 23 } 24 int main(){ 25 T=read(); 26 while(T--){ 27 M=read(); 28 N=1;x=0; 29 for(int i=1;i<=M;i++){ 30 p[i]=read();q[i]=read(); 31 N=N*p[i];q2[i]=q[i]%p[i]; 32 } 33 for(int i=1;i<=M;i++)p2[i]=N/p[i]; 34 for(int i=1;i<=M;i++){ 35 t[i]=quickpow(p2[i],p[i]-2,p[i]); 36 } 37 for(int i=1;i<=M;i++){ 38 x=(x+(((int128)q2[i]*p2[i])%N*t[i])%N)%N; 39 } 40 x=(x%N+N)%N; 41 if(x==0)x=N; 42 bool flag=true; 43 for(int i=1;i<=M;i++){ 44 if(quickpow((int128)x,p[i],N)!=q[i]){ 45 cout<<"-1"<<endl; 46 flag=false; 47 break; 48 } 49 } 50 if(flag){ 51 cout<<x<<endl; 52 } 53 } 54 return 0; 55 }
E.0 vs 1
题意：给定一串01串，0和1轮流从两端取，0只能取0，1只能取1，若取完为平局，否则0取到1 / 1取到0即输，两人都采取最优策略，问谁会获胜；
若两端字符不相同，两名玩家都只能直接选取，0输当且仅当串的两端都为1，且上一步中1已经取走了一个1，故必定存在一边有两个1，1输的情况同理（这题代码对着标程打的）；
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 char ch=getchar();int x=0,f=1; 5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 7 return x*f; 8 } 9 const int maxn=1e5+5; 10 int T,N,L,R,now; 11 string s; 12 int A[maxn]; 13 void firstcheck(){ 14 while(L<R&&A[L]+A[R]==1){ 15 if(A[L]==now)L++; 16 else R--; 17 now=1-now; 18 } 19 if(L==R&&A[L]==now)L++; 20 } 21 int checkleft(int now){ 22 for(int i=L;i<=R;i++){ 23 if(now!=A[i])return i; 24 now=1-now; 25 } 26 return -1; 27 } 28 int checkright(int now){ 29 for(int i=R;i>=L;i--){ 30 if(now!=A[i])return i; 31 now=1-now; 32 } 33 return -1; 34 } 35 int main(){ 36 T=read(); 37 while(T--){ 38 N=read(); 39 cin>>s; 40 for(int i=1;i<=N;i++)A[i]=s[i-1]-'0'; 41 L=1,R=N,now=0; 42 firstcheck(); 43 if(L>R){ 44 cout<<"-1"<<endl; 45 continue; 46 } 47 if(A[L]!=now){ 48 cout<<1-now<<endl; 49 continue; 50 } 51 int lpos=checkleft(now); 52 int rpos=checkright(now); 53 if((lpos!=-1&&A[lpos]==now)||(rpos!=-1&&A[rpos]==now)){ 54 cout<<now<<endl; 55 continue; 56 } 57 if(rpos+1==lpos||lpos==-1){ 58 cout<<"-1"<<endl; 59 continue; 60 } 61 cout<<A[lpos]<<endl; 62 } 63 return 0; 64 }
G.Solubility
题意：互溶关系具有传递性，给定一些互溶关系；询问一些液体，问是否互溶；
并查集维护即可；
1 #include<bits/stdc++.h> 2 using namespace std ; 3 inline int read(){ 4 int s=1,w=0; 5 char ch=getchar(); 6 while(ch<'0'||ch>'9'){if(ch=='-')s=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();} 8 return s*w; 9 } 10 int T,N,M,K; 11 int x,y; 12 int fa[100005]; 13 int getfa(int x){ 14 if(x==fa[x])return x; 15 return fa[x]=getfa(fa[x]); 16 } 17 void solve(){ 18 N=read();M=read(); 19 for(int i=1;i<=N;i++)fa[i]=i; 20 for(int i=1;i<=M;i++){ 21 x=read();y=read(); 22 fa[getfa(x)]=getfa(y); 23 } 24 K=read(); 25 bool flag=true; 26 x=read(); 27 int fx=getfa(x); 28 for(int i=2;i<=K;i++){ 29 y=read(); 30 if(fx!=getfa(y))flag=false; 31 } 32 if(flag)cout<<"YES"<<endl; 33 else cout<<"NO"<<endl; 34 } 35 int main() { 36 T=read(); 37 while(T--){ 38 solve(); 39 } 40 return 0 ; 41 }
H.Expectation of Rank
题意：给定方阵的行数和列数N，以及一个素数P，问方阵在模P意义下的秩的期望值；
一共有N*N个位置可以选数，每个位置有P种选择（0~P-1），且由于P是质数，我们对于确定的一个行向量，任取0~P-1中的一个数乘行向量得到的新的向量是两两不同的；我们定义dp[i][j]为当前选了i个向量，秩为j时的方案数，有转移方程dp[i][j] = ( p^N - p^(j-1) ) * dp[ i-1 ] [ j-1 ] + ( p^j ) * dp[ i-1 ] [ j ]；
因为与秩为j的向量组线性相关的向量共有p^j种（对于其极大线性无关组中的每一个向量前的系数可以在0~P-1中任取）；
最后用 当前秩方案数*秩之和 乘上 总方案数的乘法逆元即可；
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 int read(){ 5 char ch=getchar();int x=0,f=1; 6 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 8 return x*f; 9 } 10 const int Mod=1e9+7; 11 const int maxn=5e3+5; 12 int T,N,P; 13 ll dp[maxn][maxn]; 14 ll p[maxn]; 15 ll quickpow(ll a,ll b){ 16 ll ret=1; 17 while(b){ 18 if(b&1)ret=ret*a%Mod; 19 a=a*a%Mod; 20 b>>=1; 21 } 22 return ret; 23 } 24 ll solve(){ 25 N=read();P=read(); 26 p[0]=1; 27 for(int i=1;i<=N;i++){ 28 p[i]=p[i-1]*P%Mod; 29 } 30 dp[0][0]=1; 31 for(int i=1;i<=N;i++){ 32 dp[i][0]=1; 33 for(int j=1;j<=i;j++){ 34 dp[i][j]=(p[N]-p[j-1]+Mod)%Mod*dp[i-1][j-1]%Mod+p[j]*dp[i-1][j]%Mod; 35 dp[i][j]%=Mod; 36 } 37 } 38 ll ans=0; 39 for(int i=1;i<=N;i++){ 40 ans+=i*dp[N][i]%Mod; 41 ans%=Mod; 42 } 43 for(int i=1;i<=N;i++){ 44 for(int j=1;j<=i;j++){ 45 dp[i][j]=0; 46 } 47 p[i]=0; 48 } 49 return ans%Mod*quickpow(quickpow(P,N*N),Mod-2)%Mod; 50 } 51 int main(){ 52 T=read(); 53 while(T--){ 54 cout<<solve()<<endl; 55 } 56 return 0; 57 }
J.Rikka with Square Numbers
题意：给定两个数a，b，问经过最少多少次加减完全平方数的操作可以将a变成b
等价于询问经过多少次加减完全平方数的操作可以表示出abs（a - b），不妨令其等于d；
若d为完全平方数，显然只需一次操作；
此外，(x+1)^2-x^2=2x+1；故倘若d为奇数一定可以用两次操作表示出；
倘若d为偶数，设d可以表示成两个完全平方数的差，则有x^2-y^2=d，(x+y)*(x-y)=d；当x与y的奇偶性相同时，显然(x-y)与(x+y)都为偶数，故d是4的倍数时，可以两次操作表出；
枚举，判断d是否能用两个完全平方数的和表出，如果可以，也只需两次操作；
如果以上情况都不成立，我们可以通过一次操作先把其变成奇数，再通过两次操作表示，共计三次操作；
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 ll read(){ 5 char ch=getchar();ll x=0,f=1; 6 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 8 return x*f; 9 } 10 ll T,A,B; 11 bool pd(ll x){ 12 ll y=sqrt(x); 13 if(y*y==x)return true; 14 return false; 15 } 16 void solve(){ 17 A=read();B=read(); 18 ll d=max(A-B,B-A); 19 if(pd(d)){ 20 cout<<"1"<<endl; 21 return ; 22 } 23 if(d%2==1){ 24 cout<<"2"<<endl; 25 return ; 26 } 27 if(d%4==0){ 28 cout<<"2"<<endl; 29 return ; 30 } 31 for(int i=1;i*i*2<=d;i++){ 32 if(pd(d-i*i)){ 33 cout<<"2"<<endl; 34 return ; 35 } 36 } 37 cout<<"3"<<endl; 38 return ; 39 } 40 int main(){ 41 T=read(); 42 while(T--){ 43 solve(); 44 } 45 return 0; 46 }