結果

問題 No.194 フィボナッチ数列の理解(1)
コンテスト
ユーザー hashiryo
提出日時 2019-07-12 20:35:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 205 ms / 5,000 ms
コード長 9,160 bytes
コンパイル時間 2,528 ms
コンパイル使用メモリ 186,696 KB
実行使用メモリ 27,364 KB
最終ジャッジ日時 2024-11-18 12:38:47
合計ジャッジ時間 4,862 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/2;
const ll MOD = 1e9+7;

typedef long long ll;
inline ll add(ll a, ll b, ll M) { // a + b (mod M)
    return (a += b) >= M ? a - M : a;
}
inline ll sub(ll a, ll b, ll M) { // a - b (mod M)
    return (a -= b) < 0 ? a + M : a;
}
/*
inline int mul(int a,int b,int mo) {
	int d,r;
	if(a==0 || b==0) return 0;
	if(a==1 || b==1) return max(a,b);
	__asm__("mull %4;"
	        "divl %2"
		: "=d" (r), "=a" (d)
		: "r" (mo), "a" (a), "d" (b));
	return r;
}
*/
ll mul(ll a, ll b, ll M) { // a * b (mod M)
    ll r = a*b - (ll)((long double)(a)*b/M+.5)*M;
    return r < 0 ? r + M: r;
}
inline ll div(ll a, ll b, ll M) { // solve b x == a (mod M)
    ll u = 1, x = 0, s = b, t = M;
    while (s) { // extgcd for b x + M s = t
        ll q = t / s;
        swap(x -= u * q, u);
        swap(t -= s * q, s);
    }
    if (a % t) return -1; // infeasible
    return mul(x < 0 ? x + M : x, a / t, M); // b (xa/t) == a (mod M)
}
inline ll pow(ll a, ll b, ll M) {
    ll x = 1;
    for (; b > 0; b >>= 1) {
        if (b & 1) x = mul(a , x , M);
        a = mul(a , a , M);
    }
    return x;
}

// p(x) = p[0] + p[1] x + ... + p[n-1] x^n-1
// assertion: p.back() != 0
typedef vector<ll> poly;
ostream& operator<<(ostream &os, const poly &p) {
    bool head = true;
    for (size_t i = 0; i < p.size(); ++i) {
        if (p[i] == 0) continue;
        if (!head) os << " + ";
        os << p[i];
        head = false;
        if (i >= 1) os << " x";
        if (i >= 2) os << "^" << i;
    }
    return os;
}
inline poly add(poly p, const poly &q, ll M) {
    if (p.size() < q.size()) p.resize(q.size());
    for (size_t i = 0; i < q.size(); ++i)
        p[i] = add(p[i], q[i], M);
    while (!p.empty() && !p.back()) p.pop_back();
    return p;
}
inline poly sub(poly p, const poly &q, ll M) {
    if (p.size() < q.size()) p.resize(q.size());
    for (size_t i = 0; i < q.size(); ++i)
        p[i] = sub(p[i], q[i], M);
    while (!p.empty() && !p.back()) p.pop_back();
    return p;
}

// naive multiplication in O(n^2)
inline poly mul_n(const poly &p, const poly &q, ll M) {
    if (p.empty() || q.empty()) return {};
    poly r(p.size() + q.size() - 1);
    for (int i = 0; i < p.size(); ++i)
        for (int j = 0; j < q.size(); ++j)
            r[i+j] = add(r[i+j], mul(p[i], q[j], M), M);
    while (!r.empty() && !r.back()) r.pop_back();
    return r;
}

// naive division (long division) in O(n^2)
inline pair<poly,poly> divmod_n(poly p, poly q, ll M) {
    poly u(p.size() - q.size() + 1);
    ll inv = div(1, q.back(), M);
    for (int i = u.size()-1; i >= 0; --i) {
        u[i] = mul(p.back(), inv, M);
        for (int j = 0; j < q.size(); ++j)
            p[j+p.size()-q.size()] = sub(p[j+p.size()-q.size()], mul(q[j], u[i], M), M);
        p.pop_back();
    }
    return {u, p};
}


