QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#879913 | #8947. 白兔迷宫 | liulianll | 0 | 0ms | 0kb | C++14 | 2.1kb | 2025-02-02 17:53:00 | 2025-02-02 17:53:01 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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%