Submission #6871256


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

std::vector<ll> fac(510000, 1), finv(510000, 1), inv(510000, 1);

void c4_init(ll m) {
    for (ll i = 2; i < 510000; i++) {
        fac[i] = fac[i - 1] * i % m;
        inv[i] = m - inv[m%i] * (m / i) % m;
        finv[i] = finv[i - 1] * inv[i] % m;
    }
}

ll c4(ll n, ll k, ll m) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % m) % m;
}

signed main() {
  ll p;
  cin>>p;
  vector<ll> a(p-1);
  rep(i,p)
    cin>>a[i];
  c4_init(p);
  vector<ll> b(p-1,0);
  rep(i,p){
    if (a[i] == 0)
      continue;
    (b[0] += 1) %= p;
    ll pw = 1;
    for (ll j=p-1; j>=0; j--) {
      (b[j] += p*p - pw * c4(p-1, j, p)) %= p;
      (pw *= p-i) %= p;
    }
  }
  rep(i,p){
    cout<<b[i]<<(i!=p-1 ? " ":"");
  }
  cout<<endl;
  return 0;
}

Submission Info

Submission Time
Task F - Polynomial Construction
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1067 Byte
Status
Exec Time 467 ms
Memory 12416 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03
All 600 / 600 a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43
Case Name Status Exec Time Memory
a01 29 ms 12160 KB
a02 29 ms 12160 KB
a03 29 ms 12160 KB
b04 29 ms 12160 KB
b05 29 ms 12160 KB
b06 29 ms 12160 KB
b07 30 ms 12288 KB
b08 467 ms 12288 KB
b09 467 ms 12288 KB
b10 467 ms 12288 KB
b11 30 ms 12288 KB
b12 30 ms 12288 KB
b13 248 ms 12288 KB
b14 248 ms 12288 KB
b15 92 ms 12288 KB
b16 404 ms 12288 KB
b17 248 ms 12288 KB
b18 248 ms 12288 KB
b19 244 ms 12288 KB
b20 331 ms 12288 KB
b21 423 ms 12288 KB
b22 444 ms 12288 KB
b23 466 ms 12288 KB
b24 465 ms 12288 KB
b25 467 ms 12288 KB
b26 255 ms 12288 KB
b27 163 ms 12288 KB
b28 75 ms 12416 KB
b29 54 ms 12288 KB
b30 33 ms 12288 KB
b31 32 ms 12288 KB
b32 30 ms 12288 KB
b33 29 ms 12160 KB
b34 29 ms 12160 KB
b35 211 ms 12288 KB
b36 351 ms 12288 KB
b37 131 ms 12288 KB
b38 47 ms 12288 KB
b39 29 ms 12160 KB
b40 92 ms 12288 KB
b41 31 ms 12160 KB
b42 47 ms 12288 KB
b43 45 ms 12288 KB