QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#120135 | #6184. Atcoder Problem | hos_lyric | AC ✓ | 125ms | 6392kb | C++14 | 7.1kb | 2023-07-06 14:10:38 | 2023-07-06 14:10:41 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;
constexpr int LIM_INV = 200'010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];
void prepare() {
inv[1] = 1;
for (int i = 2; i < LIM_INV; ++i) {
inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
}
fac[0] = invFac[0] = 1;
for (int i = 1; i < LIM_INV; ++i) {
fac[i] = fac[i - 1] * i;
invFac[i] = invFac[i - 1] * inv[i];
}
}
Mint binom(Int n, Int k) {
if (n < 0) {
if (k >= 0) {
return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
} else if (n - k >= 0) {
return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
} else {
return 0;
}
} else {
if (0 <= k && k <= n) {
assert(n < LIM_INV);
return fac[n] * invFac[k] * invFac[n - k];
} else {
return 0;
}
}
}
// f = (1+z)^a (1-z)^b
// f' = a f/(1+z) - b f/(1-z)
// (1-z^2) f' = (a(1-z) - b(1+z)) f
vector<Mint> expand(int len, Mint a, Mint b) {
vector<Mint> fs(len);
fs[0] = 1;
fs[1] = a - b;
for (int i = 1; i < len - 1; ++i) {
fs[i + 1] = inv[i + 1] * ((a - b) * fs[i] + (-a - b + (i - 1)) * fs[i - 1]);
}
return fs;
}
/*
mod (x[0]^2, ..., x[E-1]^2)
ans(t)
= [x^X] \prod[0<=p<M] (1 + t x^p) / (1-t^2)
= (1/2^E) \sum[0<=q<2^E] (-1)^#(X&q) \prod[0<=p<M] (1 + (-1)^#(p&q) t)
M = 1001001001(2)
0*********
1000******
1001000***
1001001000
classify q by: \sum[0<=p<M] (-1)^#(p&q)
depends on bsf(q) and (-1)^#(M&q)
*/
vector<Mint> solve(int N, Int M, Int X) {
int E;
for (E = 0; !(M <= 1LL << E && X < 1LL << E); ++E) {}
#ifdef LOCAL
cerr<<"E = "<<E<<", M = "<<M<<", X = "<<X<<endl;
map<Int,Int>brt;
for(Int q=0;q<1LL<<E;++q){
Int dif=0;
for(Int p=0;p<M;++p)dif+=(__builtin_parity(p&q)?-1:+1);
// cerr<<" "<<q<<": "<<dif<<" "<<(__builtin_parity(X&q)?-1:+1)<<endl;
brt[dif]+=(__builtin_parity(X&q)?-1:+1);
}
cerr<<" brt = ";pv(brt.begin(),brt.end());
#endif
vector<Mint> ans(N, 0);
auto add = [&](Int dif, Int val) -> void {
#ifdef LOCAL
cerr<<" add "<<dif<<" "<<val<<endl;
brt[dif]-=val;
#endif
// (1+t)^num0 (1-t)^num0 / (1-t^2)^M
const Int num0 = (M + dif) / 2;
const Int num1 = (M - dif) / 2;
const auto res = expand(N, num0 - M, num1 - M);
for (int i = 0; i < N; ++i) {
ans[i] += val * res[i];
}
};
{
// q = 0
add(M, +1);
Int crt[2] = {1, 0};
Int m = M & 1LL << E;
for (int e = E; --e >= 0; ) {
// bsf(q) = e
Int dif;
if (M >> e & 1) {
const Int mm = m + (1LL << e);
dif = (mm - m) - (M - mm);
m = mm;
} else {
dif = M - m;
}
const int sigX = (X >> e & 1) ? -1 : +1;
add(+dif, sigX * crt[0]);
add(-dif, sigX * crt[1]);
Int nxt[2] = {};
for (int s = 0; s < 2; ++s) {
nxt[s] += crt[s];
nxt[s ^ (M >> e & 1)] += sigX * crt[s];
}
memcpy(crt, nxt, sizeof(nxt));
}
}
#ifdef LOCAL
for(const auto&kv:brt)assert(kv.second==0);
#endif
const Mint invTwo = Mint(2).pow(-E);
for (int i = 0; i < N; ++i) {
ans[i] *= invTwo;
}
return ans;
}
int main() {
prepare();
#ifdef LOCAL
for (Int m = 0; m <= 64; ++m) for (Int x = 0; x <= 64; ++x) {
// solve(10, m, x);
}
#endif
int N;
Int M, X;
for (; ~scanf("%d%lld%lld", &N, &M, &X); ) {
++N;
++M;
const auto ans = solve(N, M, X);
for (int i = 1; i < N; ++i) {
printf("%u\n", ans[i].x);
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 6064kb
input:
5 6 7
output:
0 3 7 25 49
result:
ok 5 number(s): "0 3 7 25 49"
Test #2:
score: 0
Accepted
time: 3ms
memory: 6040kb
input:
10 100 0
output:
1 101 1418 38280 756912 13403840 203823022 755806367 368916768 79402702
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 116ms
memory: 6372kb
input:
100000 1152921504606846975 1135906340197086405
output:
1 840200159 757208156 45079381 234857894 778713378 157653094 401709782 230628443 430324215 684650792 138395965 762802417 682389935 242725537 447284705 699422690 810878852 984774439 636218249 418883769 680950647 354420417 642906873 685645540 223359490 370171153 594906335 423999750 963169862 122670093...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 125ms
memory: 6392kb
input:
100000 1135906340197086405 0
output:
1 113027812 695077004 213731896 525802203 335155205 835852454 274346456 475280537 201443359 582037369 724576833 696494373 854514319 826907652 9179469 991556563 422731810 822598649 760659125 311818894 452007631 425590283 442774158 843151305 635490300 6982067 766134056 733977525 692498660 973160682 71...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 121ms
memory: 6368kb
input:
100000 1135906340197086405 1152921504606846975
output:
0 271072006 745954500 176515717 442855562 179056346 723923577 507918653 449150776 606758112 658684747 769476797 90012324 921104758 155944588 921730658 825936439 276825694 210555233 558400169 132510433 973023753 41449997 284153662 633262134 921817216 556971594 428704872 848487910 57553970 402713586 8...
result:
ok 100000 numbers
Test #6:
score: 0
Accepted
time: 121ms
memory: 6360kb
input:
100000 135906340197086405 1152921504606846975
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 120ms
memory: 6364kb
input:
100000 1135906340197086405 38986989798615317
output:
1 271072006 695077004 176515717 525802203 179056346 835852454 507918653 475280537 606758112 582037369 769476797 696494373 921104758 826907652 921730658 991556563 276825694 822598649 558400169 311818894 973023753 425590283 284153662 843151305 921817216 6982067 428704872 733977525 57553970 973160682 8...
result:
ok 100000 numbers
Test #8:
score: 0
Accepted
time: 123ms
memory: 6368kb
input:
99999 1152921504606846975 0
output:
1 682155965 757208156 402935458 234857894 302130892 157653094 717810642 230628443 15486544 684650792 745177033 762802417 294962385 242725537 281332463 699422690 669053148 984774439 572399878 418883769 788259891 354420417 872769360 685645540 776292040 370171153 30078222 423999750 253213607 122670093 ...
result:
ok 99999 numbers