QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#584230#8947. 白兔迷宫Xun_xiaoyao8 14ms4424kbC++171.9kb2024-09-23 10:36:312024-09-23 10:36:32

Judging History

你现在查看的是最新测评结果

  • [2024-09-23 10:36:32]
  • 评测
  • 测评结果:8
  • 用时:14ms
  • 内存:4424kb
  • [2024-09-23 10:36:31]
  • 提交

answer

#include <bits/stdc++.h>
#define Mod 998244353
using namespace std;
int Qread()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x;
}
inline void add(int &a,int b){a+=b;if(a>=Mod) a-=Mod;}
inline void del(int &a,int b){a-=b;if(a<0) a+=Mod;}
inline int chk(int a){return a>=Mod?a-Mod:a;}
inline int qpow(int a,int p)
{
	int ret=1;
	for(;p;p>>=1,a=1ll*a*a%Mod)
		if(p&1) ret=1ll*ret*a%Mod;
	return ret;
}
typedef pair<int,int> pr;
int n,m,S,T;
vector<pr> ed[110];
int x,y,o;
int inv[110],d[110];
int a[310][310];
int f[310];
void calc(int n)
{
	// for(int i=1;i<=n;i++)
	// {
	// 	for(int j=1;j<=n+1;j++)
	// 		printf("%d ",a[i][j]);
	// 	printf("\n");
	// }

	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n&&!a[i][i];j++)
			if(a[j][i]) for(int k=i;k<=n+1;k++)
				swap(a[i][k],a[j][k]);
		int ny=qpow(a[i][i],Mod-2);
		for(int j=i+1,tk;j<=n;j++)
		{
			tk=1ll*a[j][i]*ny%Mod;
			for(int k=n+1;k>=i;k--)
				del(a[j][k],1ll*a[i][k]*tk%Mod);
		}
	}

	for(int i=n;i;i--)
	{
		f[i]=a[i][n+1];
		for(int j=i+1;j<=n;j++)
			del(f[i],1ll*f[j]*a[i][j]%Mod);
		f[i]=1ll*f[i]*qpow(a[i][i],Mod-2)%Mod;
	}
}
int n2,n3;
int main()
{
	inv[1]=1;
	for(int i=2;i<=100;i++)
		inv[i]=1ll*inv[Mod%i]*(Mod-Mod/i)%Mod;

	n=Qread(),m=Qread(),S=Qread(),T=Qread();
	for(int i=1;i<=m;i++)
	{
		x=Qread(),y=Qread(),o=Qread();
		if(x!=T) ed[y].push_back(make_pair(x,o)),d[x]++;
	}
	
	n2=n+n,n3=n+n+n;

	for(int i=1,tk,tk_;i<=n;i++)
	{
		a[i][i]=a[n+i][n+i]=a[n2+i][n2+i]=1;
		if(i==S) a[i][n3+1]=1;
		#define u v.first
		for(pr v:ed[i]) if(v.second==1)
		{
			tk=inv[d[u]];tk_=chk(tk+tk);
			//p
			del(a[i][u],tk);
			//f
			del(a[n+i][u],tk),del(a[n+i][n+u],tk);
			//g
			del(a[n2+i][u],tk),del(a[n2+i][n+u],tk_),del(a[n2+i][n2+u],tk);
		}
		#undef u
	}

	calc(n3);

	printf("%d %d\n",f[n+T],chk(f[n2+T]+Mod-1ll*f[n+T]*f[n+T]%Mod));
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 11ms
memory: 4280kb

input:

91 90 83 8
51 8 0
74 51 0
64 74 0
12 64 0
90 12 0
80 90 0
14 80 0
53 14 0
26 53 0
88 26 0
35 88 0
28 35 0
15 28 0
37 15 0
54 37 0
72 54 0
22 72 0
43 22 0
20 43 0
24 20 0
73 24 0
65 73 0
87 65 0
17 87 0
82 17 0
58 82 0
61 58 0
25 61 0
46 25 0
79 46 0
23 79 0
40 23 0
4 40 0
75 4 0
19 75 0
50 19 0
16 5...

output:

0 0

result:

points 1.0

Test #2:

score: 4
Accepted
time: 11ms
memory: 4252kb

input:

90 7059 73 53
54 53 0
6 54 0
75 54 0
36 54 0
4 36 0
26 36 0
76 54 0
69 6 0
10 76 0
52 53 0
62 76 0
37 62 0
78 53 0
22 62 0
2 4 0
27 78 0
3 52 0
39 76 0
85 39 0
71 22 0
8 69 0
42 62 0
64 54 0
79 62 0
67 52 0
7 4 0
47 78 0
18 54 0
31 62 0
33 54 0
13 8 0
1 78 0
46 2 0
14 22 0
84 2 0
30 6 0
20 62 0
16 6...

output:

0 0

result:

points 1.0

Test #3:

score: 4
Accepted
time: 14ms
memory: 4160kb

input:

99 4727 84 99
33 99 0
5 33 0
65 99 0
51 33 0
4 33 0
89 65 0
62 89 0
68 33 0
84 4 0
59 4 0
35 59 0
53 35 0
15 68 0
10 62 0
27 15 0
80 5 0
50 65 0
63 99 0
49 89 0
57 80 0
1 50 0
56 10 0
8 89 0
31 68 0
85 80 0
39 50 0
72 15 0
55 4 0
76 57 0
96 76 0
66 62 0
13 63 0
3 76 0
11 4 0
20 80 0
79 11 0
61 63 0
...

output:

0 0

result:

points 1.0

Test #4:

score: 4
Accepted
time: 14ms
memory: 4424kb

input:

98 9604 19 72
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 0
1 8 0
1 9 0
1 10 0
1 11 0
1 12 0
1 13 0
1 14 0
1 15 0
1 16 0
1 17 0
1 18 0
1 19 0
1 20 0
1 21 0
1 22 0
1 23 0
1 24 0
1 25 0
1 26 0
1 27 0
1 28 0
1 29 0
1 30 0
1 31 0
1 32 0
1 33 0
1 34 0
1 35 0
1 36 0
1 37 0
1 38 0
1 39 0
1 40 0
1 41 0
1 42 0
1...

output:

0 0

result:

points 1.0

Test #5:

score: 4
Accepted
time: 9ms
memory: 4292kb

input:

83 6889 26 34
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 0
1 8 0
1 9 0
1 10 0
1 11 0
1 12 0
1 13 0
1 14 0
1 15 0
1 16 0
1 17 0
1 18 0
1 19 0
1 20 0
1 21 0
1 22 0
1 23 0
1 24 0
1 25 0
1 26 0
1 27 0
1 28 0
1 29 0
1 30 0
1 31 0
1 32 0
1 33 0
1 34 0
1 35 0
1 36 0
1 37 0
1 38 0
1 39 0
1 40 0
1 41 0
1 42 0
1...

output:

0 0

result:

points 1.0

Test #6:

score: 4
Accepted
time: 14ms
memory: 4208kb

input:

97 3283 84 80
53 80 0
42 53 0
36 42 0
41 36 0
17 41 0
48 17 0
25 48 0
19 25 0
73 19 0
72 73 0
30 72 0
22 30 0
33 22 0
64 33 0
90 64 0
66 90 0
69 66 0
68 69 0
7 68 0
83 7 0
40 83 0
39 40 0
26 39 0
70 26 0
44 70 0
61 44 0
81 61 0
47 81 0
92 47 0
65 92 0
11 65 0
29 11 0
54 29 0
16 54 0
85 16 0
31 85 0
...

output:

0 0

result:

points 1.0

Test #7:

score: 4
Accepted
time: 7ms
memory: 4248kb

input:

88 7044 78 88
70 88 0
51 88 0
63 88 0
18 70 0
28 51 0
47 70 0
53 47 0
66 18 0
10 51 0
48 66 0
73 47 0
87 73 0
49 63 0
16 28 0
76 51 0
17 73 0
81 70 0
12 28 0
43 73 0
8 70 0
31 88 0
69 53 0
20 81 0
30 12 0
65 70 0
80 31 0
59 81 0
29 31 0
78 76 0
6 80 0
25 63 0
40 49 0
26 70 0
2 17 0
50 48 0
56 17 0
5...

output:

0 0

result:

points 1.0

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 24
Accepted
time: 10ms
memory: 4200kb

input:

86 85 23 70
43 70 1
33 43 1
86 33 1
54 86 1
1 54 1
68 1 1
18 68 1
39 18 1
62 39 1
85 62 1
47 85 1
67 47 1
44 67 1
74 44 1
13 74 1
38 13 1
81 38 1
60 81 1
28 60 1
84 28 1
48 84 1
49 48 1
73 49 1
22 73 1
37 22 1
20 37 1
65 20 1
59 65 1
3 59 1
36 3 1
52 36 1
83 52 1
56 83 1
55 56 1
2 55 1
10 2 1
66 10 ...

output:

85 0

result:

points 1.0

Test #9:

score: 24
Accepted
time: 9ms
memory: 4304kb

input:

92 5377 22 42
53 42 1
9 53 1
81 42 1
89 42 1
65 53 1
34 89 1
35 34 1
21 35 1
23 9 1
19 53 1
46 19 1
59 21 1
58 46 1
33 89 1
27 23 1
7 35 1
15 81 1
31 81 1
79 59 1
63 81 1
83 59 1
4 35 1
75 59 1
84 9 1
20 59 1
48 53 1
60 35 1
77 35 1
64 53 1
5 83 1
28 58 1
90 65 1
39 31 1
70 65 1
74 21 1
8 27 1
36 46...

output:

791755969 815749922

result:

points 1.0

Test #10:

score: 24
Accepted
time: 7ms
memory: 4072kb

input:

89 3236 53 39
6 39 1
63 39 1
33 6 1
54 39 1
89 39 1
78 89 1
52 33 1
75 52 1
15 63 1
42 33 1
49 75 1
5 89 1
55 52 1
17 5 1
70 49 1
16 89 1
85 39 1
14 85 1
66 89 1
68 75 1
20 63 1
76 63 1
81 85 1
27 70 1
2 89 1
40 42 1
60 2 1
57 16 1
46 54 1
59 81 1
11 17 1
8 17 1
82 2 1
71 52 1
3 5 1
44 3 1
80 14 1
7...

output:

241617573 420398516

result:

points 1.0

Test #11:

score: 24
Accepted
time: 10ms
memory: 4180kb

input:

98 4882 40 87
85 87 1
53 85 1
73 87 1
93 53 1
74 53 1
9 73 1
50 73 1
65 9 1
38 9 1
67 87 1
37 9 1
64 74 1
47 67 1
26 85 1
68 9 1
31 87 1
13 37 1
44 73 1
10 93 1
91 87 1
76 13 1
41 93 1
55 87 1
24 87 1
88 68 1
25 38 1
34 93 1
2 64 1
29 93 1
69 37 1
98 31 1
20 69 1
39 13 1
72 55 1
83 37 1
77 64 1
90 8...

output:

616152076 345121795

result:

points 1.0

Test #12:

score: 24
Accepted
time: 11ms
memory: 4168kb

input:

89 2544 67 60
9 60 1
69 9 1
74 9 1
61 69 1
72 61 1
13 9 1
45 13 1
14 61 1
31 9 1
16 60 1
84 60 1
80 69 1
83 45 1
40 69 1
25 9 1
47 61 1
5 74 1
8 31 1
10 40 1
23 5 1
70 10 1
51 69 1
35 60 1
81 13 1
34 61 1
36 14 1
38 31 1
58 83 1
49 45 1
75 38 1
15 38 1
21 84 1
65 70 1
66 31 1
20 10 1
54 81 1
53 81 1...

output:

797093300 685991745

result:

points 1.0

Test #13:

score: 24
Accepted
time: 7ms
memory: 4240kb

input:

89 7921 1 17
1 1 1
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
1 24 1
1 25 1
1 26 1
1 27 1
1 28 1
1 29 1
1 30 1
1 31 1
1 32 1
1 33 1
1 34 1
1 35 1
1 36 1
1 37 1
1 38 1
1 39 1
1 40 1
1 41 1
1 42 1
1 ...

output:

89 7832

result:

points 1.0

Test #14:

score: 24
Accepted
time: 11ms
memory: 4264kb

input:

90 8100 5 15
1 1 1
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
1 24 1
1 25 1
1 26 1
1 27 1
1 28 1
1 29 1
1 30 1
1 31 1
1 32 1
1 33 1
1 34 1
1 35 1
1 36 1
1 37 1
1 38 1
1 39 1
1 40 1
1 41 1
1 42 1
1 ...

output:

90 8010

result:

points 1.0

Test #15:

score: 24
Accepted
time: 11ms
memory: 4204kb

input:

91 4288 63 78
65 78 1
74 78 1
56 74 1
16 74 1
91 65 1
30 56 1
3 65 1
40 91 1
29 65 1
48 40 1
88 91 1
57 29 1
19 40 1
21 78 1
28 56 1
13 30 1
75 65 1
11 30 1
84 74 1
7 3 1
12 13 1
85 16 1
86 85 1
67 12 1
20 57 1
17 67 1
69 20 1
24 28 1
47 17 1
27 11 1
15 69 1
41 74 1
87 16 1
89 13 1
53 28 1
76 91 1
8...

output:

114706894 181339953

result:

points 1.0

Test #16:

score: 24
Accepted
time: 10ms
memory: 4180kb

input:

86 3062 25 41
36 41 1
22 36 1
73 22 1
72 73 1
26 72 1
42 26 1
54 42 1
6 54 1
78 6 1
82 78 1
49 82 1
17 49 1
30 17 1
51 30 1
23 51 1
37 23 1
18 37 1
55 18 1
63 55 1
27 63 1
12 27 1
34 12 1
20 34 1
8 20 1
44 8 1
38 44 1
71 38 1
2 71 1
74 2 1
4 74 1
45 4 1
79 45 1
3 79 1
35 3 1
62 35 1
67 62 1
32 67 1
...

output:

422980980 514482462

result:

points 1.0

Test #17:

score: 24
Accepted
time: 9ms
memory: 4176kb

input:

83 2712 11 64
31 64 1
30 31 1
36 64 1
80 36 1
81 31 1
33 64 1
24 30 1
74 81 1
67 24 1
38 74 1
58 81 1
41 38 1
66 36 1
63 38 1
19 67 1
72 66 1
28 72 1
43 58 1
47 66 1
14 47 1
12 28 1
55 12 1
62 30 1
21 30 1
52 12 1
11 41 1
32 24 1
37 30 1
18 11 1
5 38 1
44 43 1
20 11 1
53 66 1
40 20 1
56 64 1
4 74 1
...

output:

817061307 357141578

result:

points 1.0

Test #18:

score: 0
Wrong Answer
time: 9ms
memory: 4120kb

input:

84 4693 16 71
1 71 1
51 1 1
34 51 1
49 34 1
27 49 1
21 27 1
39 21 1
78 39 1
20 78 1
9 20 1
40 9 1
73 40 1
84 73 1
68 84 1
3 68 1
2 3 1
12 2 1
53 12 1
15 53 1
38 15 1
7 38 1
29 7 1
13 29 1
45 13 1
31 45 1
41 31 1
54 41 1
69 54 1
36 69 1
4 36 1
25 4 1
57 25 1
83 57 1
46 83 1
52 46 1
61 52 1
55 61 1
5 ...

output:

0 0

result:

points 0.0

Subtask #3:

score: 4
Acceptable Answer

Test #19:

score: 8
Accepted
time: 7ms
memory: 4144kb

input:

90 89 77 72
38 72 1
9 38 1
20 9 1
39 20 1
61 39 1
55 61 1
46 55 1
28 46 1
56 28 1
74 56 1
35 74 1
64 35 1
27 64 1
69 27 1
79 69 1
88 79 1
31 88 1
48 31 1
57 48 1
7 57 1
85 7 1
6 85 1
63 6 1
32 63 1
34 32 1
4 34 1
67 4 1
50 67 1
11 50 1
13 11 1
71 13 1
2 71 1
45 2 1
26 45 1
43 26 1
73 43 1
44 73 1
33...

output:

89 0

result:

points 1.0

Test #20:

score: 8
Accepted
time: 11ms
memory: 4288kb

input:

91 90 68 73
10 73 0
26 10 0
65 26 0
36 65 1
41 36 0
47 41 0
5 47 0
76 5 0
51 76 1
53 51 0
13 53 0
57 13 0
62 57 1
42 62 0
46 42 0
14 46 0
27 14 0
75 27 1
84 75 0
72 84 1
11 72 0
43 11 1
71 43 0
82 71 1
59 82 0
12 59 1
90 12 1
78 90 1
30 78 0
70 30 0
19 70 0
74 19 0
54 74 1
58 54 1
40 58 1
61 40 0
32...

output:

0 0

result:

points 1.0

Test #21:

score: 8
Accepted
time: 13ms
memory: 4240kb

input:

96 95 81 68
60 68 1
27 60 1
13 27 1
50 13 1
69 50 1
59 69 1
26 59 1
51 26 1
38 51 1
32 38 1
54 32 1
37 54 1
7 37 1
96 7 1
22 96 1
71 22 1
65 71 1
73 65 1
21 73 1
46 21 1
4 46 1
94 4 1
83 94 1
3 83 1
1 3 1
79 1 1
93 79 1
16 93 1
34 16 1
12 34 1
49 12 1
47 49 1
2 47 1
61 2 1
36 61 1
17 36 1
24 17 1
28...

output:

95 0

result:

points 1.0

Test #22:

score: 8
Accepted
time: 8ms
memory: 4040kb

input:

80 79 62 75
74 75 1
70 74 1
36 70 1
25 36 1
12 25 1
17 12 1
44 17 1
35 44 1
65 35 1
23 65 1
66 23 1
15 66 1
3 15 1
78 3 1
53 78 1
18 53 1
24 18 1
57 24 1
48 57 1
19 48 1
16 19 1
60 16 1
2 60 1
52 2 1
67 52 1
37 67 1
54 37 1
31 54 1
77 31 1
20 77 1
76 20 1
29 76 1
28 29 1
13 28 1
14 13 1
71 14 1
11 7...

output:

79 0

result:

points 1.0

Test #23:

score: 8
Accepted
time: 10ms
memory: 4208kb

input:

88 87 73 22
75 22 0
66 75 0
5 66 0
68 5 0
28 68 0
48 28 0
8 48 1
36 8 0
54 36 0
78 54 0
41 78 0
16 41 0
24 16 0
45 24 0
51 45 0
67 51 0
7 67 0
10 7 0
58 10 0
69 58 0
30 69 0
39 30 0
55 39 0
61 55 0
27 61 0
43 27 0
25 43 0
20 25 0
65 20 0
63 65 0
77 63 0
52 77 0
42 52 0
50 42 0
19 50 0
21 19 0
53 21 ...

output:

0 0

result:

points 1.0

Test #24:

score: 4
Acceptable Answer
time: 7ms
memory: 4148kb

input:

90 89 64 49
68 49 1
43 68 1
88 43 0
76 88 1
20 76 0
74 20 1
5 74 1
6 5 1
86 6 0
56 86 1
63 56 1
50 63 1
58 50 0
66 58 0
23 66 1
13 23 0
67 13 1
48 67 0
52 48 1
4 52 1
12 4 1
59 12 1
10 59 1
45 10 1
30 45 0
17 30 1
77 17 1
80 77 1
62 80 1
21 62 0
22 21 1
8 22 1
87 8 0
53 87 1
47 53 0
35 47 1
2 35 0
8...

output:

0 0

result:

points 0.5

Test #25:

score: 8
Accepted
time: 13ms
memory: 4148kb

input:

97 96 85 56
88 56 1
90 88 1
94 90 1
86 94 1
92 86 1
95 92 1
4 95 1
7 4 1
74 7 1
63 74 1
65 63 1
60 65 1
61 60 1
36 61 1
58 36 1
26 58 1
91 26 1
83 91 1
71 83 1
53 71 1
78 53 1
59 78 1
89 59 1
24 89 1
29 24 1
5 29 1
49 5 1
42 49 1
96 42 1
11 96 1
15 11 1
8 15 1
19 8 1
72 19 1
20 72 1
87 20 1
33 87 1
...

output:

96 0

result:

points 1.0

Subtask #4:

score: 0
Wrong Answer

Test #26:

score: 0
Wrong Answer
time: 8ms
memory: 4204kb

input:

81 6493 65 20
79 20 0
15 79 0
2 20 0
12 15 0
48 15 0
77 2 0
73 15 0
74 2 0
68 79 0
54 73 0
66 54 0
69 74 0
36 12 0
25 77 0
24 48 0
53 68 0
43 15 0
58 12 0
50 73 0
16 24 0
27 68 0
65 69 0
38 24 0
11 15 1
51 68 0
32 77 0
30 50 0
3 25 0
72 12 0
8 79 0
64 24 0
17 54 0
70 66 0
31 68 0
60 17 0
21 16 0
63 ...

output:

0 0

result:

points 0.0

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%