#720410 (C++23) No.1731 Product of Subsequence

提出ソース

結果

問題	No.1731 Product of Subsequence
ユーザー	yasuwo
提出日時	2021-11-27 17:51:25
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,007 bytes
コンパイル時間	6,203 ms
コンパイル使用メモリ	324,864 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-06-30 08:42:13
合計ジャッジ時間	9,111 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	185 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	14 ms 6,944 KB
testcase_09	WA	-
testcase_10	AC	241 ms 6,940 KB
testcase_11	AC	203 ms 6,940 KB
testcase_12	AC	3 ms 6,944 KB
testcase_13	AC	3 ms 6,948 KB
testcase_14	AC	185 ms 6,940 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	WA	-
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	215 ms 6,944 KB
testcase_19	AC	3 ms 6,944 KB
testcase_20	AC	177 ms 6,940 KB
testcase_21	AC	242 ms 6,944 KB
testcase_22	AC	126 ms 6,940 KB
testcase_23	WA	-
testcase_24	AC	5 ms 6,940 KB
testcase_25	AC	3 ms 6,940 KB
testcase_26	AC	31 ms 6,940 KB
testcase_27	AC	45 ms 6,940 KB
testcase_28	AC	107 ms 6,940 KB
testcase_29	AC	34 ms 6,940 KB
testcase_30	AC	187 ms 6,940 KB
testcase_31	AC	127 ms 6,940 KB
testcase_32	WA	-
testcase_33	AC	9 ms 6,940 KB
testcase_34	AC	8 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "main.cpp"
#include <bits/stdc++.h>
#include <atcoder/all>
#line 2 "/home/yasu/Documents/library/library/templates/mydebug.hpp"
#ifdef __DEBUG__
    void debug_out() { std::cerr << "\n";} 
    template <typename Head, typename... Tail>
    void debug_out(Head H, Tail... T) {std::cerr << H << " "; debug_out(T...);}
    #define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:\n" , debug_out(__VA_ARGS__)
#else
    #define debug(...) 
#endif

#line 1 "/home/yasu/Documents/library/library/templates/myconst.hpp"
const int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
const int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const long long int  LL_INF = (long long int)(2e18);
#line 13 "/home/yasu/Documents/library/library/templates/template.hpp"

static std::mt19937 _g(time(nullptr)); 
inline long long int randint(long long int a, long long int b) { long long int w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); };
template<typename T, typename S> inline std::ostream& operator<<(std::ostream& os, const std::pair<T, S> p) { os << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline std::ostream& operator<<(std::ostream& os, const std::map<T, S> p) { for (auto el : p) os << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T, typename S> inline std::ostream& operator<<(std::ostream& os, const std::unordered_map<T, S> p) { for (auto el : p) os << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) { for (auto el : v) os << el << " "; return os; }
template<typename T> inline std::ostream& operator<<(std::ostream& os, const std::vector<std::vector<T>>& v) { for (auto el : v) os << el << "\n"; return os; }
template<typename T> inline std::ostream& operator<<(std::ostream& os, const std::deque<T>& v) { for (auto el : v) os << el << " "; return os; }
template<typename T> inline std::ostream& operator<<(std::ostream& os, const std::queue<T>& v) { for (auto el : v) os << el << " "; return os; }
template<typename T> inline std::ostream& operator<<(std::ostream& os, const std::stack<T>& v) { for (auto el : v) os << el << " "; return os; }
template<typename T> inline std::ostream& operator<<(std::ostream& os, const std::set<T>& v) { for (auto el : v) os << el << " "; return os; }
template<typename T> inline std::ostream& operator<<(std::ostream& os, const std::multiset<T>& v) { for (auto el : v) os << el << " "; return os; }
template<typename T> inline std::istream& operator>>(std::istream& is, std::vector<T> &vec) {for (T &x : vec) is >> x;return is;}
template<typename T> inline std::vector<T> fetch_vec(int sz) { std::vector<T> ret(sz); for (auto& elem : ret) std::cin >> elem; return ret; }
template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#include <atcoder/modint>
inline std::ostream &operator<<(std::ostream &os, const atcoder::modint1000000007 &x){os << x.val(); return os; }
inline std::ostream &operator<<(std::ostream &os, const  atcoder::modint998244353 &x){os << x.val(); return os; }
#line 4 "main.cpp"
using namespace atcoder;
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

vector<int64_t> divisor(int64_t n)
{
    vector<int64_t> ret;
    for (int64_t i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ret.push_back(i);
            if (i * i != n)
                ret.push_back(n / i);
        }
    }
    sort(begin(ret), end(ret));
    return (ret);
}
using mint = modint1000000007;

long long solve(int N, long long K, const std::vector<long long> &A)
{
    auto divK = divisor(K);
    // cerr << divK << endl;
    map<ll, ll> mpK;
    vector<ll> vK;
    for (ll x : divK)
    {
        mpK[x] = vK.size();
        vK.push_back(x);
    }
    vector<mint> dp(vK.size());
    dp[0] = 1;
    for (int i = 0; i < N; i++)
    {
        vector<mint> nxtdp = dp;
        ll g = gcd(K, A[i]);
        for (int x = 0; x < vK.size(); x++)
        {
            ll k = vK[x];
            k *= g;
            k = gcd(k, K);
            if (k >= K)
            {
                k = K;
            }
            int y = mpK[k];
            nxtdp[y] += dp[x];
        }
        swap(dp, nxtdp);
    }
    return dp[mpK[K]].val();
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int N;
    long long K;
    std::cin >> N >> K;
    std::vector<long long> A(N);
    for (int i = 0; i < N; ++i)
    {
        std::cin >> A[i];
        A[i] %= K;
    }
    auto ans = solve(N, K, A);
    std::cout << ans << '\n';
    return 0;
}

yukicoder

結果

テストケース

ソースコード