Submission #101659
Source Code Expand
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<string.h>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<map>
#include<set>
#include<bitset>
#include<iostream>
#include<sstream>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define drep(i,n) for(int i = n-1; i >= 0; i--)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y);
#define mins(x,y) x = min(x,y);
#define pb push_back
#define snuke srand((unsigned)clock()+(unsigned)time(NULL))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<ll> vi;
const int MX = 100005, INF = 1000000000, mod = 1000000007;
const ll LINF = 1000000000000000000ll;
const double eps = 1e-9;
const int dx[4] = {-1,0,1,0}, dy[4] = {0,-1,0,1}; //<^>v
vi v0;
int k, n;
ll d[2005];
// x^n mod x^k-xx^(k-1)-...x^1-x^0
vi f(int a){
if(a == 0) return v0;
vi x = f(a/2);
rep(i,k*2) d[i] = 0;
rep(i,k)rep(j,k) d[i+j+(a&1)] = (d[i+j+(a&1)]+x[i]*x[j])%mod;
for(int i = k*2-1; i >= k; i--) rep(j,k) d[i-k+j] = (d[i-k+j]+d[i])%mod;
rep(i,k) x[i] = d[i];
return x;
}
int main(){
cin >> k >> n;
v0 = vi(k,0); v0[0] = 1;
vi x = f(n-1);
int ans = 0;
rep(i,k) ans = (ans+x[i])%mod;
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
T - フィボナッチ |
User |
snuke |
Language |
C++ (G++ 4.6.4) |
Score |
8 |
Code Size |
1509 Byte |
Status |
AC |
Exec Time |
265 ms |
Memory |
924 KB |
Judge Result
Set Name |
All |
Score / Max Score |
8 / 8 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 03, 04, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
AC |
265 ms |
924 KB |
01 |
AC |
158 ms |
808 KB |
02 |
AC |
260 ms |
920 KB |
03 |
AC |
58 ms |
920 KB |
04 |
AC |
94 ms |
912 KB |
90 |
AC |
22 ms |
920 KB |
91 |
AC |
22 ms |
872 KB |