結果

問題 No.2709 1975 Powers
ユーザー mkreemmkreem
提出日時 2024-04-14 05:26:33
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 723 ms / 2,000 ms
コード長 12,163 bytes
コンパイル時間 3,661 ms
コンパイル使用メモリ 265,368 KB
実行使用メモリ 65,808 KB
最終ジャッジ日時 2024-10-03 02:38:37
合計ジャッジ時間 12,168 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 21 ms
65,732 KB
testcase_01 AC 20 ms
65,680 KB
testcase_02 AC 26 ms
65,728 KB
testcase_03 AC 378 ms
65,592 KB
testcase_04 AC 611 ms
65,724 KB
testcase_05 AC 426 ms
65,628 KB
testcase_06 AC 142 ms
65,572 KB
testcase_07 AC 21 ms
65,700 KB
testcase_08 AC 135 ms
65,736 KB
testcase_09 AC 422 ms
65,568 KB
testcase_10 AC 20 ms
65,744 KB
testcase_11 AC 29 ms
65,720 KB
testcase_12 AC 50 ms
65,696 KB
testcase_13 AC 440 ms
65,772 KB
testcase_14 AC 76 ms
65,624 KB
testcase_15 AC 86 ms
65,736 KB
testcase_16 AC 335 ms
65,596 KB
testcase_17 AC 21 ms
65,684 KB
testcase_18 AC 57 ms
65,700 KB
testcase_19 AC 608 ms
65,728 KB
testcase_20 AC 22 ms
65,808 KB
testcase_21 AC 130 ms
65,720 KB
testcase_22 AC 721 ms
65,668 KB
testcase_23 AC 721 ms
65,692 KB
testcase_24 AC 718 ms
65,728 KB
testcase_25 AC 721 ms
65,596 KB
testcase_26 AC 723 ms
65,688 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef READ_MAIN
#define READ_MAIN
#include __FILE__

const ll mod = 998244353; using mint = atcoder::modint998244353;
//const ll mod = 1000000007; using mint = atcoder::modint1000000007;

//------------------------------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------------------------------



int main(){
    fast();

    int n, p, q; cin >> n >> p >> q;
    vector<int> A(n);
    rep(i, 0, n) cin >> A[i];
    sort(all(A));

    const int m = 2000009;
    vector<ll> calc5(m), calc7(m), calc9(m), calc10(m);
    rep(i, 0, n){
        calc5[A[i]] = atcoder::pow_mod(5, A[i], p);
        calc7[A[i]] = atcoder::pow_mod(7, A[i], p);
        calc9[A[i]] = atcoder::pow_mod(9, A[i], p);
        calc10[A[i]] = atcoder::pow_mod(10, A[i], p);
    }

    int ans = 0;
    rep(a, 0, n) rep(b, a+1, n) rep(c, b+1, n) rep(d, c+1, n){
        ll calc = calc5[A[d]] + calc7[A[c]] + calc9[A[b]] + calc10[A[a]];
        calc %= p;
        if(calc == q) ans++;
    }

    cout << ans << newl;


}

#else

#include <bits/stdc++.h>
//// data structure
//#include <atcoder/fenwicktree>
//#include <atcoder/segtree>
#include <atcoder/lazysegtree>
//#include <atcoder/string>
//// math
#include <atcoder/math>
//#include <atcoder/convolution>
#include <atcoder/modint>
//// graph
//#include <atcoder/dsu>
//#include <atcoder/maxflow>
//#include <atcoder/mincostflow>
//#include <atcoder/scc>
//#include <atcoder/twosat>

void fast(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::setprecision(15);
}
/*
バグが見つからないとき(RE)...
入力の仕方でミスっている可能性大
セグフォなら、配列の要素参照を、添字演算子から.at()に変えてみる
怪しい場所をコメントアウトしてコンパイルしてみる
*/
// g++ -ggdb -O2 hoge.cpp -I ~/.pml/ac-library -o zzz
/*
メイン関数内に記述すること
std::ifstream in("testcase/hoge"); std::cin.rdbuf(in.rdbuf());
*/

