Submission #2382438
Source Code Expand
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef long long int int64;
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))
const int mod=1000000007;
int *tmp;
void mul(int *c,int *a,int *b,int k){
int 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]+(int64)a[i]*b[j])%mod;
}
}
for(i=2*k-2;i>=k;i--){
for(j=1;j<=k;j++){
int s=tmp[i-j]+tmp[i];
tmp[i-j]=s>=mod?s-mod:s;
}
}
for(i=0;i<k;i++) c[i]=tmp[i];
return;
}
int calc(int n,int k){
if(n<k) return 1;
int *t=(int *)calloc(k,sizeof(int));
int *s=(int *)calloc(k,sizeof(int));
tmp=(int *)calloc(2*k-1,sizeof(int));
s[1]=1;
t[0]=1;
while(n>0){
if(n&0x01) mul(t,t,s,k);
mul(s,s,s,k);
n>>=1;
}
int res=0;
int i;
for(i=0;i<k;i++) res=(res+t[i])%mod;
free(t);
free(s);
free(tmp);
return res;
}
void run(void){
int k,n;
scanf("%d%d",&k,&n);
int ans=calc(n-1,k);
printf("%d\n",ans);
return;
}
int main(void){
run();
return 0;
}
Submission Info
Submission Time
2018-04-20 17:32:29+0900
Task
T - フィボナッチ
User
sansen
Language
C (GCC 5.4.1)
Score
8
Code Size
1151 Byte
Status
AC
Exec Time
148 ms
Memory
128 KB
Compile Error
./Main.c: In function ‘run’:
./Main.c:55: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
148 ms
128 KB
01
AC
76 ms
128 KB
02
AC
133 ms
128 KB
03
AC
22 ms
128 KB
04
AC
1 ms
128 KB
90
AC
1 ms
128 KB
91
AC
1 ms
128 KB