Submission #1134509
Source Code Expand
#include <stdio.h> #include <string.h> typedef long long int ll; const int mod = 1000000007; int dp[2][1000]; int tmp[1001]; int *const p = tmp+1; void next(int *x, int k){ int i; int z = x[k-1]; for(i=k-1; i>0; i--){ x[i] = z + x[i-1]; if(x[i] >= mod) x[i] -= mod; } x[0] = z; } int solve(int n, int k){ int i,j,b; ll ans; int t = 1<<(31-__builtin_clz(n)); dp[0][1] = 1; b = 0; for(t = t >> 1; t; t >>= 1){ memcpy(p, dp[b], sizeof(dp[0])); for(i=0;i<k;i++){ int z = p[k-1]; for(j=k-1;j>=0;j--){ dp[b^1][j] = (dp[b^1][j] + (ll) dp[b][i] * p[j]) % mod; p[j] = z + p[j-1]; if(p[j] >= mod) p[j] -= mod; } dp[b][i] = 0; } if(n&t) next(dp[b^1], k); b ^= 1; } ans = 0; for(i=0;i<k;i++) ans += dp[b][i]; return ans % mod; } int main(){ int n, k; scanf("%d%d", &k, &n); if(n<=k){ puts("1"); return 0; } printf("%d\n", solve(n-1, k)); return 0; }
Submission Info
Submission Time | |
---|---|
Task | T - フィボナッチ |
User | ryuhei |
Language | C (GCC 5.4.1) |
Score | 8 |
Code Size | 1034 Byte |
Status | AC |
Exec Time | 118 ms |
Memory | 128 KB |
Compile Error
./Main.c: In function ‘main’: ./Main.c:52:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &k, &n); ^
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 | 118 ms | 128 KB |
01 | AC | 65 ms | 128 KB |
02 | AC | 118 ms | 128 KB |
03 | AC | 19 ms | 128 KB |
04 | AC | 1 ms | 128 KB |
90 | AC | 1 ms | 128 KB |
91 | AC | 1 ms | 128 KB |