結果
問題 |
No.2709 1975 Powers
|
ユーザー |
|
提出日時 | 2024-11-01 21:42:45 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 504 ms / 2,000 ms |
コード長 | 1,572 bytes |
コンパイル時間 | 4,142 ms |
コンパイル使用メモリ | 290,332 KB |
実行使用メモリ | 146,304 KB |
最終ジャッジ日時 | 2024-11-01 21:42:57 |
合計ジャッジ時間 | 10,990 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long P; map<pair<long long, long long>, long long> memo; long long modpow(long long base, long long exp, long long modulus) { base %= modulus; long long result = 1; while (exp > 0) { if (exp & 1) result = (result * base) % modulus; base = (base * base) % modulus; exp >>= 1; } return result; } long long calc(long long x, long long y) { pair<long long, long long> key = {x, y}; if (memo.count(key)) return memo[key]; return memo[key] = modpow(x, y, P); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long N, Q; cin >> N >> P >> Q; vector<long long> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } sort(A.begin(), A.end()); vector<vector<long long>> modP(N + 1, vector<long long>(P, 0)); for (int i = 0; i < N; i++) { for (int p = 0; p < P; p++) { modP[i + 1][p] = modP[i][p]; } int val = modpow(5, A[i], P); modP[i + 1][val]++; } long long ans = 0; for (int i = 0; i < N - 3; i++) { for (int j = i + 1; j < N - 2; j++) { for (int k = j + 1; k < N - 1; k++) { long long a = A[i], b = A[j], c = A[k]; long long cnt = (calc(10, a) + calc(9, b) + calc(7, c)) % P; long long tmp = (Q - cnt + P) % P; ans += modP[N][tmp] - modP[k + 1][tmp]; } } } cout << ans << endl; return 0; }