結果
| 問題 | No.980 Fibonacci Convolution Hard |
| ユーザー |
 sntea
|
| 提出日時 | 2020-02-16 05:27:34 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 168 ms / 2,000 ms |
| コード長 | 5,119 bytes |
| コンパイル時間 | 2,167 ms |
| コンパイル使用メモリ | 187,612 KB |
| 実行使用メモリ | 19,712 KB |
| 最終ジャッジ日時 | 2024-10-06 14:18:55 |
| 合計ジャッジ時間 | 8,837 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 17 |
ソースコード
#ifdef LOCAL111#define _GLIBCXX_DEBUG#else#pragma GCC optimize ("O3")#define NDEBUG#endif// #define _USE_MATH_DEFINES#include <bits/stdc++.h>const int INF = 1e9;using namespace std;template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { os << '(' << p.first << ' ' << p.second << ')'; return os; }#define endl '\n'#define ALL(a) (a).begin(),(a).end()#define SZ(a) int((a).size())#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)#define REP(i,n) FOR(i,0,n)#define RREP(i,n) for (int i=(n)-1;i>=0;i--)#ifdef LOCAL111#define DEBUG(x) cout<<#x<<": "<<(x)<<endltemplate<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}#else#define DEBUG(x) truetemplate<typename T> void dpite(T a, T b){ return; }#endif#define F first#define S second#define SNP string::npos#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}template<typename T,typename U,typename... V>typename enable_if<is_same<T, U>::value!=0>::typefill_v(U &u,const V... v){u=U(v...);}template<typename T,typename U,typename... V>typename enable_if<is_same<T, U>::value==0>::typefill_v(U &u,const V... v){for(auto &e:u) fill_v<T>(e,v...);}const array<int, 4> dx = {0, 1, 0, -1};const array<int, 4> dy = {1, 0, -1, 0};typedef long long int LL;typedef unsigned long long ULL;typedef pair<int,int> P;void ios_init(){//cout.setf(ios::fixed);//cout.precision(12);#ifdef LOCAL111return;#endifios::sync_with_stdio(false); cin.tie(0);}template<long long MOD>class ModInt {public:const static long long mod = MOD;long long x;ModInt() {x = 0;}ModInt(long long x) {x %= mod;this->x = x < 0 ? x+mod : x;}int get() const {return (int)x;}ModInt &operator+=(ModInt that) {if((x += that.get()) >= mod) x -= mod;return *this;}ModInt &operator-=(ModInt that) {if((x += mod-that.get()) >= mod) x -= mod;return *this;}ModInt &operator*=(ModInt that) {x = x*that.get()%mod;return *this;}ModInt &operator/=(ModInt that) {return *this *= that.inverse();}ModInt operator+(ModInt that) const {return ModInt(*this) += that;}ModInt operator-(ModInt that) const {return ModInt(*this) -= that;}ModInt operator*(ModInt that) const {return ModInt(*this) *= that;}ModInt operator/(ModInt that) const {return ModInt(*this) /= that;}ModInt inverse() const {using std::swap;long long a = x, b = mod, u = 1, v = 0;while(b) {long long t = a/b;a -= t*b; swap(a,b);u -= t*v; swap(u,v);}return ModInt(u);}ModInt pow(int n) const{ModInt b = *this;ModInt res = 1;while(n != 0) {if(n&1){res *= b;}b *= b;n >>= 1;}return res;}bool operator==(ModInt that) const { return x == that.get(); }bool operator!=(ModInt that) const { return x != that.get(); }ModInt operator-() const { return x == 0 ? 0 : ModInt(mod-x); }};template<long long MOD> ostream& operator<< (ostream& os, const ModInt<MOD>& m) { os << m.get(); return os; }template<long long MOD> istream& operator>> (istream& is, ModInt<MOD>& m){ long long n; is >> n; m = n; return is;}typedef ModInt<1000000007> mint;class ConvQuery {vector<mint> fac;vector<mint> facinv;public:ConvQuery(int n) {fac = vector<mint>(n+1);facinv = vector<mint>(n+1);fac[0] = 1;facinv[0] = 1;for(int i = 0; i < n; ++i) {fac[i+1] = fac[i]*(i+1);facinv[i+1] = fac[i+1].inverse();}}mint operator()(int n, int m) {if(n >= 0 and 0 <= m and m <= n) return fac[n]*facinv[n-m]*facinv[m];else return 0;}};using Poly = vector<mint>;Poly mul(const Poly& x, const Poly& y) {Poly res(SZ(x) + SZ(y) - 1);REP(i, SZ(x)) REP(j, SZ(y)) {res[i + j] += x[i] * y[j];}return res;}Poly div(const Poly& x, const Poly& y, int k) {Poly res(k);deque<mint> rem(ALL(x));while(SZ(rem) < SZ(y)) {rem.push_back(0);}REP(i, k) {mint co = rem[0] / y[0];res[i] = co;REP(j, SZ(y)) {rem[j] -= co * y[j];}rem.pop_front();if(SZ(rem) < SZ(y)) {rem.push_back(0);}}return res;}int main(){ios_init();int p;while(cin >> p) {int nq;cin >> nq;vector<int> q(nq);REP(i, nq) {cin >> q[i];q[i]--;}int ma = *max_element(ALL(q));Poly x = {0, 1};Poly y = {1, -p, -1};x = mul(x, x);y = mul(y, y);auto pol = div(x, y, ma + 1);dpite(ALL(pol));REP(i, nq) {cout << pol[q[i] - 1] << endl;}// auto pol = div();}return 0;}