【題解】CSES - Dice Combinations

題目連結

題目大意

給定 $n$，問丟多次骰子使得點數總和為 $n$ 的方法數量 $\bmod{10^9 + 7}$。

• $1 \leq n \leq 10^6$

題解

定義 $dp[i]$ 為點數和為 $i$ 點的方法數量。因為骰子的點數為 $1 \sim 6$，$i$ 點可以由 $i - 1$ 點後骰到 $1$、$i - 2$ 點後骰到 $2$、$\dots$、$i - 6$ 點後骰到 $6$，因此湊出 $i$ 點的方法數就是這些的總和，得到 $dp[i] = \sum\limits_{j = 1}^6 dp[i - j]$。最後所求就是 $dp[n]$。其他實作細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1E9 + 7;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> dp(n + 1);
	dp[0] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= 6; j++) {
			if(i - j >= 0) {
				dp[i] = (dp[i] + dp[i - j]) % MOD;
			}
		}
	}
	cout << dp[n] << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】CSES - Dice Combinations