模拟赛

T1

非常简单的构造，但是我忘了判断 $m=2$ 和对只有一个点特判的输出错误，导致挂成 $20$。

具体思路，考虑欧拉路径只能有两个奇点，但是每条边上中间的都是奇点，所以我们需要删掉边缘的一些边，直到剩下两个奇点，然后对于 $n,m$ 都是偶数，或者一个偶数一个奇数，或者两个都是奇数来分别构造。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#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$ 对应的老鼠死亡序列一定是符合的，而一个老鼠只能在一局内死亡，或者不死亡，而任意两个不同位置的毒药序列不同，所以其它毒药序列一定是不符合的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#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(p^e)=\sum\limits_{i=0}^{p^e-1} 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})$ 时解得数量为 $\phi^2(p^{e-\theta})$，但是 $A$ 的取值范围应该是 $[1,p^{e-\alpha})$，所以还需要乘上 $p^{\theta-\alpha}$，$B$ 同理。把这些都乘起来，待会和式，化简，可以得到一个非常简单的式子：

$$
f(p^e)=p^{2e-1}(p^e(p+1)-1)
$$

分解质因数即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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;
}