Submission #36429862
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=3010,LIM=3000,mod=998244353;
ll mypow(ll a,ll n){
if(!n)return 1;
ll tmp=mypow(a,n/2);tmp=tmp*tmp%mod;
if(n&1)tmp=tmp*a%mod;return tmp;
}
ll myinv(ll a){return mypow(a,mod-2);}
void add(ll& x,ll y){x=(x+y)%mod;}
ll inv[MAXN];
ll n,m,k;
vector<int>e[MAXN];
int deg[MAXN];
ll c[MAXN];
ll dp[MAXN][MAXN][3];
int main(){
rep(i,1,LIM)inv[i]=myinv(i);
cin>>n>>m>>k;
rep(i,1,m){
int u,v;cin>>u>>v;
e[u].push_back(v);e[v].push_back(u);
deg[u]++;deg[v]++;
}
rep(i,1,n)cin>>c[i];
dp[0][1][0]=1;
rep(i,0,k-1)rep(u,1,n){
for(auto v:e[u]){
ll p=inv[deg[u]];
if(c[v]){
rep(j,0,2)add(dp[i+1][v][j],p*dp[i][u][j]%mod);
}else{
add(dp[i+1][v][2],p*dp[i][u][2]%mod);
add(dp[i+1][v][2],p*dp[i][u][1]%mod);
add(dp[i+1][v][2],p*dp[i][u][0]%mod);
add(dp[i+1][v][1],p*dp[i][u][1]%mod);
add(dp[i+1][v][1],2*p*dp[i][u][0]%mod);
add(dp[i+1][v][0],p*dp[i][u][0]%mod);
}
}
}
ll ans=0;
rep(i,1,k)rep(j,1,n)if(c[j])add(ans,dp[i][j][2]);
cout<<ans;
return 0;
}
Submission Info
Submission Time
2022-11-12 21:39:47+0900
Task
G - Random Walk to Millionaire
User
Crying
Language
C++ (GCC 9.2.1)
Score
600
Code Size
1656 Byte
Status
AC
Exec Time
536 ms
Memory
215444 KiB
Compile Error
./Main.cpp: In function ‘ll mypow(ll, ll)’:
./Main.cpp:19:5: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
19 | if(n&1)tmp=tmp*a%mod;return tmp;
| ^~
./Main.cpp:19:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
19 | if(n&1)tmp=tmp*a%mod;return tmp;
| ^~~~~~
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
600 / 600
Status
Set Name
Test Cases
Sample
example0.txt, example1.txt
All
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, example0.txt, example1.txt
Case Name
Status
Exec Time
Memory
000.txt
AC 17 ms
15628 KiB
001.txt
AC 15 ms
15680 KiB
002.txt
AC 17 ms
15644 KiB
003.txt
AC 19 ms
15784 KiB
004.txt
AC 9 ms
3820 KiB
005.txt
AC 7 ms
3604 KiB
006.txt
AC 449 ms
215432 KiB
007.txt
AC 445 ms
215280 KiB
008.txt
AC 431 ms
215160 KiB
009.txt
AC 431 ms
215236 KiB
010.txt
AC 353 ms
215292 KiB
011.txt
AC 352 ms
215320 KiB
012.txt
AC 354 ms
215392 KiB
013.txt
AC 445 ms
215320 KiB
014.txt
AC 445 ms
215444 KiB
015.txt
AC 246 ms
21108 KiB
016.txt
AC 248 ms
20952 KiB
017.txt
AC 536 ms
215304 KiB
018.txt
AC 536 ms
215248 KiB
019.txt
AC 47 ms
11328 KiB
020.txt
AC 97 ms
16712 KiB
021.txt
AC 272 ms
109492 KiB
022.txt
AC 331 ms
109752 KiB
023.txt
AC 364 ms
137836 KiB
024.txt
AC 77 ms
31640 KiB
025.txt
AC 253 ms
100900 KiB
026.txt
AC 536 ms
215412 KiB
027.txt
AC 394 ms
118004 KiB
028.txt
AC 313 ms
142844 KiB
029.txt
AC 434 ms
145096 KiB
030.txt
AC 339 ms
77048 KiB
031.txt
AC 343 ms
82676 KiB
032.txt
AC 327 ms
71028 KiB
example0.txt
AC 4 ms
3652 KiB
example1.txt
AC 3 ms
3716 KiB