結果
問題 |
No.2709 1975 Powers
|
ユーザー |
![]() |
提出日時 | 2024-03-31 15:30:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 487 ms / 2,000 ms |
コード長 | 1,481 bytes |
コンパイル時間 | 1,945 ms |
コンパイル使用メモリ | 204,548 KB |
最終ジャッジ日時 | 2025-02-20 17:57:14 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#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; }