http://codeforces.com/contest/979
順位はそんな悪くないんですが…
A
n=0〜
B
奇数偶数やろ…となるんですが違います
C
えぇ…
D
追加は約数個のオーダーだし、答える時は、segtreeっぽく範囲を狭めていきます。問題文が無駄に複雑。やめて。
考察は一瞬でしたが、なかなか実装が辛かった。
int Q; set<int> S[100010];//can be divisible by i void loop(const vector<pi>& vec, int at, int x, int cur) { if(at == sz(vec)) { S[cur].insert(x); return; } rep(i, 0, vec[at].sec + 1) { loop(vec, at + 1, x, cur); cur *= vec[at].fst; } } void add(int x) { vector<pi> vec; int tx = x; for(int i = 2; i * i <= tx; i++) { if(tx % i == 0) { int cnt = 0; while(tx % i == 0) { tx /= i; cnt++; } vec.pb(pi(i, cnt)); } } if(tx != 1) vec.pb(pi(tx, 1)); loop(vec, 0, x, 1); } int get(int k, int y, int x) { set<int>& s = S[k]; int a = 0, b = y + 1; int l = 0, r = (1 << 17); rer(i, 17, 0) { // debug(l, r, x, vi(all(s))); int m = (r + l) / 2; if((1 << i) & x) { //i bit should be 0 int tlv = max(a, l), trv = min(b, m); if(trv - tlv > 0 && s.lower_bound(trv) != s.lower_bound(tlv)) { r = m; } else { tlv = max(a, m), trv = min(b, r); if(trv - tlv > 0 && s.lower_bound(trv) != s.lower_bound(tlv)) { l = m; } else return -1; } } else { //i bit should be 1 int tlv = max(a, m), trv = min(b, r); if(trv - tlv > 0 && s.lower_bound(trv) != s.lower_bound(tlv)) { l = m; } else { tlv = max(a, l), trv = min(b, r); if(trv - tlv > 0 && s.lower_bound(trv) != s.lower_bound(tlv)) { r = m; } else return -1; } } } return l; } void solve() { cin >> Q; while(Q--) { int type; cin >> type; if(type == 1) { int x; cin >> x; add(x); // rep(i, 1, 30) { // debug(i, vi(all(S[i]))); // } } else { int x, k, s; cin >> x >> k >> s; if(x % k != 0) cout << "-1\n"; else cout << get(k, s - x, x) << "\n"; } } }
E
えぇ…pathの偶奇みるだけ。ちょっと前計算すればO(N^4)。
int N, P; ll pre[110][2]; ll dp[51][51][51][51]; ll pow2[110]; int A[51]; void solve() { cin >> N >> P; rep(i, 0, N) cin >> A[i]; C_init(N + 10); rep(i, 0, N + 1) { rep(j, 0, i + 1) { ADD(pre[i][j % 2], C[i][j]); } } pow2[0] = 1; rep(i, 0, N) pow2[i + 1] = pow2[i] * 2 % mod; dp[0][0][0][0] = 1; rep(wo, 0, N) { rep(we, 0, N) { rep(bo, 0, N) { rep(be, 0, N) { if(dp[wo][we][bo][be] == 0) continue; int i = wo + we + bo + be; if(A[i] != 1) { //black ADD(dp[wo][we][bo + 1][be], dp[wo][we][bo][be] * pow2[we + bo + be] % mod * pre[wo][0] % mod); ADD(dp[wo][we][bo][be + 1], dp[wo][we][bo][be] * pow2[we + bo + be] % mod * pre[wo][1] % mod); } if(A[i] != 0) { //white ADD(dp[wo + 1][we][bo][be], dp[wo][we][bo][be] * pow2[wo + we + be] % mod * pre[bo][0] % mod); ADD(dp[wo][we + 1][bo][be], dp[wo][we][bo][be] * pow2[wo + we + be] % mod * pre[bo][1] % mod); } } } } } ll res = 0; rep(wo, 0, N + 1) { rep(we, 0, N + 1) { rep(bo, 0, N + 1) { rep(be, 0, N + 1) { if(wo + we + bo + be == N && (bo + wo) % 2 == P) { ADD(res, dp[wo][we][bo][be]); } } } } } cout << res << "\n"; }
ABでHackされてDで1WA。速度もそんな速くなくて悔しいですね…。
HackしてもらえなかったらCDのみだったことを考えるとヒヤッとしますね。コーナーケースをよく見極めないとやけどするので気をつけないと…
