結果
問題 | No.40 多項式の割り算 |
ユーザー |
![]() |
提出日時 | 2021-12-30 18:08:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 2,070 bytes |
コンパイル時間 | 2,311 ms |
コンパイル使用メモリ | 205,008 KB |
最終ジャッジ日時 | 2025-01-27 07:41:28 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>using namespace std;using namespace atcoder;using mint = modint1000000007;#define ll long longtemplate <typename T>T eval(vector<T> f, T v) {T res = 0;for (int i = (int)f.size()-1; i >= 0; i--) {res *= v;res += f[i];}return res;}template <typename T>vector<T> diff(vector<T> f) {int n = (int)f.size();vector<T> res(n-1, 0);for (int i = 1; i < n; i++) res[i-1] = f[i] * i;return res;}template <typename T>vector<T> integral(vector<T> f) {int n = (int)f.size();vector<mint> res(n+1, 0);for (int i = 0; i < n; i++) res[i+1] = f[i] / (i+1);return res;}template <typename T>vector<T> multiply(vector<T> f, vector<T> g) {int n = (int)f.size();int m = (int)g.size();vector<mint> res(n+m-1, 0);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {res[i+j] += f[i] * g[j];}}return res;}// (quotient, remainder)template <typename T>pair<vector<T>, vector<T>> divide(vector<T> f, vector<T> g) {int n = (int)f.size();int m = (int)g.size();vector<mint> res(n, 0);for (int i = n-1; i >= m-1; i--) {res[i] = f[i]/g[m-1];for (int j = m-1; j >= 0; j--) {f[i-(m-1-j)] -= res[i]*g[j];}}int l = 0;for (int i = 0; i < n; i++) {if (f[i].val() != 0) l = i;}f.resize(l+1);return make_pair(res, f);}int main() {ios::sync_with_stdio(0);cin.tie(0);int D;cin >> D;vector<ll> a(D+1);for (int i=0;i<D+1;i++) cin >> a[i];vector<mint> f(D+1);for (int i=0;i<D+1;i++) f[i] = a[i];vector<mint> g = {0, -1, 0, 1};auto h = divide(f, g).second;cout << h.size()-1 << "\n";for (int i=0;i<h.size();i++) {if (h[i].val() >= 5e8) {cout << h[i].val()-(1e9+7);} else {cout << h[i].val();}if (i != h.size()-1) cout << " ";else cout << "\n";}return 0;}