結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー hashiryo
提出日時 2019-07-12 20:35:51
言語 C++14
(gcc 8.2.0)
結果
AC  
実行時間 232 ms
コード長 9,160 Byte
コンパイル時間 1,933 ms
使用メモリ 14,680 KB
最終ジャッジ日時 2019-07-12 20:35:55

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 2 ms
1,548 KB
sample2.txt AC 3 ms
1,552 KB
sample3.txt AC 10 ms
9,808 KB
system_test1.txt AC 3 ms
1,548 KB
system_test2.txt AC 3 ms
1,552 KB
system_test3.txt AC 2 ms
1,552 KB
system_test4.txt AC 3 ms
1,552 KB
system_test5.txt AC 3 ms
1,552 KB
system_test6.txt AC 3 ms
1,548 KB
system_test7.txt AC 4 ms
1,548 KB
system_test8.txt AC 3 ms
1,548 KB
system_test9.txt AC 3 ms
1,548 KB
system_test10.txt AC 3 ms
1,548 KB
system_test11.txt AC 3 ms
1,548 KB
system_test12.txt AC 3 ms
1,552 KB
system_test13.txt AC 3 ms
1,556 KB
system_test14.txt AC 4 ms
1,552 KB
system_test15.txt AC 3 ms
1,548 KB
system_test16.txt AC 4 ms
1,552 KB
system_test17.txt AC 10 ms
9,808 KB
testcase01.txt AC 2 ms
1,552 KB
testcase02.txt AC 232 ms
14,680 KB
testcase03.txt AC 3 ms
1,544 KB
testcase04.txt AC 106 ms
14,256 KB
testcase05.txt AC 116 ms
12,616 KB
testcase06.txt AC 109 ms
12,276 KB
testcase07.txt AC 184 ms
14,548 KB
testcase08.txt AC 17 ms
9,992 KB
testcase09.txt AC 85 ms
12,176 KB
testcase10.txt AC 37 ms
10,404 KB
testcase11.txt AC 10 ms
9,812 KB
testcase12.txt AC 3 ms
1,548 KB
testcase13.txt AC 4 ms
1,552 KB
testcase14.txt AC 3 ms
1,548 KB
testcase15.txt AC 4 ms
1,556 KB
testcase16.txt AC 3 ms
1,552 KB
testcase17.txt AC 4 ms
1,556 KB
testcase18.txt AC 3 ms
1,552 KB
testcase19.txt AC 4 ms
1,556 KB
testcase20.txt AC 2 ms
1,556 KB
テストケース一括ダウンロード

ソースコード

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