QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#879913#8947. 白兔迷宫liulianll0 0ms0kbC++142.1kb2025-02-02 17:53:002025-02-02 17:53:01

Judging History

This is the latest submission verdict.

  • [2025-02-02 17:53:01]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
  • [2025-02-02 17:53:00]
  • Submitted

answer

#include<bits/stdc++.h>
#define mod 998244353
#define inv(x) (fastpow(x,mod-2))
using namespace std;
int n,m,s,t,u,v,o,cnt;
struct Line{
	int u,v,o;
}line[10010];
long long f[110],g[110],h[110],a[110][110],x[110],deg[110],d[110];
long long fastpow(long long x,long long y){
	long long ans=1;
	while(y){
		if(y&1) ans=(ans*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return ans;
}
void solve(int p,int q,int n,int m){
	if(p>n||q>n){
		for(int i=1;i<=n;i++){
			x[i]=a[i][n+1]*inv(a[i][i]);
		}
		return;
	}
	int k=0;
	for(int i=p;i<=n;i++){
		if(a[i][q]){
			k=i;break;
		}
	}
	for(int i=1;i<=m;i++){
		swap(a[p][i],a[k][i]);
	}
	for(int i=1;i<=n;i++){
		long long v=a[i][q]*inv(a[p][q]);
		if(a[i][q]!=0&&i!=p){
			for(int j=m;j>=q;j--){
				a[i][j]=((a[i][j]-(a[p][j]*v))%mod+mod)%mod;
			}
		}
	}
	solve(p+1,q+1,n,m);
	return;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&o);
		if(u==t) continue;
		line[++cnt].o=o;
		line[cnt].u=u;
		line[cnt].v=v;
		++deg[u];
	}
	m=cnt;
	a[s][3*n+1]=1;
	for(int i=1;i<=n;++i){
		d[i]=inv(deg[i]);
	}
	for(int i=1;i<=3*n;++i) ++a[i][i];
	for(int i=1;i<=m;++i){
		u=line[i].u,v=line[i].v;
		a[v][u]=(a[v][u]-d[u])%mod;
		if(a[v][u]<0) a[v][u]+=mod;
		if(line[i].o==0) continue;
		
		a[n+v][u]=(a[n+v][u]-d[u])%mod;
		if(a[n+v][u]<0) a[n+v][u]+=mod;
		a[n+v][n+u]=(a[n+v][n+u]-d[u])%mod;
		if(a[n+v][n+u]<0) a[n+v][n+u]+=mod;
		
		a[(n<<1)+v][u]=(a[(n<<1)+v][u]-d[u])%mod;
		if(a[(n<<1)+v][u]<0) a[(n<<1)+v][u]+=mod;
		a[(n<<1)+v][n+u]=(a[(n<<1)+v][n+u]-(d[u]<<1))%mod;
		if(a[(n<<1)+v][n+u]<0) a[(n<<1)+v][n+u]+=mod;
		a[(n<<1)+v][(n<<1)+u]=(a[(n<<1)+v][(n<<1)+u]-d[u])%mod;
		if(a[(n<<1)+v][(n<<1)+u]<0) a[(n<<1)+v][(n<<1)+u]+=mod;
	}
	solve(1,1,3*n,3*n+1);
	for(int i=1;i<=n;++i) f[i]=x[i];
	for(int i=n+1;i<=2*n;++i) g[i-n]=x[i];
	for(int i=2*n+1;i<=3*n;++i) h[i-2*n]=x[i];
	printf("%lld %lld",g[t],((h[t]-g[t]*g[t])%mod+mod)%mod);
//	for(int i=1;i<=n;++i) printf("%lld ",f[i]);printf("\n");
//	for(int i=1;i<=n;++i) printf("%lld ",g[i]);printf("\n");
//	for(int i=1;i<=n;++i) printf("%lld ",h[i]);printf("\n");
	
	return 0;
} 

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

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:


result:


Subtask #2:

score: 0
Runtime Error

Test #8:

score: 0
Runtime Error

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:


result:


Subtask #3:

score: 0
Runtime Error

Test #19:

score: 0
Runtime Error

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:


result:


Subtask #4:

score: 0
Runtime Error

Test #26:

score: 0
Runtime Error

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:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%