結果
問題 | No.695 square1001 and Permutation 4 |
ユーザー | veqcc |
提出日時 | 2019-09-01 17:44:24 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,664 ms / 7,000 ms |
コード長 | 2,054 bytes |
コンパイル時間 | 1,328 ms |
コンパイル使用メモリ | 109,716 KB |
実行使用メモリ | 42,332 KB |
最終ジャッジ日時 | 2024-07-22 19:37:37 |
合計ジャッジ時間 | 11,757 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
42,128 KB |
testcase_01 | AC | 110 ms
42,152 KB |
testcase_02 | AC | 117 ms
42,108 KB |
testcase_03 | AC | 118 ms
42,332 KB |
testcase_04 | AC | 437 ms
42,272 KB |
testcase_05 | AC | 437 ms
42,136 KB |
testcase_06 | AC | 958 ms
42,128 KB |
testcase_07 | AC | 851 ms
42,152 KB |
testcase_08 | AC | 653 ms
42,040 KB |
testcase_09 | AC | 895 ms
42,164 KB |
testcase_10 | AC | 220 ms
42,204 KB |
testcase_11 | AC | 1,591 ms
42,124 KB |
testcase_12 | AC | 1,273 ms
42,204 KB |
testcase_13 | AC | 1,664 ms
42,248 KB |
ソースコード
#include <functional> #include <algorithm> #include <iostream> #include <iomanip> #include <cstring> #include <string> #include <vector> #include <random> #include <bitset> #include <queue> #include <cmath> #include <stack> #include <set> #include <map> typedef long long ll; using namespace std; typedef pair <ll, ll> P; ll mod(ll a, ll m) { return (a % m + m) % m; } // 拡張Euclidの互除法 // ap + bq = gcd(a, b) となるp,qを求め、return d = gcd(a,b) ll extGcd(ll a, ll b, ll &p, ll &q) { ll d = a; if (b == 0) { p = 1; q = 0; } else { d = extGcd(b, a % b, q, p); q -= (a / b) * p; } return d; } // Chinese Remainder Theorem // 解あり -> x = r mod m なら return (r, m) // 解なし -> return (-1, -1) P CRT(vector <ll> &b, vector <ll> &m) { ll r = 0, M = 1; for (int i = 0; i < b.size(); i++) { ll p, q; ll d = extGcd(M, m[i], p, q); if ((b[i] - r) % d != 0) return {-1, -1}; ll tmp = (b[i] - r) / d * p % (m[i] / d); // s = (b1 - b2) / d r += M * tmp; // x = r + s * M * p の形 M *= m[i] / d; // mod を lcm に更新 } return {mod(r, M), M}; } int main() { cin.sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector <int> x(m); for (int i = 0; i < m; i++) cin >> x[i]; vector <ll> MOD = {168647939, 592951213}; vector <ll> b(2, 0); for (int i = 0; i < 2; i++) { vector <int> dp(10000005); dp[0] = 1; for (int j = 1; j <= n / 2; j++) { for (auto v : x) { if (j - v >= 0) { (dp[j] += dp[j - v]) %= MOD[i]; } } } for (int j = 0; j <= n / 2; j++) { for (auto v : x) { if (j + v > n / 2 && j + v <= n - 1) { (b[i] += (ll)dp[j] * (ll)dp[n - 1 - j - v]) %= MOD[i]; } } } } P p = CRT(b, MOD); cout << p.first << "\n"; return 0; }