using ll = long long;
using lll = __int128_t;
using ld = long double;
#define newl '\n'
#define debug(x) cout << #x << " = " << (x) << newl;
#define INF 1000390039
#define LLINF 1000000039000000039
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LLMAX LONG_LONG_MAX
#define LLMIN LONG_LONG_MIN
#define shift(i) (1LL<<(i))
#define PI acos(-1)
#define inr(l, x, r) (l <= x && x < r)
#define fore(i, a) for(auto &i : a)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define erep(i, a, b) for(int i = (a); i <= (b); i++)
#define rrep(i, a, b) for(int i = (a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pcnt(x) __builtin_popcount(x)
#define llpcnt(x) __builtin_popcountll(x)
#define vv(name, type, a, ...) vector<vector<type>> name(a, vector<type>(__VA_ARGS__))
#define vvv(name, type, a, b, ...) vector<vector<vector<type>>> name(a, vector<vector<type>>(b, vector<type>(__VA_ARGS__)))
#define vvvv(name, type, a, b, c, ...) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define vvvvv(name, type, a, b, c, d, ...) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(__VA_ARGS__)))));
template <typename T>
int lwb(const std::vector<T>& vec, const T& x){
    return lower_bound(all(vec), x) - vec.begin();
}
template <typename T>
int upb(const std::vector<T>& vec, const T& x){
    return upper_bound(all(vec), x) - vec.begin();
}
template <typename T>
T max(const std::vector<T>& vec){ return *max_element(all(vec)); }
template <typename T>
T min(const std::vector<T>& vec){ return *min_element(all(vec)); }
template <typename T>
T rad(const T& x){ return x * PI/180; }
template <typename T>
using pq = std::priority_queue<T>;
template <typename T>
using pqg = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// @brief シフト演算子を、__int128_t型用にオーバーロード
std::ostream& operator<<(std::ostream& os, __int128_t value){
    if(value == 0) return os << 0;

    static char buffer[128];
    if(value < 0){
        os << '-';
        value = -value;
    }
    int itr = 0;
    while(value > 0){
        buffer[itr++] = value%10 + '0';
        value /= 10;
    }
    std::reverse(buffer, buffer + itr);
    buffer[itr] = 0;
    return os << buffer;
}
// @brief string型の10進非負整数を、__128_t型に変換する
__int128_t parse(const std::string& s){
    __int128_t res = 0;
    for(int i = 0; i < s.length(); i++){
        res = 10*res + (s[i]-'0');
    }
    return res;
}
// 最大値・最小値の更新
template <typename T1, typename T2>
bool chmax(T1 &a, const T2& b){
    if(a < b){ a = b; return 1; }
    else return 0;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2& b){
    if(a > b){ a = b; return 1; }
    else return 0;
}
template <typename T>
void iota(std::vector<T>& vec, bool greater = false){
    std::iota(all(vec), 0);
    std::sort(all(vec), [&](int i, int j){
        if(greater) return vec[i] > vec[j];
        return vec[i] < vec[j];
    });
}
// 2つのvectorをマージ
template <typename T>
std::vector<T> vmerge(std::vector<T>& a, std::vector<T>& b){
    std::vector<T> res;
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(res));
    return res;
}


// 辺
template <typename T>
class Edge{
public:
    int from, to;
    T cost;
    int ID;
    Edge(int to, T cost) : to(to), cost(cost) {} // for WG
    Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} // for Edges
    Edge(int from, int to, T cost, int ID) : from(from), to(to), cost(cost), ID(ID) {} // for Edges
    bool operator<(const Edge<T>& rhs) const { return cost < rhs.cost; };
    bool operator>=(const Edge<T>& rhs) const { return !(cost < rhs.cost); };
    bool operator>(const Edge<T>& rhs) const { return cost > rhs.cost; };
    bool operator<=(const Edge<T>& rhs) const { return !(cost > rhs.cost); };
    bool operator==(const Edge<T>& rhs) const { return cost == rhs.cost; };
    bool operator!=(const Edge<T>& rhs) const { return !(cost == rhs.cost); };
};
using G = std::vector<std::vector<int>>;
template <typename T>
using WG = std::vector<std::vector<Edge<T>>>;
template <typename T>
using Edges = std::vector<Edge<T>>;

