結果
問題 | No.2709 1975 Powers |
ユーザー | ななな |
提出日時 | 2024-03-31 14:33:57 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 2,225 bytes |
コンパイル時間 | 1,494 ms |
コンパイル使用メモリ | 177,776 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-09-30 19:41:15 |
合計ジャッジ時間 | 2,594 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 4 ms
6,820 KB |
testcase_03 | AC | 19 ms
6,820 KB |
testcase_04 | AC | 30 ms
6,816 KB |
testcase_05 | AC | 21 ms
6,816 KB |
testcase_06 | AC | 9 ms
6,816 KB |
testcase_07 | AC | 3 ms
6,820 KB |
testcase_08 | AC | 12 ms
6,820 KB |
testcase_09 | AC | 24 ms
6,816 KB |
testcase_10 | AC | 3 ms
6,816 KB |
testcase_11 | AC | 3 ms
6,820 KB |
testcase_12 | AC | 6 ms
6,816 KB |
testcase_13 | AC | 25 ms
6,820 KB |
testcase_14 | AC | 7 ms
6,816 KB |
testcase_15 | AC | 8 ms
6,816 KB |
testcase_16 | AC | 18 ms
6,820 KB |
testcase_17 | AC | 2 ms
6,816 KB |
testcase_18 | AC | 7 ms
6,820 KB |
testcase_19 | AC | 31 ms
6,820 KB |
testcase_20 | AC | 4 ms
6,816 KB |
testcase_21 | AC | 11 ms
6,816 KB |
testcase_22 | AC | 30 ms
6,816 KB |
testcase_23 | AC | 36 ms
6,820 KB |
testcase_24 | AC | 33 ms
6,824 KB |
testcase_25 | AC | 33 ms
6,816 KB |
testcase_26 | AC | 29 ms
6,820 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; #define int long long #define rep(i, n) for (int i = 0; i < n; i++) long long modpow(long long n, long long k, long long mod) { long long res = 1; while (k) { if (k & 1) { res = (res * n) % mod; } n = (n * n) % mod; k >>= 1; } return res; } // x以上の一番左側のイテレーターを返す // sortを忘れずに // x以上ものがなかったら1e9を返す int ijyou(const vector<int> &a, int x, int k, int k1) { int le = k; int ri = k1; if (a[k] >= x) return k; if (a[k1] < x) return 1e9; while (ri - le > 1) { int mid = (le + ri) / 2; if (x > a[mid]) { le = mid; } else { ri = mid; } } return ri; } // x以下の一番右側のイテレーターを返す // sortを忘れずに // x以下のものがなかったら1e9を返す int ika(const vector<int> &a, int x, int k, int k1) { if (a[k1] <= x) return k1; if (a[k] > x) return 1e9; int le = k; int ri = k1; while (ri - le > 1) { int mid = (le + ri) / 2; if (x >= a[mid]) le = mid; else ri = mid; } return ri - 1; } int yoriue(const vector<int> &a, int x, int k, int k1) { return ijyou(a, x + 1, k, k1); } int yorisita(const vector<int> &a, int x, int k, int k1) { return ika(a, x - 1, k, k1); } signed main() { int n, p, q; cin >> n >> p >> q; vector<int> a(n); rep(i, n) cin >> a[i]; sort(a.begin(), a.end()); vector<int> mo10(n); vector<int> mo9(n); vector<int> mo7(n); vector<int> mo5(n); vector<vector<int>> g(p); rep(i, n) { mo10[i] = modpow(10, a[i], p); mo9[i] = modpow(9, a[i], p); mo7[i] = modpow(7, a[i], p); mo5[i] = modpow(5, a[i], p); g[mo5[i]].push_back(i); } int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int t = j + 1; t < n; t++) { int k = mo10[i] + mo9[j] + mo7[t]; k %= p; int h = q - k; h += p; h %= p; if (g[h].size() == 0) continue; int e = yoriue(g[h], t, 0, g[h].size() - 1); if (e == 1e9) continue; ans += (g[h].size() - e); } } } cout << ans << endl; }