Submission #98972

---

Source Code Expand

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>

using namespace std;

typedef long long LL;

const int MOD = 1000000007;

// x^n = x^(n-1) + ... x + 1
vector<LL>mulPoly(const vector<LL>&x, const vector<LL>&y) {
    int n=x.size();
    vector<LL>z(2*n);
    for (int i=0; i<n; i++) {
	for (int j=0; j<n; j++) {
	    z[i+j] = (z[i+j]+x[i]*y[j]) % MOD;
	}
    }
    for (int i=2*n-1; i>=n; i--) {
	for (int j=1; j<=n; j++) {
	    z[i-j] = (z[i-j]+z[i]) % MOD;
	}
    }
    z.resize(n);
    return z;
}
vector<LL>powPoly(vector<LL> x, LL y) {
    int n=x.size();
    vector<LL>r(n);
    r[0]=1;
    for (int i=0; (1LL<<i)<=y; i++) {
	if (y&(1LL<<i)) r = mulPoly(r, x);
	x = mulPoly(x, x);
    }
    return r;
}

int K, N;


int main() {
    scanf("%d %d", &K, &N);
    //K=1000; N=1000000000;
    
    if (N<=K) puts("1");
    else {
	vector<LL>x(K), r;
	x[1]=1;
	r = powPoly(x, N-1);
	LL ans=0;
	for (int i=0; i<K; i++) ans = (ans+r[i])%MOD;
	cout << ans << endl;
    }

    return 0;
}

Submission Info

Compile Error

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

Judge Result