1
#include <stdio.h>
int memo[10001]={};
int f(int n){
if(memo[n]!=0) return memo[n];
if(n <= 1)
return 1;
if(n == 2)
return 2;
return memo[n] = (f(n - 2) + f(n - 1)) % 100000007;
}
int main(){
int n;
scanf("%d",&n);
printf("%d",f(n));
}
2
#include <stdio.h>
int f(int n){
if(n == 1)
return 2;
return (2 * f(n - 1)) % 100000007;
}
int main(){
int n;
scanf("%d",&n);
if(n % 3 != 0)
printf("0");
else{
printf("%d",f(n / 3));
}
return 0;
}
3
#include <stdio.h>
int memo[10000] = {};
int f(int n){
if(memo[n]!=0) return memo[n];
if(n <= 1) return 1;
if(n <= 2) return 3;
return memo[n] = (f(n - 2) * 2 + f(n - 1)) % 100007;
}
int main(){
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
4
#include <stdio.h>
int memo[10000] = {};
int f(int n){
if(memo[n]!=0) return memo[n];
if(n <= 1) return 1;
if(n == 2) return 5;
if(n == 3)return 11;
return memo[n] = (f(n - 2) * 4 + f(n-1) + f(n-3) * 2) % 100007;
}
int main(){
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
5
#include <stdio.h>
int memo[10001] = {1,1,2,6};
int f(int n)
{
if(memo[n] != 0) return memo[n];
return memo[n] = (f(n - 1) + f(n - 2) + f(n - 3) * 3) % 1000;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
6
#include <stdio.h>
int memo[10001] = {1,2,7,22};
int f(int n)
{
if(memo[n] != 0) return memo[n];
int sum = f(n - 1) * 2 + f(n - 2) * 3;
for(int i = 3 ; i < n ; i++){
sum += f(n - i) * 2;
}
return memo[n] = (sum + 2) % 100007;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
7
#include <stdio.h>
int memo[10001] = {0,0,3,0,11};
int f(int n)
{
if(memo[n] != 0) return memo[n];
int sum = f(n - 2) * 3;
for(int i = 4 ; i < n ; i += 2){
sum += f(n - i) * 2;
}
return memo[n] = (sum + 2) % 100007;
}
int main()
{
int n;
scanf("%d",&n);
if(n % 2 == 0)
printf("%d",f(n));
else
printf("0");
}
8
#include <stdio.h>
int memo[10001] = {0,1,5};
int f(int n)
{
if(memo[n] != 0) return memo[n];
int sum = f(n - 1) + f(n - 2) * 4;
for(int i = 3 ; i < n ; i++){
sum += f(n - i) * 2;
}
for(int i = 4 ; i < n ; i += 2){
sum += f(n - i);
}
if(n % 2 == 0)
return memo[n] = (sum + 3) % 100007;
return memo[n] = (sum + 2) % 100007;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}