結果
| 問題 |
No.2164 Equal Balls
|
| コンテスト | |
| ユーザー |
 chro_96
|
| 提出日時 | 2022-12-15 12:38:58 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 5,983 bytes |
| コンパイル時間 | 612 ms |
| コンパイル使用メモリ | 35,848 KB |
| 実行使用メモリ | 663,584 KB |
| 最終ジャッジ日時 | 2024-11-14 03:09:30 |
| 合計ジャッジ時間 | 140,132 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 MLE * 2 |
| other | WA * 22 TLE * 17 MLE * 12 |
ソースコード
#include <stdio.h>
long long mod_num = 998244353LL;
long long org_root = 3LL;
int org_length = 998244352;
long long root[10] = {};
int length[10] = {};
long long inverse_root[10] = {};
long long inverse_l[10] = {};
int log_l[10] = {};
long long pow_root[10][16] = {};
long long pow_root_inv[10][16] = {};
long long power_mod (long long a, long long b, long long p) {
long long ans = 0LL;
a %= p;
if (b <= 0LL) {
return 1LL;
}
ans = power_mod(a, b/2LL, p);
ans = (ans * ans) % p;
if (b%2LL == 1LL) {
ans = (ans * a) % p;
}
return ans;
}
void setup_ntt (int l, int id) {
int tmp_length = 4;
log_l[id] = 1;
while(tmp_length < 2*l) {
tmp_length *= 4;
log_l[id]++;
}
root[id] = power_mod(org_root, org_length / tmp_length, mod_num);
inverse_root[id] = power_mod(root[id], mod_num-2LL, mod_num);
inverse_l[id] = power_mod((long long) tmp_length, mod_num-2LL, mod_num);
length[id] = tmp_length;
pow_root[id][log_l[id]-1] = root[id];
for (int i = log_l[id]-1; i > 0; i--) {
pow_root[id][i-1] = pow_root[id][i];
pow_root[id][i-1] *= pow_root[id][i];
pow_root[id][i-1] %= mod_num;
pow_root[id][i-1] *= pow_root[id][i-1];
pow_root[id][i-1] %= mod_num;
}
pow_root_inv[id][log_l[id]-1] = inverse_root[id];
for (int i = log_l[id]-1; i > 0; i--) {
pow_root_inv[id][i-1] = pow_root_inv[id][i];
pow_root_inv[id][i-1] *= pow_root_inv[id][i];
pow_root_inv[id][i-1] %= mod_num;
pow_root_inv[id][i-1] *= pow_root_inv[id][i-1];
pow_root_inv[id][i-1] %= mod_num;
}
return;
}
void ntt_4n (long long *a, long long *pow_root, int length, int log_l) {
long long root_1_4 = pow_root[0];
for (int i = 0; i < length; i++) {
int idx = 0;
int tmp = i;
for (int j = 0; j < log_l; j++) {
idx <<= 2;
idx |= (tmp&3);
tmp >>= 2;
}
if (i < idx) {
long long swap = a[i];
a[i] = a[idx];
a[idx] = swap;
}
}
for (int i = 0; i < log_l; i++) {
int step = (1<<(2*i));
int stepx4 = (step<<2);
int cnt = length/stepx4;
long long tmp_root = 1LL;
for (int j = 0; j < step; j++) {
long long w1 = tmp_root;
long long w2 = (w1*w1)%mod_num;
long long w3 = (w2*w1)%mod_num;
for (int k = 0; k < cnt; k++) {
int idx1 = ((k*stepx4)|j);
int idx2 = (idx1|step);
int idx3 = (idx1|(2*step));
int idx4 = (idx2|idx3);
long long a1 = a[idx1];
long long a2 = (a[idx2]*w1)%mod_num;
long long a3 = (a[idx3]*w2)%mod_num;
long long a4 = (a[idx4]*w3)%mod_num;
long long wa2 = (a2*root_1_4)%mod_num;
long long wa4 = (a4*root_1_4)%mod_num;
long long pad = (mod_num<<1LL);
a[idx1] = (a1+a2+a3+a4) % mod_num;
a[idx2] = (a1+wa2-a3-wa4+pad) % mod_num;
a[idx3] = (a1-a2+a3-a4+pad) % mod_num;
a[idx4] = (a1-wa2-a3+wa4+pad) % mod_num;
}
tmp_root = (tmp_root*pow_root[i])%mod_num;
}
}
return;
}
int main () {
int n = 0;
int m = 0;
int a[200000] = {};
int b[200000] = {};
int res = 0;
long long ans[4000000] = {};
long long mod_num = 998244353LL;
long long comb[301][301] = {};
long long cnt[301][301][301] = {};
long long prod[300][601] = {};
long long st[10][1048576] = {};
int stnum[10] = {};
int idx = 0;
int logm = 0;
res = scanf("%d", &n);
res = scanf("%d", &m);
for (int i = 0; i < n; i++) {
res = scanf("%d", a+i);
}
for (int i = 0; i < n; i++) {
res = scanf("%d", b+i);
}
for (int i = 0; i <= 300; i++) {
comb[i][0] = 1LL;
comb[i][i] = 1LL;
for (int j = 1; j < i; j++) {
comb[i][j] = (comb[i-1][j-1]+comb[i-1][j])%mod_num;
}
}
for (int i = 1; i <= 300; i++) {
for (int j = 0; j <= 300; j++) {
cnt[i][0][j] = comb[i][j];
}
for (int j = 1; j <= 300; j++) {
for (int k = 0; k < 300; k++) {
cnt[i][j][k] = (cnt[i][j-1][k]+cnt[i][j-1][k+1])%mod_num;
}
if (i >= 300) {
cnt[i][j][300] = 1LL;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j <= 600; j++) {
prod[i][j] = 1LL;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= 300; j++) {
prod[i%m][j+300] *= cnt[a[i]][b[i]][j];
prod[i%m][j+300] %= mod_num;
}
for (int j = 1; j <= 300; j++) {
prod[i%m][300-j] *= cnt[b[i]][a[i]][j];
prod[i%m][300-j] %= mod_num;
}
}
while ((1<<logm) < m) {
setup_ntt(600*(1<<logm)+1, logm);
logm++;
}
setup_ntt(600*m+1, logm);
for (int i = 0; i < m; i++) {
stnum[idx] = 0;
for (int j = 0; j <= 600; j++) {
st[idx][j] = prod[i][j];
}
while (idx > 0 && stnum[idx-1] == stnum[idx]) {
ntt_4n(st[idx-1], pow_root[stnum[idx]], length[stnum[idx]], log_l[stnum[idx]]);
ntt_4n(st[idx], pow_root[stnum[idx]], length[stnum[idx]], log_l[stnum[idx]]);
for (int j = 0; j < length[stnum[idx]]; j++) {
st[idx-1][j] *= st[idx][j];
st[idx-1][j] %= mod_num;
st[idx][j] = 0LL;
}
ntt_4n(st[idx-1], pow_root_inv[stnum[idx]], length[stnum[idx]], log_l[stnum[idx]]);
for (int j = 0; j <= length[stnum[idx]]; j++) {
st[idx-1][j] *= inverse_l[stnum[idx]];
st[idx-1][j] %= mod_num;
}
stnum[idx-1]++;
idx--;
}
idx++;
}
printf("%d\n", idx);
ans[0] = 1LL;
for (int i = 0; i < idx; i++) {
ntt_4n(ans, pow_root[logm], length[logm], log_l[logm]);
ntt_4n(st[i], pow_root[logm], length[logm], log_l[logm]);
for (int j = 0; j < length[logm]; j++) {
ans[j] *= st[i][j];
ans[j] %= mod_num;
}
ntt_4n(ans, pow_root_inv[logm], length[logm], log_l[logm]);
for (int j = 0; j <= 600*m; j++) {
ans[j] *= inverse_l[logm];
ans[j] %= mod_num;
}
for (int j = 600*m+1; j < length[logm]; j++) {
ans[j] = 0LL;
}
}
printf("%lld\n", ans[300*m]);
return 0;
}