QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#228077#7634. Cardsucup-team1209#AC ✓3959ms34528kbC++203.0kb2023-10-28 11:33:502023-10-28 11:33:50

Judging History

你现在查看的是测评时间为 2023-10-28 11:33:50 的历史记录

  • [2023-10-28 19:27:19]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:4086ms
  • 内存:34268kb
  • [2023-10-28 11:33:50]
  • 评测
  • 测评结果:100
  • 用时:3959ms
  • 内存:34528kb
  • [2023-10-28 11:33:50]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin, std::cout;
using u64 = unsigned long long;
using u128 = __int128_t;
const int mod = 998244353;

const int N = 1 << 20;
int rev[N], wn[N], lim, invlim;
int pow(int a, int b, int ans = 1) {
	for(;b;b >>= 1, a = (u64) a * a % mod) if(b & 1)
		ans = (u64) ans * a % mod;
	return ans;
}
void init(int len) {
	lim = 2 << std::__lg(len - 1);
	invlim = mod - (mod - 1) / lim;
	for(static int i = 1;i < lim;i += i) {
		wn[i] = 1;
		const int w = pow(3, mod / i / 2);
		for(int j = 1;j < i;++j) {
			wn[i + j] = (u64) wn[i + j - 1] * w % mod;
		}
	}
	for(int i = 1;i < lim;++i) {
		rev[i] = rev[i >> 1] >> 1 | (i % 2u * lim / 2);
	}
}
void DFT(u64 * a) {
	static u64 t[N];
	for(int i = 0;i < lim;++i) {
		t[i] = a[rev[i]];
	}
	for(int i = 1;i < lim;i += i) {
		for(int j = 0;j < lim;j += i + i) {
			for(int k = 0;k < i;++k) {
				const u64 x = t[i + j + k] * wn[i + k] % mod;
				t[i + j + k] = t[k + j] + mod - x;
				t[k + j] += x;
			}
		}
	}
	for(int i = 0;i < lim;++i) {
		a[i] = t[i] % mod;
	}
}
void IDFT(u64 * a) {
	DFT(a), std::reverse(a + 1, a + lim);
	for(int i = 0;i < lim;++i) {
		a[i] = (u64) a[i] * invlim % mod;
	}
}


int n, m;
int x[5];

u64 h[N];
u64 f[N], g[N];
u64 tmp[N];
const int B = 1000;

