結果

問題 No.2709 1975 Powers
コンテスト
ユーザー solstice
提出日時 2026-01-10 00:07:38
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 1,725 ms / 2,000 ms
コード長 6,219 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,822 ms
コンパイル使用メモリ 383,536 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-10 00:08:05
合計ジャッジ時間 25,806 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// suo
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
// #include "atcoder/segtree.hpp"
// using namespace atcoder;
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// typedef tree<pair<int,int>, null_type, greater<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
template <class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;  

typedef long long ll;
typedef long double ld;
using usize = size_t;
using NAME = void;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

template<class qu> using pq = priority_queue<qu>;
template<class qu> using pqg = priority_queue<qu, vector<qu>, greater<qu>>;

// #define mp make_pair
#define int long long
#define uint long long
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define fi first
#define se second
#define lso(s) ((s) & -(s))
int lg(ll s) { return s ? __builtin_clzll(1) - __builtin_clzll(s) : -1; }//lg(1)=0, lg(2)=1, lg(3)=1, lg(4)=2, ...
#define all(x) begin(x), end(x)
// #define sz(x) (int)(x).sz()

const ll MOD = (int)1e9 + 7;
const ll mod = 998244353;
const double EPS = 1e-16;
const ll BIG = 1e18;
const ll INF = 4e18;
ll lcm(ll a,ll b) { return a/__gcd(a,b)*b; }
ll floor(ll a, ll b) { return a / b - (a % b < 0); }
ll ceil(ll a, ll b) { return a / b + (a % b > 0); }

template<typename qu>
istream& operator>>(istream& in, vector<qu> &vec){
  for(auto &x : vec){
    in >> x;
  }
  return in;
}

#ifdef sparkle
template <typename T>
ostream& operator << (ostream &o, vector<T> vec) {
    o << "{"; int f = 0;
    for (T i : vec) o << (f++ ? " " : "") << i;
    return o << "}";
}
void bug__(int c, auto ...a) {
    cerr << "\e[1;" << c << "m";
    (..., (cerr << a << " "));
    cerr << "\e[0m" << endl;
}
#define bug_(c, x...) bug__(c, __LINE__, "[" + string(#x) + "]", x)
#define bug(x...) bug_(32, x)
#define bugv(x...) bug_(36, vector(x))
#define safe bug_(33, "safe")
#else
#define bug(x...) void(0)
#define bugv(x...) void(0)
#define safe void(0)
#endif

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.a/splitmix64.c
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const noexcept {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }

  size_t operator()(const pair<ll, ll>& pq) const noexcept {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    uint64_t h1 = splitmix64((uint64_t)pq.first + FIXED_RANDOM);
    uint64_t h2 = splitmix64((uint64_t)pq.second + FIXED_RANDOM + 0x9e3779b97f4a7c15ULL);
    return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2));
  }
};

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll gen() {
  ll x = 0;
  while(x == 0)
    x = rng() % MOD;
  return x;
}

struct mint {
  ll x;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint& operator+=(const mint a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}
  mint& operator-=(const mint a) {if ((x += MOD-a.x) >= MOD) x -= MOD;return *this;}
  mint& operator*=(const mint a) {(x *= a.x) %= MOD;return *this;}
  mint operator+(const mint a) const {mint res(*this);return res+=a;}
  mint operator-(const mint a) const {mint res(*this);return res-=a;}
  mint operator*(const mint a) const {mint res(*this);return res*=a;}
  mint pow(ll b) const {
      mint res(1), a(*this);
      while (b) {
          if (b & 1) res *= a;
          a *= a;
          b >>= 1;
      }
      return res;
  }
  // for pq MOD
  mint inv() const {return pow(MOD-2);}
  mint& operator/=(const mint a) {return (*this) *= a.inv();}
  mint operator/(const mint a) const {mint res(*this);return res/=a;}
};  
ostream& operator<<(ostream& os, const mint& a) {os << a.x; return os;}

template <class T>
  inline void chadd(T &x, T y) { x += y; if(x >= mod) x -= mod; }

template <class T>
  inline void chmin(T &x, T y) { if (y < x) x = y; }

template <class T>
  inline void chmax(T &x, T y) { if (y > x) x = y; }

auto mul(int a, int b) -> int { return (a % MOD * b % MOD) % MOD; }
auto add(int a, int b) -> int { return (a % MOD + b % MOD) % MOD; }
auto sub(int a, int b) -> int { return (a % MOD - b % MOD + MOD) % MOD; }

inline NAME  before() { }

// #define tests
auto sparkle() -> void {
  
}

auto fastexpo(int a, int b, int md) -> int {
  int res = 1;
  a %= md;
  while (b) {
    if (b & 1) {
      res = (res * a) % md;
    }
    b >>= 1;
    a = (a * a) % md;
  }
  return res;
}

[[gnu::target("avx2"), gnu::flatten]] 
auto main() -> int32_t {
  std::cin.tie(nullptr)->sync_with_stdio(0);
  std::cin.exceptions(std::ios::failbit | std::ios::badbit);
  // freopen("in","r",stdin);
  // freopen("outt","w",stdout);
  
  int TC = 1; // cin >> TC;
  while (TC --> 0) {  
    int n, p, q; cin >> n >> p >> q;
    vector<int> a(n); 
    for (auto& i : a) cin >> i;   
    sort(all(a));
    
    map<int, vector<int>> mp;
    for (int i = 0; i < n; ++i) {
      mp[fastexpo(5, a[i], p)].pb(i);
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        for (int k = j + 1; k < n; ++k) {
          int sum = (fastexpo(10, a[i], p) + fastexpo(9, a[j], p) + fastexpo(7, a[k], p)) % p;
          auto it = mp.find((q - sum + p) % p);
          if (it != mp.end()) {
            auto d = it->se;
            auto v = upper_bound(d.begin(), d.end(), k);
            ans += distance(v, d.end());
          }
        }
      }
    }
    cout << ans << '\n';
  }
    
  return 0;
}
0