模拟赛
T1
非常简单的构造，但是我忘了判断 $m=2$ 和对只有一个点特判的输出错误，导致挂成 $20$。
具体思路，考虑欧拉路径只能有两个奇点，但是每条边上中间的都是奇点，所以我们需要删掉边缘的一些边，直到剩下两个奇点，然后对于 $n,m$ 都是偶数，或者一个偶数一个奇数，或者两个都是奇数来分别构造。
代码：
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define P pair<int,int>
#define mp make_pair
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define fi first
#define se second
#define N number
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x){
x=0;int f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f*=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int n,m,x0,Y0,x1,Y1,all;
bool op;
inline void Print(){
if(op) printf("%d %d\n",x0,Y0);
else printf("%d %d\n",Y0,x0);
}
inline bool Check(){
if(x0==x1&&Y0==Y1) return 1;return 0;
}
namespace Subtask1{
inline void Solve(){
if(n==2&&m==2) printf("4\n");
else printf("%d\n",all-(n+m-5));
op=1;
if(n>m)op=0,swap(n,m);
x0=n-1;Y0=1;Print();
while(x0){
Y0--;Print();x0--;Print();Y0++;Print();if(!x0) break; x0--;Print();
}
assert(x0==0&&Y0==1);
for(int i=1;i<=n-1;i++){
if(i&1) x1=i,Y1=m-1;
else x1=i,Y1=1;
if(i&1){
while(!Check()){
x0++;Print();if(Check()) break;
Y0++;Print();if(Check()) break;
x0--;Print();if(Check()) break;
Y0++;Print();if(Check()) break;
}
}
else{
while(!Check()){
Y0--;Print();if(Check()) break;
x0++;Print();if(Check()) break;
Y0--;Print();if(Check()) break;
x0--;Print();if(Check()) break;
}
}
}
if(n!=2||m!=2) Y0--,Print();
}
}
namespace Subtask2{
inline void Solve(){
printf("%d\n",all-(n+m-5));
if(n&1) swap(n,m),op=0;
else op=1;
x0=n-1;Y0=1;Print();Y0--;Print();
for(int i=n-2;i>=0;i--){
if(i&1) x1=i,Y1=0;
else x1=i,Y1=m-1;
// printf("x1=%d Y1=%d\n",x1,Y1);
if(i&1){
while(!Check()){
Y0--;Print();if(Check()) break;
x0--;Print();if(Check()) break;
Y0--;Print();if(Check()) break;
x0++;Print();if(Check()) break;
}
}
else{
while(!Check()){
x0--;Print();if(Check()) break;
Y0++;Print();if(Check()) break;
x0++;Print();if(Check()) break;
Y0++;Print();if(Check()) break;
}
}
}
Y0--;Print();
}
}
namespace Subtask3{
inline void Solve(){
op=1;
printf("%d\n",all-(m+n-4));
x0=n-1;Y0=1;Print();
x1=0;Y1=1;
while(!Check()){
x0--;Print();if(Check()) break;
Y0--;Print();if(Check()) break;
x0--;Print();if(Check()) break;
Y0++;Print();if(Check()) break;
}
for(int i=1;i<=n-1;i++){
if(i&1) x1=i,Y1=m-1;
else x1=i,Y1=1;
if(i&1){
while(!Check()){
x0++;Print();if(Check()) break;
Y0++;Print();if(Check()) break;
x0--;Print();if(Check()) break;
Y0++;Print();if(Check()) break;
}
}
else{
while(!Check()){
x0++;Print();if(Check()) break;
Y0--;Print();if(Check()) break;
x0--;Print();if(Check()) break;
Y0--;Print();if(Check()) break;
}
}
}
Y0--;Print();x0--;Print();
}
}
int main(){
// freopen("grid.in","r",stdin);
// freopen("grid.out","w",stdout);
read(n);read(m);all=m*(n-1)+n*(m-1);
if(n==1&&m==1){
puts("0\n0 0");return 0;
}
if(n==1||m==1){
printf("%d\n",max(n-1,m-1));
op=1;
if(m==1) swap(n,m),op=0;
x0=0;Y0=0;Print();rep(i,1,m-1) Y0=i,Print();return 0;
}
if(n%2==0&&m%2==0) Subtask1::Solve();
else if((n&1)^(m&1)==1) Subtask2::Solve();
else if((n&1)^(m&1)==0) Subtask3::Solve();
return 0;
}
T2
wym 的做法非常巧妙。首先信息是非常多的，我们考虑一个信息对应一个结果，我们直接枚举毒药位置，然后暴力枚举哪只老鼠是在哪一轮死的，我们只需要保证，毒药位置不同，老鼠的死亡轮数序列也不同，然后对于每一轮，我们按照这个序列去给老鼠喂药。
正确性：设 $x$ 是毒药，那么 $x$ 对应的老鼠死亡序列一定是符合的，而一个老鼠只能在一局内死亡，或者不死亡，而任意两个不同位置的毒药序列不同，所以其它毒药序列一定是不符合的。
#include<bits/stdc++.h>
#include "poison.h"
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 10010
#define M 21
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int lim,nn,nm,nk,nt,tot;
int a[M],b[N][M];
int di[M];
inline void dfs(int k,int num){
if(num>lim) return;
if(k==nm){
rep(i,0,nm-1) b[tot][i]=a[i];tot++;
return;
}
if(tot==nn) return;
rep(i,0,nt){
a[k]=i;dfs(k+1,num+(i!=0));
if(tot==nn) return;
}
}
int solve(int n,int m,int k,int t){
nn=n;nm=m;nk=k;nt=t;lim=m-k;
dfs(0,0);
// rep(i,0,n-1){
// rep(j,0,m-1) printf("%d ",b[i][j]);puts("");
// }
rep(i,1,t){
rep(j,0,n-1)rep(o,0,m-1)if(b[j][o]==i&&!di[o]){
feed(j,o);
}
int ans=done();
rep(j,0,m-1){
if(di[j]) continue;
if(!((ans>>j)&1)){
di[j]=i;
}
}
}
// rep(i,0,m-1) printf("di[%d]=%d\n",i,di[i]);
rep(i,0,n-1){
bool op=1;
rep(j,0,m-1) if(di[j]!=b[i][j]) op=0;
if(op){
// printf("MyAns=%d\n",i);
return i;
}
}
assert(0);
}
T3
推式子题，除掉 $p$ 的倍数的情况，我们根据费马小定理，原问题等价为有多少个 $a,b,c,d$ 满足 $a^b\equiv c^d$，其中 $1\le a,b,c,d\le p-1$，指数显然是这个取值范围，而底数不取 $0$ 是因为我们去掉整除的情况。指数难以处理，利用原根，我们可以得到 $ab\equiv cd \bmod p-1$，设 $f(m)$ 表示为 有多少 $a,b,c,d$ 满足 $ab\equiv cd\mod m$，同时利用中国剩余定理的唯一性，我们也可以证明 $f(x)$ 是积性的。所以我们现在需要考虑如何求出 $f(p^e)$ 即可。设 $c(t)$ 表示有多少个 $a,b$ 满足 $ab\equiv t \bmod m$，所以我们可以得到 $f(pe)=\sum\limits_{i=0} c^2(t)$。设 $a=Ap\alpha,b=Bp\beta,t=Tp^\theta$，由 $ab\equiv t$ 我们可以得到 $\alpha+\beta=\theta,AB=T \bmod p^{e-\theta}$，前者答案是 $\theta +1$，后者当 $A,B,T$ 都取在 $[1,p^{e-theta})$ 时解得数量为 $\phi2(p)$，但是 $A$ 的取值范围应该是 $[1,p^{e-\alpha})$，所以还需要乘上 $p^{\theta-\alpha}$，$B$ 同理。把这些都乘起来，待会和式，化简，可以得到一个非常简单的式子：
$$
f(pe)=p(p^e(p+1)-1)
$$
分解质因数即可。
代码：
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N number
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=998244353;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int t;
ll p;
inline int ksm(int a,int b,int mod){
int res=1;while(b){if(b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
inline int Calc(int p,int e){
// printf("p=%d e=%d\n",p,e);
return 1ll*ksm(p,2*e-1,mod)*((1ll*ksm(p,e,mod)*(p+1)%mod-1+mod)%mod)%mod;
}
inline int Solve(ll x){
ll i=2;int ans=1;
for(;i*i<=x;i++){
if(x%i) continue;
int cnt=0;while(x%i==0) cnt++,x/=i;
ans=1ll*ans*Calc(i,cnt)%mod;
}
if(x!=1) ans=1ll*ans*Calc(x%mod,1)%mod;
return ans;
}
// ll Solve(ll n)
// {
// ll ans=1;
// for(ll i=2;i*i<=n;i++)
// {
// int num=0;
// while(n%i==0)
// {
// num++;
// n/=i;
// }
// if(num)ans=ans*Calc(i,num)%mod;
// }
// if(n!=1)ans=ans*Calc(n%mod,1)%mod;
// return ans;
// }
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(t);
while(t--){
read(p);p--;
int ans=Solve(p);
p%=mod;ans=(ans+1ll*p*p%mod)%mod;
printf("%lld\n",ans);
}
return 0;
}