結果
問題 | No.2709 1975 Powers |
ユーザー | Tatsu_mr |
提出日時 | 2024-03-31 15:30:12 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 484 ms / 2,000 ms |
コード長 | 1,481 bytes |
コンパイル時間 | 2,154 ms |
コンパイル使用メモリ | 211,488 KB |
実行使用メモリ | 348,152 KB |
最終ジャッジ日時 | 2024-03-31 15:30:40 |
合計ジャッジ時間 | 11,873 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 162 ms
81,480 KB |
testcase_01 | AC | 164 ms
81,480 KB |
testcase_02 | AC | 234 ms
148,216 KB |
testcase_03 | AC | 312 ms
204,536 KB |
testcase_04 | AC | 456 ms
303,992 KB |
testcase_05 | AC | 401 ms
254,840 KB |
testcase_06 | AC | 232 ms
125,176 KB |
testcase_07 | AC | 180 ms
90,228 KB |
testcase_08 | AC | 337 ms
243,064 KB |
testcase_09 | AC | 429 ms
275,064 KB |
testcase_10 | AC | 183 ms
91,892 KB |
testcase_11 | AC | 198 ms
105,080 KB |
testcase_12 | AC | 292 ms
207,224 KB |
testcase_13 | AC | 484 ms
321,656 KB |
testcase_14 | AC | 241 ms
142,840 KB |
testcase_15 | AC | 325 ms
234,872 KB |
testcase_16 | AC | 309 ms
173,304 KB |
testcase_17 | AC | 201 ms
95,480 KB |
testcase_18 | AC | 325 ms
213,496 KB |
testcase_19 | AC | 440 ms
277,496 KB |
testcase_20 | AC | 231 ms
141,944 KB |
testcase_21 | AC | 367 ms
241,528 KB |
testcase_22 | AC | 476 ms
348,152 KB |
testcase_23 | AC | 466 ms
290,424 KB |
testcase_24 | AC | 378 ms
196,088 KB |
testcase_25 | AC | 468 ms
282,360 KB |
testcase_26 | AC | 455 ms
308,216 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<long long> v = {10LL, 9LL, 7LL, 5LL}; int siz = 2000010; int main() { int n; long long p, q; cin >> n >> p >> q; vector<long long> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<vector<long long>> mods(4, vector<long long>(siz, 1LL)); for (int i = 0; i < 4; i++) { for (int j = 1; j < siz; j++) { mods[i][j] = mods[i][j - 1] * v[i] % p; } } sort(a.begin(), a.end()); vector<vector<long long>> ans1(n, vector<long long>(p)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { if (i < j && j < k) { long long res = ((mods[0][a[i]] + mods[1][a[j]]) % p + mods[2][a[k]]) % p; ans1[k][res]++; } } } } vector<vector<long long>> ans2(n, vector<long long>(p)); for (int i = 0; i < n; i++) { ans2[i][mods[3][a[i]]]++; } for (int i = n - 2; i >= 0; i--) { for (int j = 0; j < p; j++) { ans2[i][j] += ans2[i + 1][j]; } } long long ans = 0LL; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < p; j++) { int i2 = i + 1; int j2 = q - j; if (j2 < 0) { j2 += p; } ans += ans1[i][j] * ans2[i2][j2]; } } cout << ans << endl; }