namespace FFT {
    const int max_base = 19, maxN = 1 << max_base; // N <= 2e5
    const double PI = acos(-1);
    struct num {
        double x{}, y{};
        num() = default;
        num(double x, double y): x(x), y(y) {}
        explicit num(double r): x(cos(r)), y(sin(r)) {}
    };
    inline num operator+(num a, num b) { return {a.x + b.x, a.y + b.y}; }
    inline num operator-(num a, num b) { return {a.x - b.x, a.y - b.y}; }
    inline num operator*(num a, num b) { return {a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x}; }
    inline num conj(num a) {return {a.x, -a.y}; }
    num root[maxN];
    int rev[maxN];
    bool is_root_prepared = false;

    inline void prepare_root(){
        if(is_root_prepared) return;
        is_root_prepared = true;
        root[1] = num(1, 0);
        for (int i = 1; i < max_base; ++i) {
            num x(2*PI / (1LL << (i+1)));
            for (ll j = (1LL << (i-1)); j < (1LL << (i)); ++j) {
                root[2*j] = root[j];
                root[2*j+1] = root[j]*x;
            }
        }
    }

    int base=1, N=2;
    int lastN = -1;

    inline void prepare_rev(){
        if(lastN == N) return;
        lastN = N;
        for (int i = 0; i < N; ++i) rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (base - 1));
    }

    inline void fft(num *a, num *f){
        for (int i = 0; i < N; ++i) f[i] = a[rev[i]];
        for (int k = 1; k < N; k <<= 1) {
            for (int i = 0; i < N; i += 2*k) {
                for (int j = 0; j < k; ++j) {
                    num z = f[i+j+k]* root[j+k];
                    f[i+j+k] = f[i+j] - z;
                    f[i+j] = f[i+j] + z;
                }
            }
        }
    }
    num a[maxN], b[maxN], f[maxN], g[maxN];
    ll A[maxN], B[maxN], C[maxN];

    inline void multi_mod(int m){
        for (int i = 0; i < N; ++i) {
            ll x = A[i] % m;
            a[i] = num(x & ((1LL << 15)-1), x >> 15);
        }
        for (int i = 0; i < N; ++i) {
            ll x = B[i] % m;
            b[i] = num(x & ((1LL << 15)-1), x >> 15);
        }
        fft(a, f);
        fft(b, g);
        for (int i = 0; i < N; ++i) {
            int j = (N-i) &(N-1);
            num a1 = (f[i] + conj(f[j])) * num(0.5, 0);
            num a2 = (f[i] - conj(f[j])) * num(0, -0.5);
            num b1 = (g[i] + conj(g[j])) * num(0.5/N, 0);
            num b2 = (g[i] - conj(g[j])) * num(0, -0.5/N);
            a[j] = a1*b1 + a2*b2 * num(0, 1);
            b[j] = a1*b2 + a2*b1;
        }
        fft(a, f);
        fft(b, g);
        for (int i = 0; i < N; ++i) {
            ll aa = f[i].x + 0.5;
            ll bb = g[i].x + 0.5;
            ll cc = f[i].y + 0.5;
            C[i] = (aa + bb % m * (1LL << 15) + cc% m *(1LL << 30)) % m;
        }
    }

    inline void prepare_AB(int n1, int n2){
        if(N > n1+n2){
            base = 1;
            N = 2;
        }
        while(N < n1+n2) base++, N <<= 1;
        for (int i = n1; i < N; ++i) A[i] = 0;
        for (int i = n2; i < N; ++i) B[i] = 0;
        prepare_root();
        prepare_rev();
    }

    inline void multi_mod(int n1, int n2, int m){
        prepare_AB(n1, n2);
        multi_mod(m);
    }
}
inline poly mul(poly A, poly B,int M){
    while(!A.empty()&&!A.back())A.pop_back();
    while(!B.empty()&&!B.back())B.pop_back();
    if(A.size()+B.size()<80)return mul_n(A,B,M);
    poly C(A.size() + B.size()-1);
    for (size_t i = 0; i < A.size(); ++i) FFT::A[i] = A[i];
    for (size_t i = 0; i < B.size(); ++i) FFT::B[i] = B[i];
    FFT::multi_mod(A.size(), B.size(), M);
    for (size_t i = 0; i < C.size(); ++i) C[i] = FFT::C[i];
    while(!C.empty()&&!C.back())C.pop_back();
    return C;
}


