CSES - Dice Combinations | Kết hợp xúc xắc

View as PDF
Authors:
Flower_On_Stone, kitsune, Namlenam
Problem type
Points: 1100 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

Your task is to count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.

For example, if n=3, there are 4 ways:

  • 1+1+1
  • 1+2
  • 2+1
  • 3

Input

  • The only input line has an integer n.

Output

  • Print the number of ways modulo 10^9+7.

Constraints

  • 1 \le n \le 10^6

Example

Sample input

3

Sample output

4

Comments


  • -1
    tk22NguyenHongPhuc,  6:22 p.m. 20 nov, 2023

    include <bits/stdc++.h>

    using namespace std;
    typedef long long ll;
    typedef long double ld;
    const ll MOD = 1e9 + 7;

    int main(){
    int n;
    cin >> n;

    vector<int> dp(n + 1);

dp[0] = 1;
for (int i = 1; i <= n; i++)
    for (int j = max(0, i - 6); j < i; j++)
        dp[i] = (dp[i] + dp[j]) % MOD;

cout << dp[n] << endl;

    }

      • 1 more comment