int main() {
#ifdef zqj
//	freopen("$.in", "r", stdin);
#endif
	cin >> n >> m;
	int sum = 0;
	for(int i = 0;i < 5;++i) cin >> x[i], sum += x[i];
	sum = pow(sum, mod - 2);
	for(int i = 0;i < 5;++i) {
		x[i] = (u64) x[i] * sum % mod;
		h[i] = x[i];
	}
	f[0] = 1;
	init((m + B) * 4);
	DFT(h);
	for(int i = 0;i < lim;++i) {
		h[i] = pow(h[i], B);
	}
	for(int i = 1;i <= m % B;++i) {
		for(int j = 0;j <= m * 4;++j) {
			g[j + 0] += f[j] * x[0];
			g[j + 1] += f[j] * x[1];
			g[j + 2] += f[j] * x[2];
			g[j + 3] += f[j] * x[3];
			g[j + 4] += f[j] * x[4];
		}
		// x => x + n - 2 * i
		const int kill = 2 * i - n;
		for(int j = 0;j <= m * 4;++j) {
			f[j] = g[j] % mod;
			g[j] = 0;
		}
		for(int i = 0;i < kill;++i) {
			f[i] = 0;
		}
	}
	for(int i = m % B + 1;i <= m;i += B) {
		const int prekill = std::max(2 * (i - 1) - n, 0);
		const int kill = std::max(2 * (i + B - 1) - n, 0);
		for(int j = kill;j <= m * 4;++j) {
			tmp[j] = f[j];
			f[j] = 0;
		}
		DFT(tmp);
		for(int j = 0;j < lim;++j) {
			tmp[j] = (u64) tmp[j] * h[j] % mod;
		}
		IDFT(tmp);
		for(int k = 0;k < B;++k) {
			const int R = kill + k * 4 + 4;
			for(int j = prekill;j < R;++j) {
				g[j + 0] += f[j] * x[0];
				g[j + 1] += f[j] * x[1];
				g[j + 2] += f[j] * x[2];
				g[j + 3] += f[j] * x[3];
				g[j + 4] += f[j] * x[4];
			}
			for(int j = prekill;j < R;++j) {
				f[j] = g[j] % mod;
				g[j] = 0;
			}
			for(int j = prekill;j < std::max(2 * (i + k) - n, 0);++j) {
				f[j] = 0;
			}
		}
		for(int j = kill;j <= m * 4;++j) {
			f[j] = (f[j] + tmp[j]) % mod;
		}
		memset(tmp, 0, lim << 2);
		memset(f, 0, kill << 2);
	}
	u64 ans = 0;
	for(int j = 0;j <= m * 4;++j) {
		ans += f[j];
	}
	cout << ans % mod << '\n';
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 11876kb

input:

1 1
1 1 1 1 1

output:

399297742

result:

ok 1 number(s): "399297742"

Test #2:

score: 0
Accepted
time: 3059ms
memory: 32128kb

input:

100000 100000
1234 4567 7890 4321 54321

output:

348074135

result:

ok 1 number(s): "348074135"

Test #3:

score: 0
Accepted
time: 3048ms
memory: 32124kb

input:

100000 100000
1 2 3 4 5

output:

639188342

result:

ok 1 number(s): "639188342"

Test #4:

score: 0
Accepted
time: 3059ms
memory: 32220kb

input:

100000 100000
5 4 3 2 1

output:

211669278

result:

ok 1 number(s): "211669278"

Test #5:

score: 0
Accepted
time: 2ms
memory: 11908kb

input:

0 0
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 966ms
memory: 20064kb

input:

1 50000
1 1 1 1 1

output:

548880636

result:

ok 1 number(s): "548880636"

Test #7:

score: 0
Accepted
time: 2ms
memory: 11908kb

input:

50000 1
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 3056ms
memory: 32280kb

input:

100000 100000
234 666 7655 12234 0

output:

45268602

result:

ok 1 number(s): "45268602"

Test #9:

score: 0
Accepted
time: 3958ms
memory: 34436kb

input:

99999 99999
12345 54332 12345 65432 34444

output:

360543661

result:

ok 1 number(s): "360543661"

Test #10:

score: 0
Accepted
time: 3957ms
memory: 34524kb

input:

99998 99998
1 1 1 1 1

output:

602326230

result:

ok 1 number(s): "602326230"

Test #11:

score: 0
Accepted
time: 3940ms
memory: 32540kb

input:

99998 99997
1 1 1 1 1

output:

159752985

result:

ok 1 number(s): "159752985"

Test #12:

score: 0
Accepted
time: 3054ms
memory: 32212kb

input:

99997 100000
1 2 3 4 5

output:

139603712

result:

ok 1 number(s): "139603712"

Test #13:

score: 0
Accepted
time: 3959ms
memory: 34528kb

input:

100000 99997
1 2 2 1 3232323

output:

363030953

result:

ok 1 number(s): "363030953"

Test #14:

score: 0
Accepted
time: 0ms
memory: 11888kb

input:

0 0
0 0 1 0 0

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 87ms
memory: 21024kb

input:

10000 10000
91095828 93770094 5303328 491263 50290308

output:

135900098

result:

ok 1 number(s): "135900098"

Test #16:

score: 0
Accepted
time: 167ms
memory: 12896kb

input:

9226 9995
62366139 253808 1929312 491263 4375669

output:

812662634

result:

ok 1 number(s): "812662634"

Test #17:

score: 0
Accepted
time: 66ms
memory: 14880kb

input:

18641 10000
1061 4359 1330 13764 16043

output:

112339046

result:

ok 1 number(s): "112339046"

Extra Test:

score: 0
Extra Test Passed