QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#282361 | #3242. 骰子旅行 | kilo_tobo_tarjen# | WA | 82ms | 8504kb | C++20 | 1.7kb | 2023-12-11 21:04:25 | 2023-12-11 21:04:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
int inv[110];
void add(int &x,int y){
if((x+=y)>=mod)x-=mod;
}
void del(int &x,int y){
if((x-=y)<0)x+=mod;
}
void init(){
inv[0]=1;
inv[1]=1;
for(int i=2;i<110;i++){
inv[i]=(long long)(mod-mod/i)*inv[mod%i]%mod;
}
}
int p[110][110][110],g[110][110];
int siz[110];
vector<int> ve[110];
int yes[110][110];
signed main()
{
init();
ios::sync_with_stdio(false);
cin.tie(0);
int n,s0,T;
cin>>n>>s0>>T;
for(int i=1;i<=n;i++){
cin>>siz[i];
for(int j=0;j<siz[i];j++){
int x;cin>>x;
yes[i][x]=1;
p[i][x][1]=1ll*inv[siz[i]]*x%mod;
ve[i].push_back(x);
// assert(x!=i);
}
}
for(int i=1;i<T;i++){
for(int x=1;x<=n;x++){
for(int y=1;y<=n;y++)if(x!=y){
for(auto &to:ve[y])add(p[x][to][i+1],1ll*p[x][y][i]*inv[siz[y]]%mod);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int t=1;t<=T;t++)add(p[i][j][t],p[i][j][t-1]);
}
}
g[s0][0]=1;
int ans=0;
for(int i=0;i<T;i++){
for(int x=1;x<=n;x++){
// if(g[x][i])cout<<"g["<<x<<"]["<<i<<"]="<<g[x][i]<<"\n";
for(auto &to:ve[x]){
if(x==to){
add(ans,1ll*g[x][to]*inv[siz[x]]%mod);
}
add(g[to][i+1],1ll*g[x][i]*inv[siz[x]]%mod);
}
for(int y=1;y<=n;y++)if(yes[y][x]){
add(ans,1ll*g[x][i]*p[x][y][T-i-1]%mod*inv[siz[y]]%mod);
}
}
}
cout<<ans;
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 82ms
memory: 8504kb
input:
100 30 100 51 8 80 45 28 2 36 19 49 74 41 24 65 3 87 7 88 10 77 91 55 92 59 69 98 84 73 83 31 40 35 23 94 62 71 46 86 12 82 5 81 33 29 9 89 22 38 44 70 14 11 60 48 15 13 48 12 23 28 42 18 27 21 43 57 96 34 2 58 73 52 70 31 76 24 82 64 39 100 75 49 56 79 14 97 92 6 33 22 3 47 8 1 32 78 4 90 45 59 44 ...
output:
875692161
result:
wrong answer 1st lines differ - expected: '882477706', found: '875692161'