QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#425954 | #6102. Query on a Tree | HKOI0# | WA | 0ms | 6680kb | C++20 | 7.1kb | 2024-05-30 19:34:18 | 2024-05-30 19:34:19 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
const int MOD = 998244353, root = 62;
typedef vector<ll> vl;
int pm(int a, int b){
if (b == 0) return 1;
return pm(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD;
}
int mi(int a){
return pm(a, MOD - 2);
}
void ntt(vl & a) {
int n = a.size(), L = 63 - __builtin_clzll(n);
static vl rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
ll z[] = {1, pm(root, MOD >> s)};
for (int i = k; i < k * 2; i++) rt[i] = rt[i / 2] * z[i & 1] % MOD;
}
vi rev(n);
for (int i = 0; i < n; i++)
rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
for (int i = 0; i < n; i++)
if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) for (int j = 0; j < k; j++) {
int z = rt[j + k] * a[i + j + k] % MOD, &ai = a[i + j];
a[i + j + k] = ai - z + (z > ai ? MOD : 0);
ai += (ai + z >= MOD ? z - MOD : z);
}
}
vl conv(const vl& a, const vl& b) {
if (a.empty() || b.empty()) return {};
int s = a.size() + b.size() - 1, B = 64 - __builtin_clzll(s), n = 1 << B;
int inv = mi(n);
vl L(a), R(b), out(n);
L.resize(n), R.resize(n); ntt(L); ntt(R);
for (int i = 0; i < n; i++) {
out[-i & (n - 1)] = L[i] * R[i] % MOD * inv % MOD;
}
ntt(out);
return {out.begin(), out.begin() + s};
}
const int N = 2e5 + 11;
int fa[N], fi[N];
int binom(int n, int r){
return fa[n] * fi[n - r] % MOD * fi[r] % MOD;
}
struct poly{
vector<int> a;
void normalise() { while (!a.empty() && a.back() == 0) a.pop_back(); }
poly(int v) { a.push_back(v); normalise(); }
poly(vector<int> a) : a(a) { normalise(); }
bool is_zero() const { return a.empty(); }
int size() const { return a.size(); }
int deg() const { return (int) a.size() - 1; }
void resize(int n) { a.resize(n); }
int operator[] (int idx) const { return 0 <= idx && idx < a.size() ? a[idx] : 0; }
int& at(int idx) { assert(0 <= idx && idx < a.size()); return a[idx]; }
void print() const { for (auto x : a) cout << x << ' '; cout << endl; }
poly operator* (const poly& o) const {
return conv(a, o.a);
}
friend poly operator+ (const poly& a, const poly& b){
vector<int> res(max(a.size(), b.size()));
for (int i = 0; i < res.size(); i++) {
res[i] = a[i] + b[i] >= MOD ? a[i] + b[i] - MOD : a[i] + b[i];
}
return res;
}
friend poly operator- (const poly& a, const poly& b){
vector<int> res(max(a.size(), b.size()));
for (int i = 0; i < res.size(); i++) {
res[i] = a[i] - b[i] < 0 ? a[i] - b[i] + MOD : a[i] - b[i];
}
return res;
}
void operator-= (const poly& o) { *this = *this - o; }
poly mod_xk(size_t k) const {
return vector<int>{a.begin(), a.begin() + min(a.size(), k)};
}
poly mul_xk(size_t k) const {
vector<int> b(k, 0); for (auto x : a) b.push_back(x);
return b;
}
poly div_xk(size_t k) const {
return size() < k ? vector<int>{} : vector<int>{a.begin() + k, a.end()};
}
poly substr(size_t l, size_t r) const {
return div_xk(l).mod_xk(r - l);
}
poly deriv () const {
if (size() <= 1) return {0};
vector<int> res(size() - 1);
for (int i = 1; i <= deg(); i++) {
res[i - 1] = a[i] * i % MOD;
}
return res;
}
poly integr () const {
vector<int> res(size() + 1);
for (int i = 0; i <= deg(); i++) {
res[i + 1] = a[i] * mi(i + 1) % MOD;
}
return res;
}
poly negx () const {
vector<int> res(size());
for (int i = 0; i < size(); i++) {
res[i] = i % 2? (MOD - a[i]) % MOD : a[i];
}
return res;
}
poly x2 () const {
if (size() == 0) return {0};
vector<int> res(size() * 2 - 1);
for (int i = 0; i < size(); i++) {
res[i * 2] = a[i];
}
return res;
}
pair<poly, poly> bisect() const {
vector<int> q0, q1;
for (int i = 0; i < size(); i++) {
(i % 2 ? q1 : q0).push_back(a[i]);
}
return {q0, q1};
}
poly recp(size_t k) const {
auto q = mod_xk(k);
if (k == 1) return vector<int>{mi(a[0])};
auto [q0, q1] = q.negx().bisect();
poly t = (q0 * q0 - (q1 * q1).mul_xk(1));
poly it = t.recp((k + 1) / 2);
return ((q0 * it).x2() + (q1 * it).x2().mul_xk(1)).mod_xk(k);
}
poly log(size_t n) const {
assert(a[0] == 1);
return (deriv().mod_xk(n) * recp(n)).integr().mod_xk(n);
}
poly exp(size_t n) const {
if (is_zero()) return 1;
assert(a[0] == 0);
poly ans = 1;
size_t a = 1;
while (a < n) {
poly C = ans.log(a * 2).div_xk(a) - substr(a, a * 2);
ans -= (ans * C).mod_xk(a).mul_xk(a);
a *= 2;
}
return ans.mod_xk(n);
}
poly egf() const {
vector<int> res(size());
for (int i = 0; i <= deg(); i++) {
res[i] = a[i] * fi[i] % MOD;
}
return res;
}
poly ops() const {
vector<int> res(size());
for (int i = 0; i <= deg(); i++) {
res[i] = a[i] * fa[i] % MOD;
}
return res;
}
poly mul_x2(int x) const {
vector<int> res(size());
int m2 = 1, m1 = 1;
for (int i = 1; i <= deg(); i++) {
m2 = m2 * m1 % MOD;
res[i] = a[i] * m2 % MOD;
m1 = m1 * x % MOD;
}
return res;
}
};
int a[4];
void solve() {
int m, k; cin >> m >> k;
for (int i = 0; i <= k; i++) cin >> a[i];
vector<int> t(m + 1);
t[1] = 1; for (int i = 2; i <= m; i++) t[i] = pm(i, i - 2);
a[1] = a[1] * mi(a[0]) % MOD;
a[2] = a[2] * mi(a[0]) % MOD;
poly S1 = poly(t).egf().mul_x2(a[1]);
poly T = poly(t).egf().mul_x2(a[1] * mi(a[2]) % MOD);
T = T.deriv().mul_xk(1);
// poly T = vector<int>{0, 1};
// (((1 - T).log(m + 1) * (-1) - T - T * T * mi(2)) * mi(2)).ops().print();
poly S2 = (T * T * T * mi(6) + T * T * T * T * mi(8)).mod_xk(m + 1).mul_x2(a[2]);
// poly S2 = (((1 - T).log(m + 1) * (-1) - T - T * T * mi(2)) * mi(2)).mul_x2(a[2]);
T.print(); (S2.ops() * 2).print();
poly S = S1 + S2;
poly ans = S.exp(m + 1).mul_x2(a[0]).ops();
for (int i = 2; i <= m; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
signed main() {
fa[0] = 1; for (int i = 1; i < N; i++) fa[i] = fa[i - 1] * i % MOD;
fi[N - 1] = mi(fa[N - 1]); for (int i = N - 2; i >= 0; i--) fi[i] = fi[i + 1] * (i + 1) % MOD;
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 6680kb
input:
7 1 2 1 3 1 5 2 7 4 6 4 7 6 1 1 2 1 2 4 1 2 3 4 5 1 2 4 6 7 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7
output:
0 1 3 23 416 17149 1578704 319498663
result:
wrong answer 4th numbers differ - expected: '10', found: '23'