dice_combinations_1633.cpp (400B)
1 #include <algorithm> 2 #include <array> 3 #include <iostream> 4 5 // We use a funny memory optimization: we only store the last 7 values. 6 7 int main() { 8 constexpr unsigned mod = 1e9+7; 9 int n; 10 std::cin >> n; 11 std::array<int, 7> v{0}; 12 v[0] = 1; 13 for (int i = 1; i <= n; i++) { 14 v[i%7] = 0; 15 for (int j = std::max(0, i-6); j < i; j++) 16 v[i%7] = (v[i%7]+v[j%7]) % mod; 17 } 18 std::cout << v[n%7] << "\n"; 19 }