QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #312172 | #6328. Many Products | memset0 | WA | 877ms | 13516kb | C++20 | 10.1kb | 2024-01-23 15:51:38 | 2024-01-23 15:51:38 |
Judging History
answer
#include <bits/stdc++.h>
#define logvec(v) \
cerr << #v << ": "; \
for (int i = 0; i < v.size(); i++) \
cerr << v[i] << " \n"[i + 1 == v.size()];
#define all(x) begin(x), end(x)
using namespace std;
const int N = 2e5 + 9, K = 35, V = 1e6 + 9, mod = 998244353;
int n, t, a[N], fac[N], ifac[N], inv[N], f[N][K], g[N][K], h[K][K], dp[K];
bool vis[V];
long long m;
vector<int> pri;
vector<long long> uni;
vector<pair<long long, int>> p;
void upd(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
int sub(int x, int y) {
x -= y;
return x < 0 ? x + mod : x;
}
int add(int x, int y) {
x += y;
return x >= mod ? x - mod : x;
}
int C(int n, int m) {
if (n < m) return 0;
return (long long)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int power(int a, int b) {
int s = 1;
for (; b; b >>= 1, a = (long long)a * a % mod)
if (b & 1) s = (long long)s * a % mod;
return s;
}
vector<int> rev, rt;
void getRevRoot(int n) {
int m = __lg(n); // log(n)/log(2)+1e-8;
rev.resize(n);
for (int i = 1; i < n; i++) {
rev[i] = rev[i >> 1] >> 1 | (i & 1) << (m - 1);
}
static int len = 1;
if (len < n) {
rt.resize(n);
for (; len < n; len <<= 1) {
int uni = power(3, (mod - 1) / (len << 1));
rt[len] = 1;
for (int i = 1; i < len; i++) {
rt[i + len] = (long long)rt[i + len - 1] * uni % mod;
}
}
}
}
void ntt(vector<int> &f, int n) {
f.resize(n);
for (int i = 0; i < n; i++) {
if (i < rev[i]) swap(f[i], f[rev[i]]);
}
for (int len = 1; len < n; len *= 2) {
for (int i = 0; i < n; i += len * 2) {
for (int j = 0; j < len; j++) {
int x = f[i + j];
int y = (long long)f[i + j + len] * rt[j + len] % mod;
f[i + j] = add(x, y);
f[i + j + len] = sub(x, y);
}
}
}
}
vector<int> operator*(vector<int> f, vector<int> g) {
int n = 1, m = (int)(f.size() + g.size()) - 1;
while (n < m)
n <<= 1;
int invn = power(n, mod - 2);
getRevRoot(n), ntt(f, n), ntt(g, n);
for (int i = 0; i < n; i++)
f[i] = (long long)f[i] * g[i] % mod;
reverse(f.begin() + 1, f.end()), ntt(f, n);
f.resize(m);
for (int i = 0; i < m; i++)
f[i] = (long long)f[i] * invn % mod;
return f;
}
vector<pair<long long, int>> factor(long long x) {
vector<pair<long long, int>> fac;
for (int p : pri)
if (p * p <= x) {
if (x % p == 0) {
fac.emplace_back(p, 0);
while (x % p == 0) {
x /= p;
fac.back().second++;
}
}
} else {
break;
}
if (x > 1) fac.emplace_back(x, 1);
return fac;
}
void dfs(int u, long long s) {
if (u == p.size()) {
uni.emplace_back(s);
return;
}
for (int i = 0; i <= p[u].second; i++) {
dfs(u + 1, s);
s *= p[u].first;
}
}
int find(long long x) {
if (x > m) return -1;
int k = lower_bound(all(uni), x) - uni.begin();
return x == uni[k] ? k : -1;
}
vector<int> solve(int l, int r) {
if (l == r) {
return {1, a[l]};
}
int mid = (l + r) >> 1;
vector<int> lv = solve(l, mid);
vector<int> rv = solve(mid + 1, r);
vector<int> v(min((size_t)K, lv.size() + rv.size() - 1));
for (int i = 0; i < lv.size(); i++)
for (int j = 0; j < rv.size() && i + j < v.size(); j++) {
v[i + j] = (v[i + j] + (long long)lv[i] * rv[j]) % mod;
}
return v;
}
int main() {
#ifdef popteam
// freopen("L.in", "r", stdin);
freopen("L2.in", "r", stdin);
#endif
inv[0] = inv[1] = fac[0] = ifac[0] = 1;
for (int i = 2; i < N; i++) {
inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
}
for (int i = 1; i < N; i++) {
fac[i] = (long long)fac[i - 1] * i % mod;
ifac[i] = (long long)ifac[i - 1] * inv[i] % mod;
}
for (int i = 2; i < V; i++) {
if (!vis[i]) pri.push_back(i);
for (int j = i; j < V; j += i)
vis[j] = true;
}
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (++a[i] == mod) a[i] = 0;
}
p = factor(m);
dfs(0, 1);
sort(all(uni));
// logvec(uni);
int zero = 0, all = 1;
for (int i = 1; i <= n; i++)
if (a[i] == 0) {
swap(a[++zero], a[i]);
} else {
all = (long long)all * a[i] % mod;
a[i] = power(a[i], mod - 2);
}
// cerr << "zero = " << zero << endl;
// cerr << "all = " << all << endl;
// for (int i = 1; i <= n; i++)
// cerr << a[i] << " \n"[i == n];
vector<int> p = zero < n ? solve(zero + 1, n) : vector<int>{};
for (int i = 0; i < K - zero; i++)
dp[i + zero] = i < p.size() ? p[i] : 0;
for (int i = 0; i < K; i++)
if (dp[i]) {
dp[i] = (long long)dp[i] * all % mod;
// fprintf(stderr, "dp[%d] = %d\n", i, dp[i]);
}
f[0][0] = g[0][0] = 1;
for (int i = 1; i < uni.size(); i++) {
int j = upper_bound(all(uni), m / uni[i]) - uni.begin() - 1;
for (; j >= 0; j--)
if (m % (uni[i] * uni[j]) == 0) {
long long t = m / uni[j];
for (int y = 1; y < K; y++) {
if (t % uni[i]) break;
t /= uni[i];
int k = find(m / t);
assert(k != -1);
// fprintf(stderr, ">> i=%d j=%d k=%d y=%d\n", i, j, k, y);
for (int x = y; x < K; x++) {
upd(f[k][x], (long long)f[j][x - y] * ifac[y] % mod);
upd(g[k][x], (long long)g[j][x - y] * power((uni[i] - 1) % mod, y) % mod * ifac[y] % mod);
}
}
}
}
for (int i = 0; i < uni.size(); i++)
for (int j = 0; j < K; j++)
if (f[i][j] || g[i][j]) {
f[i][j] = (long long)f[i][j] * fac[j] % mod;
g[i][j] = (long long)g[i][j] * fac[j] % mod;
// fprintf(stderr, "i=%d j=%d >> f=%d g=%d\n", i, j, f[i][j], g[i][j]);
}
for (int x = 0; x < K; x++)
for (int y = 0; x + y < K; y++) {
for (int i = 0; i < uni.size(); i++) {
int j = find(m / uni[i]);
assert(j != -1);
if (f[i][x] && g[j][y]) {
upd(h[x][y], (long long)f[i][x] * g[j][y] % mod);
// fprintf(stderr, "f[%d][%d](%d) * g[%d][%d](%d) -> %d\n", i, x, f[i][x], j, y, g[j][y], h[x][y]);
}
}
}
int ans = 0;
for (int x = 0; x < K; x++)
for (int y = 0; x + y < K && x + y <= n; y++)
if (h[x][y] && dp[y]) {
// fprintf(stderr, "x=%d y=%d h=%d C=%d dp=%d\n", x, y, h[x][y], C(n - y, x), dp[y]);
upd(ans, (long long)h[x][y] * C(n - y, x) % mod * dp[y] % mod);
}
cout << ans << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 15ms
memory: 12952kb
input:
2 3 0 1
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: 0
Accepted
time: 15ms
memory: 12756kb
input:
5 1 0 1 2 3 4
output:
120
result:
ok 1 number(s): "120"
Test #3:
score: 0
Accepted
time: 11ms
memory: 10856kb
input:
10 314159265358 0 1 2 3 4 5 6 7 8 9
output:
658270849
result:
ok 1 number(s): "658270849"
Test #4:
score: 0
Accepted
time: 67ms
memory: 11084kb
input:
200000 999999999989 823489320 406308599 710963770 183707427 192930969 941365774 318564299 391028855 945374838 651744270 515755727 220857626 599403217 214957584 335628890 771694833 40989299 34892948 630275822 869708185 432704750 924850167 707864789 232688853 406616372 529994171 782650336 979286144 65...
output:
777405593
result:
ok 1 number(s): "777405593"
Test #5:
score: 0
Accepted
time: 71ms
memory: 13516kb
input:
199999 999999999331 969252353 737776924 108584656 914893031 394348303 484491127 481944452 120707790 396027156 912223841 673218447 285837840 782450963 144940963 892852383 782342131 655814479 1324532 794011279 219428289 470995270 489684781 347978895 102371386 546635675 585575402 940741300 644383693 67...
output:
573300948
result:
ok 1 number(s): "573300948"
Test #6:
score: 0
Accepted
time: 109ms
memory: 10728kb
input:
200000 742073813481 681694404 632869785 595996398 549654767 229574822 571126931 469341419 702184356 904366313 746328903 842820475 578092052 586236587 796973195 766841610 123554290 666934376 118830348 326368534 40766155 790927880 880528134 890721558 357539968 885997091 937508042 5345140 189162897 200...
output:
998002127
result:
ok 1 number(s): "998002127"
Test #7:
score: 0
Accepted
time: 877ms
memory: 11812kb
input:
199999 963761198400 124206358 425059813 396286827 293468808 45861386 890748681 587148852 2565459 137729579 865441288 710978415 682768035 62610967 490442955 426217252 132942846 314800009 680954919 208583546 438814504 79283475 26876485 718279429 714019319 799517726 874565672 262935553 180792133 654326...
output:
150795568
result:
ok 1 number(s): "150795568"
Test #8:
score: -100
Wrong Answer
time: 71ms
memory: 13360kb
input:
200000 549755813888 154464482 922506517 440386473 592872114 740241030 65093066 195263806 140372279 686442905 168161853 216221623 831551102 203181658 450884227 451817602 487635386 545548989 216183567 218772329 189773367 217113749 131736290 966799162 875967103 93914434 521722337 383140644 765520582 20...
output:
907722857
result:
wrong answer 1st numbers differ - expected: '437668137', found: '907722857'