Submission #1165637


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;

__attribute__((target("arch=sandybridge")))
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;
}

__attribute__((target("arch=sandybridge")))
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;
}

__attribute__((target("arch=sandybridge")))
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 (Clang 3.8.0)
Score 8
Code Size 1169 Byte
Status AC
Exec Time 81 ms
Memory 128 KB

Judge Result

Set Name All
Score / Max Score 8 / 8
Status
AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 81 ms 128 KB
01 AC 46 ms 128 KB
02 AC 81 ms 128 KB
03 AC 13 ms 128 KB
04 AC 1 ms 128 KB
90 AC 1 ms 128 KB
91 AC 1 ms 128 KB