結果
問題 | No.2709 1975 Powers |
ユーザー |
![]() |
提出日時 | 2024-03-31 14:24:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 720 ms / 2,000 ms |
コード長 | 2,937 bytes |
コンパイル時間 | 4,006 ms |
コンパイル使用メモリ | 233,672 KB |
実行使用メモリ | 66,044 KB |
最終ジャッジ日時 | 2024-09-30 19:28:59 |
合計ジャッジ時間 | 13,178 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>#define rep(i,a,n) for(ll i = a; i < n; i++)#define yes (cout << "Yes" << endl)#define YES (cout << "YES" << endl)#define no (cout << "No" << endl)#define NO (cout << "NO" << endl)#define pb push_back#define pf push_front#define mp make_pair#define fi first#define se second#define all(a) (a).begin(),(a).end()using namespace std;using namespace atcoder;using ll = long long;using ull = unsigned long long;using vi = vector<int>;using vd = vector<double>;using vs = vector<string>;using vl = vector<long long>;using vvi = vector<vector<int>>;using Graph = vector<vector<int>>;const int mod = 998244353;const int MOD = 1000000007;const int dx[4] = {-1,0,1,0};const int dy[4] = {0,1,0,-1};ll chmin(ll a,ll b) {if(a < b) return a;else return b;}void O(vector<int> v) {rep(i,0,v.size()) {cout << v[i] << " ";}cout << endl;}void O(vector<string> v) {rep(i,0,v.size()) cout << v[i] << endl;cout << endl;}void O(int a) {cout << a << endl;}void O(ll a) {cout << a << endl;}void O(string s) {cout << s << endl;}struct unionfind {vector<int> data;unionfind(int size) : data(size, -1) { }bool unite(int x, int y) {x = root(x); y = root(y);if (x != y) {if (data[y] < data[x]) swap(x, y);data[x] += data[y]; data[y] = x;}return x != y;}bool same(int x, int y) {return root(x) == root(y);}int root(int x) {return data[x] < 0 ? x : data[x] = root(data[x]);}int size(int x) {return -data[root(x)];}};ll gcd(ll a, ll b) {a = abs(a); b = abs(b);if (a < b)swap(a, b);while (b) {ll r = a % b; a = b; b = r;}return a;}//x,yがax+by=gcd(a,b)の解になる x,yが格納ll extgcd(ll a, ll b, ll& x, ll& y) {ll d = a;if (b != 0) {d = extgcd(b, a % b, y, x);y -= (a / b) * x;}else {x = 1; y = 0;}return d;}ll pow(ll a,ll b) {ll ans = 1;rep(i,0,b) ans *= a;return ans;}int main() {ll n,p,q;cin >> n >> p >> q;ll a[n];rep(i,0,n) {cin >> a[i];}sort(a,a + n);ll ten[2000006],nine[2000006],seven[2000006],five[2000006];ten[0] = 1;nine[0] = 1;seven[0] = 1;five[0] = 1;rep(i,1,2000006) {ten[i] = (ten[i - 1] * 10) % p;nine[i] = (nine[i - 1] * 9) % p;seven[i] = (seven[i - 1] * 7) % p;five[i] = (five[i - 1] * 5) % p;}//rep(i,0,p) cout << i << " " << ten[i] << " " << nine[i] << " " << seven[i] << " " << five[i] << endl;ll ans = 0;rep(i,0,n) rep(j,i + 1,n) rep(k,j + 1,n) rep(l,k + 1,n) {ll now = ten[a[i]] + nine[a[j]] + seven[a[k]] + five[a[l]];now %= p;if(now == q) {ans++;//cout << a[i] << " " << a[j] << " " << a[k] << " " << a[l] << now << endl;}}cout << ans << endl;}