QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#231157#7634. Cardsucup-team484#AC ✓8372ms9448kbC++173.9kb2023-10-29 02:48:312023-10-29 02:48:31

Judging History

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

  • [2023-10-29 02:48:31]
  • 评测
  • 测评结果:AC
  • 用时:8372ms
  • 内存:9448kb
  • [2023-10-29 02:48:31]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e6 + 5;
const int BLOCK = 900;

int pw(int x, int y) {
	int r = 1;
	for (; y; y /= 2, x = x * 1ll * x % mod)
		if (y & 1)
			r = r * 1ll * x % mod;
	return r;
}

const int root = 565042129; // 3^(119 * 2^3)
const int root_pw = 1 << 20; // order of root
const int root_1 = pw(root, mod - 2);

void fft(vector<int> & a, bool invert) {
  int n = a.size();
  for(int i = 1, j = 0; i < n; i++) {
    int bit = n >> 1;
    for (j ^= bit; !(j&bit); j ^= (bit>>=1));
    if (i < j)
      swap(a[i], a[j]);
  }
  for(int len = 2; len <= n; len <<= 1) {
    int wlen = invert ? root_1 : root;
    for(int i = len; i < root_pw; i <<= 1)
      wlen = 1LL * wlen * wlen % mod;
    for(int i = 0; i < n; i += len) {
      for(int j=i, w=1; j < i + len/2; j++) {
        int u=a[j], v=1LL*a[j+len/2]*w % mod;
        a[j] = u+v < mod ? u+v : u+v-mod;
        a[j+len/2] = u-v < 0 ? u-v+mod : u-v;
        w = 1LL * w * wlen % mod;
      }
    }
  }
  if(invert) {
    int n_1 = pw(n, mod - 2);
    for(int & x : a)
      x = 1LL * x * n_1 % mod;
  }
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, m, s = 0; cin >> n >> m;
	if (m == 0) {
		cout << "1\n";
		return 0;
	}
	int mm = 1;
	while (mm <= 4 * m)
		mm *= 2;
	vector<int> a(5);
	for (int i = 0; i < 5; i++) {
		cin >> a[i];
		s += a[i];
	}
	s = pw(s, mod - 2);
	for (int i = 0; i < 5; i++)
		a[i] = a[i] * 1ll * s % mod;

	int lo = max(0, 2 * m - n);
//	vector<int> dp(4 * m + 1);
//	dp[2 * m] = 1;
//	for (int i = 0; i < m; i++) {
//		vector<int> ndp(4 * m + 1);
//		for (int j = lo; j <= 4 * m; j++) {
//			for (int k = -2; k <= 2; k++)
//				if (lo <= k + j && k + j <= 4 * m)
//					ndp[k + j] = (ndp[k + j] + dp[j] * 1ll * a[k + 2]) % mod;
//		}
//		swap(dp, ndp);
//	}
//	for (int i = 0; i <= 4 * m; i++) {
//		cout << dp[i] << " ";
//	}
//	cout << endl;
//	int ans = 0;
//	for (int i = max(0, 2 * m - n); i <= 4 * m; i++) {
//		ans += dp[i];
//		if (ans >= mod)
//			ans -= mod;
//	}
//	cout << ans << "\n";

	vector<int> cur(mm), arr(mm);
	cur[2 * m] = 1;
	for (int i = 0; i < 5; i++)
		arr[i] = a[i];
	fft(arr, 0);
	for (int i = 0; i < mm; i++)
		arr[i] = pw(arr[i], BLOCK);
//	fft(arr, 1);
	for (int i = 0; i < m;) {
		if (i + BLOCK >= m) {
			vector<int> nx(mm);
			for (int j = lo; j <= 4 * m; j++) {
				for (int k = -2; k <= 2; k++)
					if (lo <= k + j && k + j <= 4 * m)
						nx[k + j] = (nx[k + j] + cur[j] * 1ll * a[k + 2]) % mod;
			}
			swap(cur, nx);
			i++;
			continue;
		}
		vector<int> small(4 * BLOCK), tail(mm);
		for (int j = lo; j <= 4 * m && j - lo < 2 * BLOCK; j++) {
			small[j - lo] = cur[j];
			cur[j] = 0;
		}
		for (int it = 0; it < BLOCK; it++) {
			vector<int> tmp(4 * BLOCK);
			for (int j = 0; j < 4 * BLOCK; j++) {
				for (int k = -2; k <= 2; k++)
					if (0 <= k + j && k + j < 4 * BLOCK)
						tmp[k + j] = (tmp[k + j] + small[j] * 1ll * a[k + 2]) % mod;
			}
			swap(small, tmp);
		}
		for (int j = 0; j + lo + 2 * BLOCK <= 4 * m; j++) {
			cur[j] = cur[j + lo + 2 * BLOCK];
			cur[j + lo + 2 * BLOCK] = 0;
		}
		fft(cur, 0);
		for (int j = 0; j < mm; j++)
			cur[j] = cur[j] * 1ll * arr[j] % mod;
		fft(cur, 1);
		for (int j = 4 * m; j >= lo; j--) {
			cur[j] = cur[j - lo];
			cur[j - lo] = 0;
		}
		for (int j = lo; j <= 4 * m && j - lo < 4 * BLOCK; j++) {
			cur[j] += small[j - lo];
			if (cur[j] >= mod)
				cur[j] -= mod;
		}
		i += BLOCK;
	}
//	for (int i = 0; i <= 4 * m; i++) {
////		cout << cur[i] << " ";
//		assert(cur[i] == dp[i]);
//	}
//	cout << endl;
	int ans = 0;
	for (int i = lo; i <= 4 * m; i++) {
		ans += cur[i];
		if (ans >= mod)
			ans -= mod;
	}
	cout << ans << "\n";
}

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

