QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398669#3766. 抄板子SamponYWAC ✓112ms7140kbC++141.9kb2024-04-25 16:23:252024-04-25 16:23:25

Judging History

This is the latest submission verdict.

  • [2024-04-25 16:23:25]
  • Judged
  • Verdict: AC
  • Time: 112ms
  • Memory: 7140kb
  • [2024-04-25 16:23:25]
  • Submitted

answer

#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 1000005
int P;
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
  int s = 1;
  while(n) {
    if(n & 1) s = 1ll * s * p % P;
    p = 1ll * p * p % P, n >>= 1;
  }
  return s;
}
int n, w;
il vector<int> ntt(vector<int> f, int w) {
  if(SZ(f) <= 3) {
    int c = 1; vector<int> s(SZ(f));
    for(auto &sum : s) {
      int v = 1;
      for(auto x : f)
        addr(sum, 1ll * v * x % P),
        v = 1ll * v * c % P;
      c = 1ll * c * w % P;
    }
    assert(c == 1);
    return s;
  }
  int m = SZ(f) / 2; vector<int> a(m), b(m);
  FOR(i, 0, m - 1) a[i] = f[i * 2], b[i] = f[i * 2 + 1];
  int c = 1, p = 1ll * w * w % P, op = qpow(w, m);
  a = ntt(a, p), b = ntt(b, p);
  FOR(i, 0, m - 1) {
    f[i] = add(a[i], 1ll * b[i] * c % P);
    f[i + m] = add(a[i], 1ll * op * b[i] % P * c % P);
    c = 1ll * c * w % P;
  }
  return f;
}
il void WORK() {
  // cerr << n << "\n";
  vector<int> f(n);
  for(auto &x : f) cin >> x; f = ntt(f, w);
  for(auto x : f) cout << x << " "; cout << "\n";
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  while(cin >> n >> P >> w) WORK();
  cerr << 1.0 * clock() / CLOCKS_PER_SEC;
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 112ms
memory: 7140kb

input:

3 7 1
1 2 3
3 7 2
1 2 3
6 458719 458718
91633 324072 357282 141401 443440 75350
768 514561 485375
306042 35097 10695 128492 291101 378867 192572 303052 4068 342913 491848 360207 96443 437578 343659 122388 452505 438388 28080 437341 145852 489939 126800 414663 240274 110690 274192 14591 129395 250161...

output:

6 6 6 
6 3 1 
57021 351532 57021 351532 57021 351532 
214897 213991 103216 146406 395817 287610 302603 231730 269555 118458 242202 387998 172699 431431 363434 474119 453099 473997 342030 171160 491310 193812 432928 132545 294019 203809 179721 482448 311968 475195 210406 140340 198951 194087 497153 1...

result:

ok 120 lines