Submission #98359

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef vector<ll> Poly;

const int MOD = 1000000007;

Poly polyPower(const Poly& a, ll n) {
    int m = (int)a.size() - 1;
    Poly p(m + 1);
    p[0] = 1;
    for (int b = sizeof(ll) * 8 - __builtin_clzll(n) - 1; b >= 0; --b) {
        Poly q(2 * m, 0);
        int d = n >> b & 1;
        ll pm = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < m; ++j) {
                q[i + j + d] = (q[i + j + d] + p[i] * p[j]) % MOD;
            }
            pm += p[i];
        }
        pm = pm % MOD * p[m] % MOD;
        for (int i = 2 * m - 1; i >= m; --i) {
            for (int j = 0; j < m; ++j) {
                q[i - m + j] = (q[i - m + j] + q[i] * a[j]) % MOD;
            }
            pm = (pm + q[i] * a[m]) % MOD;
        }
        for (int i = 0; i < m; ++i) {
            p[i] = q[i];
        }
        p[m] = pm;
    }
    return p;
}

int main() {
    int K, N;
    scanf("%d%d", &K, &N);

    Poly a(K, 1);
    a.push_back(0);
    Poly ret = polyPower(a, N - 1);
    printf("%lld\n", accumulate(ret.begin(), ret.end(), 0LL) % MOD);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:43:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result