template <typename T, typename F>
// @param ok 解が存在する値
// @param ng 解が存在しない値
// @remark ok > ng の場合は最小値、ok < ng の場合は最大値を返却
T Bsearch(T& ok, T& ng, const F& f){
    while(std::abs(ok-ng) > 1){
        T mid = (ok-ng)/2 + ng;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}
template <typename T, typename F>
T Bsearch_double(T& ok, T& ng, const F& f, int itr = 80){
    while(itr--){
        T mid = (ok+ng)/2;
        //T mid = sqrtl(ok*ng);
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}


template <typename T>
// @brief (k, n-k)-shuffleである0, 1, ..., N-1 の置換Aを、辞書順で列挙する
bool next_shuffle(std::vector<T>& vec, const int& k){
    int n = vec.size();
    if(n <= k){
        return false;
    }

    // 前K項 := L
    // 後ろN-K項 := R
    auto left = vec.begin();
    auto right = vec.begin() + k;
    T R_max = *std::max_element(right, vec.end());
    T tmp = (std::numeric_limits<T>::min)();
    // @param i Lの要素の中で、Rの要素の最大値よりも小さいもののうち、最大のもののイテレータ(*i := L_(i))
    auto tmpi = left, i = right;
    while(tmpi != right){
        if(tmp <= *tmpi && *tmpi < R_max){
            tmp = *tmpi;
            i = tmpi;
        }
        tmpi++;
    }
    if(i == right){
        return false;
    }

    // @param j Rの要素の中で、L_(i)よりも大きいもののうち、最小のもののイテレータ(*j := R_(j))
    tmp = (std::numeric_limits<T>::max)();
    auto tmpj = right, j = vec.end();
    while(tmpj != vec.end()){
        if(tmp >= *tmpj && *tmpj > *i){
            tmp = *tmpj;
            j = tmpj;
        }
        tmpj++;
    }

    std::iter_swap(i, j); // L_(i)とR_(j)をswap
    i++, j++;
    // やりたいこと：L_(i+1)～L_(k-1)(:= X)とR_(j+1)～R_(n-k-1)(:= Y)を接続し、R_(j+1)が先頭に来るように回転する
    int X_len = k-std::distance(left, i);
    int Y_len = n-k-std::distance(right, j);
    int swap_len = std::min(X_len, Y_len);
    // Xの末尾swap_len項とYの末尾swap_len項をswapする
    std::swap_ranges(right-swap_len, right, j);
    if(swap_len == X_len){
        std::rotate(j, j+swap_len, vec.end());
    }
    else{
        std::rotate(i, right-swap_len, right);
    }

    return true;
}

int log2ll(long long N){
    int B = -1;
    while(N != 0){
        B++;
        N /= 2;
    }
    return B;
}
template <typename T>
// @brief (2,...,2)-shuffleである0, 1, ..., 2*N-1 の置換Aを、辞書順で列挙する
bool next_pairing(std::vector<T>& vec){
    int n = vec.size();
    // @param used vecに含まれるどの数が使用済みであるか
    ll used = 0;
    for(int i = n-1; i >= 0; i--){
        used |= (1<<vec[i]);
        if(i%2 == 1 && vec[i] < log2ll(used)){ // インクリメントできる
            vec[i] = __builtin_ctzll(used >> (vec[i]+1)) + vec[i]+1;
            used ^= (1<<vec[i]);
            for(int j = i+1; j < n; j++){
                vec[j] = __builtin_ctzll(used);
                used ^= (1<<vec[j]);
            }
            return true;
        }
    }
    return false;
}


const int di4[4] = {-1, 0, 1, 0};
const int dj4[4] = {0, 1, 0, -1};
const int di8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const std::vector<std::tuple<int, int, int>> line3{{0,1,2}, {3,4,5}, {6,7,8}, {0,3,6}, {1,4,7}, {2,5,8}, {0,4,8}, {2,4,6}};
const std::vector<std::tuple<int, int, int, int>> line4{{0,1,2,3}, {4,5,6,7}, {8,9,10,11}, {12,13,14,15}, {0,4,8,12}, {1,5,9,13}, {2,6,10,14}, {3,7,11,15}, {0,5,10,15}, {3,6,9,12}};

bool OutOfGrid(const int& i, const int& j, const int& h, const int& w){
    if(i < 0 || j < 0 || i >= h || j >= w) return true;
    return false;
}

// @brief 繰り返し二乗法を利用した、x^nの求値
ll power(ll x, ll n){
    ll res = 1;

    while(n){
        if(n & 1) res *= x;
        x *= x;
        n >>= 1;
    }

    return res;
}

ll power_mod(ll x, ll n, const ll& m){
    ll res = 1;

    while(n){
        if(n & 1){
            res = (res*x) % m;
        }
        x = (x*x) % m;
        n >>= 1;
    }

    return res;
}

// @brief x/mのfloor（x/m以下の最大の整数）を求める
ll floor(const ll& x, const ll& m){
    ll r = (x%m + m) % m; // xをmで割った余り
    return (x-r)/m;
}

// @brief x/mのceil（x/m以上の最小の整数）を求める
ll ceil(const ll& x, const ll& m){
    return floor(x+m-1, m); // x/m + (m-1)/m
}

// @brief prefix_sum[i][j] := [0, i)×[0, j) での二次元配列の総和
// @brief f(i, j) := a[i][j]の値
// @rem 貰う遷移で埋めていく
template <typename T>
std::vector<std::vector<T>> prefix_sum(const int& h, const int& w, const std::function<T(int, int)>& f) {
    std::vector<std::vector<T>> sum(h+1, std::vector<T>(w+1, T()));
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            sum[i+1][j+1] = f(i, j) + sum[i][j+1] + sum[i+1][j] - sum[i][j];
        }
    }
    return sum;
}

// @brief suffix_sum[i][j] := [0, i)×[0, j) での二次元配列の総和
// @brief f(i, j) := a[i][j]の値
// @rem 貰う遷移で埋めていく
template <typename T>
std::vector<std::vector<T>> suffix_sum(const int& h, const int& w, const std::function<T(int, int)>& f) {
    std::vector<std::vector<T>> sum(h+1, std::vector<T>(w+1, T()));
    for(int i = h-1; i >= 0; i--){
        for(int j = w-1; j >= 0; j--){
            sum[i][j] = f(i, j) + sum[i+1][j] + sum[i][j+1] - sum[i+1][j+1];
        }
    }
    return sum;
}

using namespace std;

#endif
0