Submission #2448275

---

Source Code Expand

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef unsigned long long int ull;
typedef unsigned int ui;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

const ui mod=1000000007;

ui *tmp;
void mul(ui *c,ui *a,ui *b,const ui k){
  ui i,j;
  for(i=0;i<2*k-1;i++) tmp[i]=0;
  for(i=0;i<k;i++){
    for(j=0;j<k;j++){
      tmp[i+j]=(tmp[i+j]+(ull)a[i]*b[j])%mod;
    }
  }
  for(i=2*k-2;i>=k;i--){
    for(j=1;j<=k;j++){
      tmp[i-j]=(tmp[i-j]+tmp[i])%mod;
    }
  }
  for(i=0;i<k;i++) c[i]=tmp[i];
  return;
}

ui calc(ui n,ui k){
  if(n<k) return 1;
  ui *t=(ui *)calloc(k,sizeof(ui));
  ui *s=(ui *)calloc(k,sizeof(ui));
  tmp=(ui *)calloc(2*k-1,sizeof(ui));
  s[1]=1;
  t[0]=1;
  while(n>0){
    if(n&0x01) mul(t,t,s,k);
    mul(s,s,s,k);
    n>>=1;
  }
  ui res=0;
  ui i;
  for(i=0;i<k;i++) res=(res+t[i])%mod;
  free(t);
  free(s);
  free(tmp);
  return res;
}

void run(void){
  ui k,n;
  scanf("%d%d",&k,&n);
  ui ans=calc(n-1,k);
  printf("%d\n",ans);
  return;
}

int main(void){
  run();
  return 0;
}

Submission Info

Judge Result