QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#283613#3242. 骰子旅行ioritWA 52ms6356kbC++143.2kb2023-12-14 22:10:022023-12-14 22:10:03

Judging History

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

  • [2023-12-14 22:10:03]
  • 评测
  • 测评结果:WA
  • 用时:52ms
  • 内存:6356kb
  • [2023-12-14 22:10:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace IO {
	#if ONLINE_JUDGE
	#define getc() (IS == IT && (IT = (IS = ibuf) + fread(ibuf, 1, IL, stdin), IS == IT) ? EOF : *IS++)
	#else
	#define getc() getchar()
	#endif
	const int IL = 1 << 21, OL = 1 << 21;
	int olen = 0;
	char ibuf[IL], *IS = ibuf, *IT = ibuf, obuf[OL];
	inline int read() {
		register char ch = getc(); register int x = 0, f = 1;
		while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
		while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
		return x * f;
	}
	inline double readdb() {
		register char ch = getc(); register double x = 0, f = 1;
		while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
		while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
		if(ch == '.') {
			register double b = 0.1;
			ch = getc();
			while(isdigit(ch)) x += (ch - 48) * b, b *= 0.1, ch = getc();
		}
		return x * f;
	}
	inline int readstr(char *s) {
		register char ch = getc(); register int len = 0;
		while(!isalpha(ch)) ch = getc();
		while(isalpha(ch)) s[++len] = ch, ch = getc();
		return len;
	}
	inline void flush() { fwrite(obuf, 1, olen, stdout); olen = 0; }
	inline void putc(register char ch) { obuf[olen++] = ch; }
	template<class T>
	inline void write(register T x) {
		if(x < 0) obuf[olen++] = '-', x = -x;
		if(x > 9) write(x / 10);
		obuf[olen++] = x % 10 + 48;
	}
} using namespace IO;
const int N = 2e2 + 10, mod = 998244353;
int n, s0, t;
int st[N][N], m[N], l[N][N], inv[N], f[N][N], ans;
//st[i][j] j 步走到 i 概率
//f[x][i][j] x 出发 j 步走到 i 且不经过 x 概率 
int qpow(int a, int k) {
	int res = 1;
	while(k) {
		if(k & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
		k >>= 1;
	}
	return res;
}
signed main() {
	n = read(), s0 = read(), t = read();
	inv[1] = 1;
	for(int i = 2; i <= 100; i++)
		inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
	st[0][s0] = 1;
	for(int i = 1; i <= n; i++) {
		m[i] = read();
		for(int j = 1; j <= m[i]; j++)
			l[i][j] = read();
	}
	for(int i = 0; i < t; i++)
		for(int j = 1; j <= n; j++)
			for(int k = 1; k <= m[j]; k++)
				st[i + 1][l[j][k]] = (st[i + 1][l[j][k]] + 1ll * inv[m[j]] * st[i][j]) % mod;
//	for(int i = 1; i <= t; i++) {
//		int s = 0;
////		for(int j = 1; j <= n; j++)
////		cout << i << " " << j << " " << st[i][j] << endl;
//		for(int j = 1; j <= n; j++) s = (s + st[i][j]) % mod;
//		s = qpow(s, mod - 2);
//		for(int j = 1; j <= n; j++) st[i][j] = 1ll * st[i][j] * s % mod;
////		cout << i << " " << j << " " << st[i][j] << endl;
//	}
	for(int i=  1; i <= n; i++)
		for(int j = 0; j <= t; j++)
			cout << i << " " << j << " " << st[j][i] << endl;
	for(int i = 1; i <= n; i++) {
		memset(f, 0, sizeof(f));
		for(int j = 1; j <= m[i]; j++)
			f[1][l[i][j]] = 1ll * inv[m[i]] * l[i][j] % mod;
		for(int j = 1; j < t; j++)
			for(int k = 1; k <= n; k++) {
				if(k == i) continue;
				for(int s = 1; s <= m[k]; s++)
					f[j + 1][l[k][s]] = (f[j + 1][l[k][s]] + 1ll * inv[m[k]] * f[j][k]) % mod;
			}
//		cout << f[1][s0] << endl;
//		for(int j = 1; j )
		
		for(int j = 0; j <= t; j++)
			for(int k = 1; j + k <= t; k++)
				ans = (ans + 1ll * st[j][i] * f[k][i]) % mod;
	}
	printf("%d\n", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 52ms
memory: 6356kb

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'