QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#283611#3242. 骰子旅行ioritWA 60ms3632kbC++141.3kb2023-12-14 21:55:242023-12-14 21:55:24

Judging History

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

  • [2023-12-14 21:55:24]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:3632kb
  • [2023-12-14 21:55:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 5;
const int mod = 998244353;
int n, ans, s0, T, inv[N], f[N][N], g[N][N];
vector <int> e[N];
int main() {
	cin >> n >> s0 >> T, inv[1] = 1;
	for(int i = 2; i < N; i++) inv[i] = mod - 1ll * mod / i * inv[mod % i] % mod;
	for(int i = 1; i <= n; i++) {
		int m, id; scanf("%d", &m);
		for(int j = 1; j <= m; j++) scanf("%d", &id), e[i].push_back(id);
	}
	for(int i = 1; i <= n; i++) {
		memset(f, 0, sizeof(f));
		for(int it : e[i]) f[1][it] = 1ll * it * inv[e[i].size()] % mod;
		for(int j = 0; j < T; j++) {
			for(int k = 1; k <= n; k++)
				if(f[j][k] && k != i) {
					int v = 1ll * f[j][k] * inv[e[k].size()] % mod;
					for(int it : e[k]) f[j + 1][it] = (f[j + 1][it] + v) % mod;
				}
			g[i][j + 1] = f[j + 1][i];
		}
	}
	memset(f, 0, sizeof(f)), f[0][s0] = 1;
	for(int i = 0; i < T; i++) {
		for(int j = 1; j <= n; j++)
			if(f[i][j]) {
				for(int k = 1; k + i <= T; k++)
					ans = (ans + 1ll * f[i][j] * g[j][k] % mod) % mod;
				int v = 1ll * f[i][j] * inv[e[j].size()] % mod;
				for(int it : e[j]) f[i + 1][it] = (f[i + 1][it] + v) % mod;
			}
	}
	for(int i=  1; i <= n; i++)
		for(int j = 0; j <= T; j++)
			cout << i << " " << j << " " << f[j][i] << endl;
	cout << ans << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 60ms
memory: 3632kb

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:

1 0 0
1 1 0
1 2 920475718
1 3 194714004
1 4 885524136
1 5 360644576
1 6 986446597
1 7 408365783
1 8 555177441
1 9 477354067
1 10 368570443
1 11 392252009
1 12 492392649
1 13 902450547
1 14 897431584
1 15 225897170
1 16 463136442
1 17 318027121
1 18 925440121
1 19 665386245
1 20 231854851
1 21 168332...

result:

wrong answer 1st lines differ - expected: '882477706', found: '1 0 0'