yukicoder埋め

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をそのまま使えます。