inline poly inverse(const poly &f,ll M,int size){
    poly t = {div(1, f[0], M)};
    if (t[0] < 0) return { {}, {} }; // infeasible
    poly ff(1,f[0]);
    for (int k = 2; k <= 2*size; k <<= 1) {
        for(int i=k/2;i<(int)f.size()&&i<k;i++)ff.push_back(f[i]);
        poly s = mul(mul(t,t,M),ff, M);
        s.resize(k);
        for (int i = 0; i < k/2; ++i){
            s[i] = sub(2*t[i], s[i], M);
            s[i+k/2] = sub(0, s[i+k/2], M);
        }
        t=s;
    }
    t.resize(size);
    return t;
}

inline poly quotient(poly a,poly b,ll M,poly brevinv={}){
  int s=a.size()-b.size()+1;
  if(s<=0)return {};
  if(brevinv.empty()){
    while(!b.empty()&&!b.back())b.pop_back();
    s=a.size()-b.size()+1;
    reverse(b.begin(),b.end());
    brevinv=inverse(b,M,s);
  }
  brevinv.resize(s);
  while(!brevinv.empty()&&!brevinv.back())brevinv.pop_back();
  reverse(a.begin(),a.end());
  a.resize(s);
  while(!a.empty()&&!a.back())a.pop_back();
  poly ret = mul(a,brevinv,M);
  ret.resize(s);
  reverse(ret.begin(),ret.end());
  while(!ret.empty()&&!ret.back())ret.pop_back();
  return ret;
}

inline pair<poly,poly> divmod(const poly &a,const poly &b,ll M,poly brevinv={}){
  if(a.size()<b.size())return {{},a};
  if (b.size()<256){
    return divmod_n(a,b,M);
  }
  poly q=quotient(a,b,M,brevinv);
  return {q,sub(a,mul(q,b,M),M)};
}

//x^n (mod f)
poly x_pow_mod(ll n, const poly& f,ll M) {
  poly invf=f;
  reverse(invf.begin(),invf.end());
  invf=inverse(invf,M,f.size());
  poly cur={1},x={0,1};
  while(n){
    if(n%2)cur=divmod(mul(cur,x,M),f,M,invf).second;
    x=divmod(mul(x,x,M),f,M,invf).second;
    n>>=1;
  }
  return cur;
}
#include <ctime>
double tick() {
  static clock_t oldtick;
  clock_t newtick = clock();
  double diff = 1.0*(newtick - oldtick) / CLOCKS_PER_SEC;
  oldtick = newtick;
  return diff;
}
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N,K;cin>>N>>K;
  vll A(N),sum(N+1,0);
  for(ll i=0;i<N;i++){
    cin>>A[i];
    (sum[i]+=A[i])%=MOD;
    sum[i+1] = sum[i];
  }
  sum[N] = 2*sum[N]%MOD;
  vll P(N+2,0);
  P[0]=1;
  P[N]=MOD-2;
  P[N+1]=1;
  poly r = x_pow_mod(K-2,P,MOD);
  ll S1=0;
  for(ll i=0;i<=N;i++){
    (S1+=sum[i]*r[i]%MOD)%=MOD;
  }
  r = divmod(mul(r,{0,1},MOD),P,MOD).second;
  ll S2=0;
  for(ll i=0;i<=N;i++){
    (S2+=sum[i]*r[i]%MOD)%=MOD;
  }
  cout<<(S2-S1+MOD)%MOD<<" "<<S2<<endl;
  return 0;
}
0