QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#120135#6184. Atcoder Problemhos_lyricAC ✓125ms6392kbC++147.1kb2023-07-06 14:10:382023-07-06 14:10:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-06 14:10:41]
  • 评测
  • 测评结果:AC
  • 用时:125ms
  • 内存:6392kb
  • [2023-07-06 14:10:38]
  • 提交

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