Submission #7020148

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<complex>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<stack>
#include<set>

using namespace std;
#define endl '\n'

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;

template<typename T = long long>
T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }

// value
int p;
int a[3000];

/* べき乗を計算 */
ll mpow(ll v, long long k) {
	ll res = 1, tmp = v;
	while (k) {
		if (k & 1) res *= tmp;
		tmp *= tmp;
		res %= p;
		tmp %= p;
		k >>= 1;
	}
	return res;
}

ll inv(ll v) { return mpow(v, p - 2); }

ll b[3000];
ll fact[3000], fact_inv[3000];

void calc() {
	fact[0] = 1;
	fact_inv[0] = 1;
	for (int i = 1; i < 3000; i++) {
		fact[i] = fact[i - 1] * i;
		fact[i] %= p;
		fact_inv[i] = inv(fact[i]);
	}
}

ll comb(ll n, ll r) {
	return (fact[n] * fact_inv[r] % p) * fact_inv[n - r] % p;
}

void solve() {

	cin >> p;
	for (int i = 0; i < p; i++) {
		cin >> a[i];
	}

	calc();

	for (int j = 0; j < p; j++) {
		if (a[j] == 1) {
			ll j2 = 1;
			for (int k = 0; k < p; k++) {
				b[p - 1 - k] += (-1) * comb(p - 1, k) * j2 % p;
				b[p - 1 - k] += p; b[p - 1 - k] %= p;
				j2 *= -j; j2 += p; j2 %= p;
			}
			b[0] += 1;
		}
	}

	for (int i = 0; i < p - 1; i++) {
		cout << b[i] % p << " ";
	}

	cout << b[p - 1] % p << endl;

	return;

}

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	solve();

	return 0;

}

Submission Info

Judge Result