結果

問題 No.978 Fibonacci Convolution Easy
ユーザー tamaron
提出日時 2020-05-11 22:46:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 3,996 bytes
コンパイル時間 1,476 ms
コンパイル使用メモリ 172,040 KB
実行使用メモリ 50,148 KB
最終ジャッジ日時 2024-07-19 07:28:18
合計ジャッジ時間 2,897 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1 << 27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void yn(bool j){cout << (j ? "Yes" : "No") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> long long bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

struct mint {
long long x;
    mint(long long x = 0):x((x % MOD + MOD) % MOD){}
    mint& operator += (const mint a) {if ((x += a.x) >= MOD) x -= MOD; return *this;}
    mint& operator -= (const mint a) {if ((x += MOD-a.x) >= MOD) x -= MOD; return *this;}
    mint& operator *= (const mint a) {(x *= a.x) %= MOD; return *this;}
    mint operator + (const mint a) const {mint res(*this); return res += a;}
    mint operator - (const mint a) const {mint res(*this); return res -= a;}
    mint operator * (const mint a) const {mint res(*this); return res *= a;}
    mint pow(long long t) const {if (!t) return 1; mint a = pow(t >> 1); a *= a; if (t&1) a *= *this; return a;}
    mint inv() const {return pow(MOD - 2);}
    mint& operator /= (const mint a) {return (*this) *= a.inv();}
    mint operator / (const mint a) const {mint res(*this); return res /= a;}
};

class combination {
    public:
    vector<mint> fact, ifact;
    combination(int n):fact(n + 1), ifact(n + 1) {
        assert(n < MOD);
        fact[0] = 1;
        for(int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for(int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (COMBMAX < n){
            mint ret = 1;
            for(long long i = 1; i <= k; i++){
                ret *= (n - i + 1);
                ret /= i;
            }
            return ret;
        }
        return fact[n] * ifact[k] * ifact[n - k];
    }

    mint multi(long long n, long long sum, long long l, long long r){
        long long m = r - l + 1;
        long long t = sum - n * (l - 1);
        mint ans = 0;
        for(long long k = 0; k <= (t - n) / m; k++){
            long long sign = k % 2 == 0 ? 1 : -1;
            mint temp = this->operator() (n, k);
            temp *= this->operator() (n + (t - n - m * k - 1), t - n - m * k);
            temp *= sign;
            ans += temp;
        }
        return ans;
    }
} com(COMBMAX);


int main(){
    ll N, p; cin >> N >> p;
    vector<mint> a(N), ac(N + 1);
    a[0] = 0;
    a[1] = 1;
    for(ll i = 2; i < N; i++){
        a[i] = p; 
        a[i] *= a[i - 1];
        a[i] += a[i - 2];
    }
    rep(i, N){
        ac[i + 1] = ac[i] + a[i];
    }
    // rep(i, N + 1) pt(ac[i].x); 
    mint ans = 0;
    rep(i, N){
        mint temp = a[i];
        temp *= (ac[N] - ac[i]);
        ans += temp;
    }
    pt(ans.x);
}
0