详细

Test #1:

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

input:

1 1
1 1 1 1 1

output:

399297742

result:

ok 1 number(s): "399297742"

Test #2:

score: 0
Accepted
time: 8357ms
memory: 9380kb

input:

100000 100000
1234 4567 7890 4321 54321

output:

348074135

result:

ok 1 number(s): "348074135"

Test #3:

score: 0
Accepted
time: 8329ms
memory: 9444kb

input:

100000 100000
1 2 3 4 5

output:

639188342

result:

ok 1 number(s): "639188342"

Test #4:

score: 0
Accepted
time: 8360ms
memory: 9368kb

input:

100000 100000
5 4 3 2 1

output:

211669278

result:

ok 1 number(s): "211669278"

Test #5:

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

input:

0 0
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 3106ms
memory: 6284kb

input:

1 50000
1 1 1 1 1

output:

548880636

result:

ok 1 number(s): "548880636"

Test #7:

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

input:

50000 1
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 8343ms
memory: 9448kb

input:

100000 100000
234 666 7655 12234 0

output:

45268602

result:

ok 1 number(s): "45268602"

Test #9:

score: 0
Accepted
time: 8343ms
memory: 9448kb

input:

99999 99999
12345 54332 12345 65432 34444

output:

360543661

result:

ok 1 number(s): "360543661"

Test #10:

score: 0
Accepted
time: 8349ms
memory: 9364kb

input:

99998 99998
1 1 1 1 1

output:

602326230

result:

ok 1 number(s): "602326230"

Test #11:

score: 0
Accepted
time: 8353ms
memory: 9448kb

input:

99998 99997
1 1 1 1 1

output:

159752985

result:

ok 1 number(s): "159752985"

Test #12:

score: 0
Accepted
time: 8372ms
memory: 9368kb

input:

99997 100000
1 2 3 4 5

output:

139603712

result:

ok 1 number(s): "139603712"

Test #13:

score: 0
Accepted
time: 8326ms
memory: 9368kb

input:

100000 99997
1 2 2 1 3232323

output:

363030953

result:

ok 1 number(s): "363030953"

Test #14:

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

input:

0 0
0 0 1 0 0

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 305ms
memory: 3840kb

input:

10000 10000
91095828 93770094 5303328 491263 50290308

output:

135900098

result:

ok 1 number(s): "135900098"

Test #16:

score: 0
Accepted
time: 302ms
memory: 3840kb

input:

9226 9995
62366139 253808 1929312 491263 4375669

output:

812662634

result:

ok 1 number(s): "812662634"

Test #17:

score: 0
Accepted
time: 318ms
memory: 3828kb

input:

18641 10000
1061 4359 1330 13764 16043

output:

112339046

result:

ok 1 number(s): "112339046"

Extra Test:

score: 0
Extra Test Passed