結果
問題 | No.2709 1975 Powers |
ユーザー | wanui |
提出日時 | 2024-03-31 15:22:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 258 ms / 2,000 ms |
コード長 | 1,851 bytes |
コンパイル時間 | 2,708 ms |
コンパイル使用メモリ | 219,440 KB |
実行使用メモリ | 141,768 KB |
最終ジャッジ日時 | 2024-03-31 15:22:56 |
合計ジャッジ時間 | 8,307 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 106 ms
65,860 KB |
testcase_01 | AC | 105 ms
65,860 KB |
testcase_02 | AC | 113 ms
68,040 KB |
testcase_03 | AC | 157 ms
91,592 KB |
testcase_04 | AC | 241 ms
133,960 KB |
testcase_05 | AC | 162 ms
92,744 KB |
testcase_06 | AC | 153 ms
87,752 KB |
testcase_07 | AC | 107 ms
65,988 KB |
testcase_08 | AC | 151 ms
87,112 KB |
testcase_09 | AC | 190 ms
107,720 KB |
testcase_10 | AC | 105 ms
65,988 KB |
testcase_11 | AC | 116 ms
69,448 KB |
testcase_12 | AC | 123 ms
74,056 KB |
testcase_13 | AC | 250 ms
121,800 KB |
testcase_14 | AC | 127 ms
76,488 KB |
testcase_15 | AC | 124 ms
74,568 KB |
testcase_16 | AC | 181 ms
105,032 KB |
testcase_17 | AC | 107 ms
66,372 KB |
testcase_18 | AC | 126 ms
75,720 KB |
testcase_19 | AC | 241 ms
134,600 KB |
testcase_20 | AC | 109 ms
67,400 KB |
testcase_21 | AC | 148 ms
86,600 KB |
testcase_22 | AC | 236 ms
138,952 KB |
testcase_23 | AC | 257 ms
141,768 KB |
testcase_24 | AC | 255 ms
140,744 KB |
testcase_25 | AC | 254 ms
138,696 KB |
testcase_26 | AC | 258 ms
127,176 KB |
ソースコード
#include <bits/stdc++.h> // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18; void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);} void print1(){print0("\n");}; template<typename H,typename... T>void print1(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print1(t...);} void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); } #define debug1(a) { cerr<<#a<<":"<<a<<endl; } #define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; } #define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; } #define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; } // clang-format on int main() { ioinit(); ll N, P, Q; cin >> N >> P >> Q; vector<ll> pow10(2000001, 1); vector<ll> pow9(2000001, 1); vector<ll> pow7(2000001, 1); vector<ll> pow5(2000001, 1); for (ll i = 1; i <= 2000000; i++) { pow10[i] = pow10[i - 1] * 10 % P; pow9[i] = pow9[i - 1] * 9 % P; pow7[i] = pow7[i - 1] * 7 % P; pow5[i] = pow5[i - 1] * 5 % P; } vector<ll> A(N); for (ll i = 0; i < N; i++) { cin >> A[i]; } sort(A.begin(), A.end()); vector<map<ll, ll>> mp(N); map<ll, ll> cnt; for (ll c = N - 1; c >= 0; c--) { for (ll d = c + 1; d < N; d++) { ll m = (pow7[A[c]] + pow5[A[d]]) % P; cnt[m]++; } mp[c] = cnt; } ll ans = 0; for (ll a = 0; a < N; a++) { for (ll b = a + 1; b < N; b++) { ll m = (pow10[A[a]] + pow9[A[b]]) % P; if (b + 1 < N) ans += mp[b + 1][(Q - m + P) % P]; } } print1(ans); return 0; }