結果
| 問題 | No.1731 Product of Subsequence |
| ユーザー |
 shobonvip
|
| 提出日時 | 2023-05-26 21:11:54 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,056 bytes |
| コンパイル時間 | 4,704 ms |
| コンパイル使用メモリ | 272,024 KB |
| 実行使用メモリ | 108,320 KB |
| 最終ジャッジ日時 | 2023-08-26 09:42:25 |
| 合計ジャッジ時間 | 12,358 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef modint1000000007 mint;
typedef long long ll;
vector<pair<int,int>> pfact(int n){
vector<pair<int,int>> ret;
for (int i=2; i*i<=n; i++){
if (n%i == 0){
int cnt = 0;
while (n%i == 0){
n /= i;
cnt++;
}
ret.push_back(pair(i, cnt));
}
}
if (n > 1) ret.push_back(pair(n, 1));
return ret;
}
int main(){
int n, k; cin >> n >> k;
vector<pair<int,int>> pf = pfact(k);
vector<int> pl;
for (auto [p,c]: pf){
pl.push_back(p);
}
vector<ll> a(n);
for (int i=0; i<n; i++){
cin >> a[i];
ll nw = 1;
for (int j: pl){
while (a[i] % j == 0){
nw *= j;
a[i] /= j;
}
}
a[i] = nw;
}
map<int,mint> s;
s[1] = 1;
for (int i=0; i<n; i++){
map<int,mint> ns = s;
for (auto j=s.begin(); j!=s.end(); j++){
int tmp = (ll)j->first * a[i] % k;
if (ns.find(tmp) == ns.end()){
ns[tmp] = 0;
}
ns[tmp] += j->second;
}
s = ns;
}
if (s.find(0) == s.end()){
s[0] = 0;
}
cout << s[0].val() << endl;
}