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

View as PDF

Points: 1100 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

Nhiệm vụ của bạn là đếm số cách tạo ra tổng \(n\) bằng cách gieo xúc xắc một hoặc nhiều lần. Mỗi lần gieo cho ra số từ \(1\) đến \(6\).

VÍ dụ, nếu \(n = 3\), có \(4\) cách:

  • \(1 + 1 + 1\)
  • \(1 + 2\)
  • \(2 + 1\)
  • \(3\)

Input

  • Dòng đầu vào duy nhất có số nguyên \(n\).

Output

  • In số cách chia lấy dư cho \(10^9 + 7\).

Constraints

  • \(1 \leq n \leq 10^6\)

Example

Sample input

3

Sample output
4


Comments


  • 0
    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;
    

    }


    • 0
      dtai08    10:18 p.m. 12 jun, 2024

      bạn giải thích cách hoạt động được không ạ, mình cảm ơn.

      4 more comments