結果

問題 No.1731 Product of Subsequence
コンテスト
ユーザー yasuwo
提出日時 2021-11-27 17:51:25
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0