https://yukicoder.me/problems/no/753
dp[level][bit][winner]:level段のトーナメントをbitに属す挑戦者で作る。勝者がwinnerの時の場合の数
として求めます。高速化いろいろしてAC。
https://yukicoder.me/problems/no/749
和と積のクエリが混ざっている時ってこうやれば良いんですね。解説で群論による考え方が記載されていたのであとで読みたいですね。
ai->kは0を掛けてkを足すクエリに言い換えられます。
struct segtree { // this is piece of shit. use BIT int n; vl sum, add, mul, fib; void init(int mx) { n = 1; while(n < mx) n *= 2; sum = vl(n * 2, 0); add = vl(n * 2, 0); mul = vl(n * 2, 1); fib = vl(n * 2, 0); } segtree(int mx = 0) { init(mx); } inline void lazy_eval(int k, int l, int r) { int m = (l + r) / 2; if(add[k] || mul[k] != 1 || fib[k]) { MUL(sum[k * 2 + 1], mul[k]); ADD(sum[k * 2 + 1], (vx[m] - vx[l] + mod) * add[k] % mod); ADD(sum[k * 2 + 1], (F[vx[m]] - F[vx[l]] + mod) * fib[k] % mod); MUL(mul[k * 2 + 1], mul[k]); MUL(add[k * 2 + 1], mul[k]); MUL(fib[k * 2 + 1], mul[k]); ADD(add[k * 2 + 1], add[k]); ADD(fib[k * 2 + 1], fib[k]); MUL(sum[k * 2 + 2], mul[k]); ADD(sum[k * 2 + 2], (vx[r] - vx[m] + mod) * add[k] % mod); ADD(sum[k * 2 + 2], (F[vx[r]] - F[vx[m]] + mod) * fib[k] % mod); MUL(mul[k * 2 + 2], mul[k]); MUL(add[k * 2 + 2], mul[k]); MUL(fib[k * 2 + 2], mul[k]); ADD(add[k * 2 + 2], add[k]); ADD(fib[k * 2 + 2], fib[k]); add[k] = 0; mul[k] = 1; fib[k] = 0; } } void addapp(int a, int b, ll s, int k, int l, int r) { if(b <= l || r <= a) return; if(a <= l && r <= b) { ADD(sum[k], (vx[r] - vx[l] + mod) * s % mod); //here too ADD(add[k], s); } else { lazy_eval(k, l, r); addapp(a, b, s, k * 2 + 1, l, (l + r) / 2); addapp(a, b, s, k * 2 + 2, (l + r) / 2, r); sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod; } } void mulapp(int a, int b, ll s, int k, int l, int r) { if(b <= l || r <= a) return; if(a <= l && r <= b) { MUL(sum[k], s); //here too MUL(add[k], s); MUL(mul[k], s); MUL(fib[k], s); } else { lazy_eval(k, l, r); mulapp(a, b, s, k * 2 + 1, l, (l + r) / 2); mulapp(a, b, s, k * 2 + 2, (l + r) / 2, r); sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod; } } void fibapp(int a, int b, ll s, int k, int l, int r) { if(b <= l || r <= a) return; if(a <= l && r <= b) { ADD(sum[k], (F[vx[r]] - F[vx[l]] + mod) * s % mod); ADD(fib[k], s); } else { lazy_eval(k, l, r); fibapp(a, b, s, k * 2 + 1, l, (l + r) / 2); fibapp(a, b, s, k * 2 + 2, (l + r) / 2, r); sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod; } } ll ga(int a, int b, int k, int l, int r) { if(b <= l || r <= a) return ll(); if(a <= l && r <= b) return sum[k]; else { lazy_eval(k, l, r); ll lv = ga(a, b, k * 2 + 1, l, (l + r) / 2); ll rv = ga(a, b, k * 2 + 2, (l + r) / 2, r); return (lv + rv) % mod; } } void show() { vector<ll> tmp; rep(i, 0, n) tmp.push_back(get(i, i + 1)); debug(tmp); } ll get(int a, int b) { return ga(a, b, 0, 0, n); } //[a, b) void addupdate(int a, int b, ll s) { addapp(a, b, s, 0, 0, n); } //[a, b) void mulupdate(int a, int b, ll s) { mulapp(a, b, s, 0, 0, n); } //[a, b) void fibupdate(int a, int b, ll s) { fibapp(a, b, s, 0, 0, n); } //[a, b) };
https://yukicoder.me/problems/no/255
前の問題のsegtreeをそのまま使えます。