Submission #1331003

---

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--){
        if(dp[b][i]) 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

Judge Result