結果
問題 |
No.695 square1001 and Permutation 4
|
ユーザー |
|
提出日時 | 2018-09-15 15:02:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,660 ms / 7,000 ms |
コード長 | 1,522 bytes |
コンパイル時間 | 1,970 ms |
コンパイル使用メモリ | 197,920 KB |
最終ジャッジ日時 | 2025-01-06 13:25:06 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using ll = long long; constexpr ll MOD1 = 168647939; constexpr ll MOD2 = 592951213; template <typename T> constexpr std::pair<T, T> extgcd(const T a, const T b) { if (b == 0) { return std::pair<T, T>{1, 0}; } const auto p = extgcd(b, a % b); return {p.second, p.first - p.second * (a / b)}; } template <typename T> std::pair<T, T> ChineseRemainderTheorem(const std::pair<T, T>& a1, const std::pair<T, T>& a2) // (mod, value) { const T p1 = a1.first, m1 = a1.second, p2 = a2.first, m2 = a2.second, m = p1 * p2; if (m1 == m2) { return {p1 * p2, m1}; } auto p = extgcd(p1, p2); return {m, (((p1 * p.first * (m2 - m1) + m1) % m) + m) % m}; } int main() { int N, M; std::cin >> N >> M; std::vector<int> x(M); for (int i = 0; i < M; i++) { std::cin >> x[i]; } const int H = (N + 1) / 2; auto solve = [&](const ll mod) { std::vector<int> dp(H, 0); dp[0] = 1; for (int i = 1; i < H; i++) { for (int j = 0; j < M; j++) { if (i >= x[j]) { (dp[i] += dp[i - x[j]]) %= mod; } } } ll ans = 0; for (int j = 0; j < M; j++) { for (int i = std::max(0, x[j] - H); i < std::min(N - H, x[j]); i++) { (ans += (ll)dp[H - x[j] + i] * dp[N - H - i - 1] % mod) %= mod; } } return ans; }; const auto ans = ChineseRemainderTheorem<__int128_t>({MOD1, solve(MOD1)}, {MOD2, solve(MOD2)}); std::cout << (ll)ans.second << std::endl; return 0; }