QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#584162#8947. 白兔迷宫Xun_xiaoyao12 4ms4228kbC++171.7kb2024-09-23 09:36:492024-09-23 09:36:49

Judging History

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

  • [2024-09-23 09:36:49]
  • 评测
  • 测评结果：12
  • 用时：4ms
  • 内存：4228kb
查看
  • [2024-09-23 09:36:49]
  • 提交

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 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];
int a[210][210];
int f[210];
void calc(int 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 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));
	}
	ed[S].push_back(make_pair(0,0));
	for(int i=1,tk,tk_;i<=n;i++)
	{
		tk=inv[ed[i].size()];
		tk_=(tk+tk)%Mod;
		a[i][i]=1,a[n+i][n+i]=1;;
		for(pr v:ed[i]) if(v.second==1)
		{
			del(a[i][v.first],tk),add(a[i][n+n+1],tk);
			del(a[n+i][v.first],tk_),del(a[n+i][n+v.first],tk),add(a[n+i][n+n+1],tk);
		}
	}

	calc(n+n);

	printf("%d %lld\n",f[T],(f[n+T]+Mod-1ll*f[T]*f[T]%Mod)%Mod);
	return 0;
}
源文件, 语言: C++17

详细

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 0ms
memory: 3972kb

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: 4ms
memory: 4028kb

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: 2ms
memory: 4052kb

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: 2ms
memory: 4228kb

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: 3ms
memory: 4000kb

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: 4ms
memory: 4020kb

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: 4ms
memory: 4092kb

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: 3ms
memory: 4032kb

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: 0
Wrong Answer
time: 4ms
memory: 4056kb

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:

299162215 331088993

result:

points 0.0

Subtask #3:

score: 8
Accepted

Test #19:

score: 8
Accepted
time: 4ms
memory: 4104kb

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: 2ms
memory: 3892kb

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: 4ms
memory: 3892kb

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: 3ms
memory: 3896kb

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: 3ms
memory: 3960kb

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: 8
Accepted
time: 4ms
memory: 3956kb

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:

2 0

result:

points 1.0

Test #25:

score: 8
Accepted
time: 4ms
memory: 4056kb

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: 3ms
memory: 3988kb

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:

943403107 28972234

result:

points 0.0

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

服务器时间: 2025-01-21 06:00:47 | 开源项目