結果
問題 | No.719 Coprime |
ユーザー | snrnsidy |
提出日時 | 2021-07-15 15:23:01 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,161 bytes |
コンパイル時間 | 2,811 ms |
コンパイル使用メモリ | 221,048 KB |
実行使用メモリ | 11,776 KB |
最終ジャッジ日時 | 2024-07-04 15:33:48 |
合計ジャッジ時間 | 15,441 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 181 ms
11,648 KB |
testcase_01 | AC | 180 ms
11,648 KB |
testcase_02 | AC | 184 ms
11,520 KB |
testcase_03 | AC | 178 ms
11,520 KB |
testcase_04 | AC | 180 ms
11,520 KB |
testcase_05 | AC | 180 ms
11,520 KB |
testcase_06 | AC | 188 ms
11,520 KB |
testcase_07 | AC | 180 ms
11,648 KB |
testcase_08 | AC | 180 ms
11,648 KB |
testcase_09 | AC | 182 ms
11,648 KB |
testcase_10 | AC | 183 ms
11,520 KB |
testcase_11 | AC | 186 ms
11,520 KB |
testcase_12 | AC | 180 ms
11,520 KB |
testcase_13 | AC | 178 ms
11,520 KB |
testcase_14 | AC | 183 ms
11,392 KB |
testcase_15 | AC | 181 ms
11,520 KB |
testcase_16 | AC | 183 ms
11,648 KB |
testcase_17 | AC | 183 ms
11,648 KB |
testcase_18 | AC | 183 ms
11,520 KB |
testcase_19 | AC | 185 ms
11,520 KB |
testcase_20 | AC | 186 ms
11,520 KB |
testcase_21 | AC | 184 ms
11,520 KB |
testcase_22 | AC | 182 ms
11,648 KB |
testcase_23 | AC | 183 ms
11,648 KB |
testcase_24 | AC | 182 ms
11,520 KB |
testcase_25 | AC | 183 ms
11,520 KB |
testcase_26 | AC | 180 ms
11,520 KB |
testcase_27 | AC | 178 ms
11,520 KB |
testcase_28 | AC | 182 ms
11,520 KB |
testcase_29 | AC | 180 ms
11,520 KB |
testcase_30 | AC | 181 ms
11,648 KB |
testcase_31 | AC | 185 ms
11,648 KB |
testcase_32 | AC | 189 ms
11,648 KB |
testcase_33 | AC | 182 ms
11,520 KB |
testcase_34 | AC | 183 ms
11,648 KB |
testcase_35 | AC | 184 ms
11,648 KB |
testcase_36 | AC | 184 ms
11,520 KB |
testcase_37 | AC | 179 ms
11,520 KB |
testcase_38 | AC | 180 ms
11,392 KB |
testcase_39 | AC | 180 ms
11,648 KB |
testcase_40 | AC | 181 ms
11,520 KB |
testcase_41 | AC | 183 ms
11,648 KB |
testcase_42 | AC | 178 ms
11,520 KB |
testcase_43 | AC | 180 ms
11,520 KB |
testcase_44 | WA | - |
testcase_45 | WA | - |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | WA | - |
testcase_49 | WA | - |
testcase_50 | WA | - |
testcase_51 | WA | - |
testcase_52 | WA | - |
testcase_53 | WA | - |
testcase_54 | WA | - |
testcase_55 | WA | - |
testcase_56 | WA | - |
testcase_57 | WA | - |
testcase_58 | WA | - |
testcase_59 | WA | - |
testcase_60 | WA | - |
コンパイルメッセージ
main.cpp: In function 'std::vector<int> berlekamp_massey(std::vector<int>)': main.cpp:33:44: warning: 'ld' may be used uninitialized [-Wmaybe-uninitialized] 33 | lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod; | ~~~~^~~~~~~~~~~~~ main.cpp:20:17: note: 'ld' was declared here 20 | int lf, ld; | ^~ main.cpp:34:32: warning: 'lf' may be used uninitialized [-Wmaybe-uninitialized] 34 | vector<int> c(i-lf-1); | ~^~~ main.cpp:20:13: note: 'lf' was declared here 20 | int lf, ld; | ^~
ソースコード
#include <bits/stdc++.h> using namespace std; vector <int> prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71}; int dp[2][1<<20]; const int mod = 998244353; using lint = long long; lint ipow(lint x, lint p){ lint ret = 1, piv = x; while(p){ if(p & 1) ret = ret * piv % mod; piv = piv * piv % mod; p >>= 1; } return ret; } vector<int> berlekamp_massey(vector<int> x){ vector<int> ls, cur; int lf, ld; for(int i=0; i<x.size(); i++){ lint t = 0; for(int j=0; j<cur.size(); j++){ t = (t + 1ll * x[i-j-1] * cur[j]) % mod; } if((t - x[i]) % mod == 0) continue; if(cur.empty()){ cur.resize(i+1); lf = i; ld = (t - x[i]) % mod; continue; } lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod; vector<int> c(i-lf-1); c.push_back(k); for(auto &j : ls) c.push_back(-j * k % mod); if(c.size() < cur.size()) c.resize(cur.size()); for(int j=0; j<cur.size(); j++){ c[j] = (c[j] + cur[j]) % mod; } if(i-lf+(int)ls.size()>=(int)cur.size()){ tie(ls, lf, ld) = make_tuple(cur, i, (t - x[i]) % mod); } cur = c; } for(auto &i : cur) i = (i % mod + mod) % mod; return cur; } int get_nth(vector<int> rec, vector<int> dp, lint n){ int m = rec.size(); vector<int> s(m), t(m); s[0] = 1; if(m != 1) t[1] = 1; else t[0] = rec[0]; auto mul = [&rec](vector<int> v, vector<int> w){ int m = v.size(); vector<int> t(2 * m); for(int j=0; j<m; j++){ for(int k=0; k<m; k++){ t[j+k] += 1ll * v[j] * w[k] % mod; if(t[j+k] >= mod) t[j+k] -= mod; } } for(int j=2*m-1; j>=m; j--){ for(int k=1; k<=m; k++){ t[j-k] += 1ll * t[j] * rec[k-1] % mod; if(t[j-k] >= mod) t[j-k] -= mod; } } t.resize(m); return t; }; while(n){ if(n & 1) s = mul(s, t); t = mul(t, t); n >>= 1; } lint ret = 0; for(int i=0; i<m; i++) ret += 1ll * s[i] * dp[i] % mod; return ret % mod; } int guess_nth_term(vector<int> x, lint n){ if(n < x.size()) return x[n]; vector<int> v = berlekamp_massey(x); if(v.empty()) return 0; return get_nth(v, x, n); } struct elem{int x, y, v;}; // A_(x, y) <- v, 0-based. no duplicate please.. vector<int> get_min_poly(int n, vector<elem> M){ // smallest poly P such that A^i = sum_{j < i} {A^j \times P_j} vector<int> rnd1, rnd2; mt19937 rng(0x14004); auto randint = [&rng](int lb, int ub){ return uniform_int_distribution<int>(lb, ub)(rng); }; for(int i=0; i<n; i++){ rnd1.push_back(randint(1, mod - 1)); rnd2.push_back(randint(1, mod - 1)); } vector<int> gobs; for(int i=0; i<2*n+2; i++){ int tmp = 0; for(int j=0; j<n; j++){ tmp += 1ll * rnd2[j] * rnd1[j] % mod; if(tmp >= mod) tmp -= mod; } gobs.push_back(tmp); vector<int> nxt(n); for(auto &i : M){ nxt[i.x] += 1ll * i.v * rnd1[i.y] % mod; if(nxt[i.x] >= mod) nxt[i.x] -= mod; } rnd1 = nxt; } auto sol = berlekamp_massey(gobs); reverse(sol.begin(), sol.end()); return sol; } lint det(int n, vector<elem> M){ vector<int> rnd; mt19937 rng(0x14004); auto randint = [&rng](int lb, int ub){ return uniform_int_distribution<int>(lb, ub)(rng); }; for(int i=0; i<n; i++) rnd.push_back(randint(1, mod - 1)); for(auto &i : M){ i.v = 1ll * i.v * rnd[i.y] % mod; } auto sol = get_min_poly(n, M)[0]; if(n % 2 == 0) sol = mod - sol; for(auto &i : rnd) sol = 1ll * sol * ipow(i, mod - 2) % mod; return sol; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; vector <int> v = {0,0}; cin >> N; for(int i=0;i<2;i++) { for(int j=0;j<(1<<20);j++) { dp[i][j] = -1e9; } } dp[1][0] = 0; for(int i=1;i<100;i++) { memcpy(dp[0],dp[1],sizeof(dp[1])); fill(dp[1],dp[1]+(1<<20),-1e9); int bitmask = 0; for(int j=0;j<20;j++) { if(((i+1)%prime[j])==0) { bitmask += (1<<j); } } //cout << i+1 << ' ' << bitmask << '\n'; for(int j=0;j<(1<<20);j++) { if(dp[0][j]<=-1e9) continue; dp[1][j] = max(dp[1][j],dp[0][j]); if((j&bitmask)) continue; dp[1][bitmask + j] = max(dp[1][bitmask + j],dp[0][j] + (i+1)); } int res = 0; for(int j=0;j<(1<<20);j++) { res = max(res,dp[1][j]); } v.push_back(res); } cout << guess_nth_term(v,N) << '\n'; return 0; }