白駿アルゴリズム15988号:1、2、3プラス3

リンク

https://www.acmicpc.net/problem/15988

質問する

整数4を1、2、3の和と表す方法は全部で7種類ある.和を表すときは1つ以上の数を使います.

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1
整数nが与えられると、nが1、2、3の和で表される方法の数を求めるプログラムが作成される.

入力

第1行は、試験例の個数Tを与える.各試験例は1行からなり、整数nが与えられる.nは正数であり、1000000以下である.

しゅつりょく

各試験例について、nを1、2、3の和として表す方法数を1000000009で割った後、残りを出力する.

入力と出力の例

プールコード

// 1,2,3 더하기 3
#include <stdio.h>
#define size 1000001

const long long mod = 1000000009;


long long dp[size];

int main(){
  long long n,test;
  scanf("%lld",&test);
  dp[0] = 0;
  dp[1] = 1;
  dp[2] = 2;
  dp[3] = 4;
  for(int i = 4; i < size; i++){
    dp[i] = (dp[i -1] + dp[i - 2] + dp[i -3]) % mod;
  }
  for(int i = 0; i < test; i++){
    scanf("%lld",&n);
    printf("%lld\n",dp[n]);
  }
  return 0;
}

ふくガス

資料型の範囲に注意してください.

脳コードを除去する