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

5721 ワード
バックアップアルゴリズム テキストリンク

リンク


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;
}

    ふくガス

  • 資料型の範囲に注意してください.
  • 脳コードを除去する
    • カラーコーディングテーブル
    [CS]CSSベースDay-6