ARC101 E - Ribbons on Tree

問題

n(:偶数)頂点の木が与えられる
これらの頂点を端点を共有しないペアn/2組に分け、各ペアの2頂点間にリボンを張る
どの辺にも少なくとも1本のリボンが張られているようなペアの分け方は何通りあるか

2 <= n <= 5000

解法

f(S): Sのどの辺にもリボンが張られていないようなペアの分け方の個数
とすると、包除原理より答えは
Σ f(S) * (-1)^|S| (S: 与えられた木の辺の部分集合)
となる
ではf(S)は具体的にはどう求めれば良いか？

木からSの辺を全て取り除いて出来るグラフをGとする
このグラフは |S|+1 個の連結成分に分かれる
g(i): i番目の連結成分(サイズはk[i]とする)の各頂点をk[i]/2個のペアに分ける方法の個数
とすると、
k[i]が奇数のとき) g[i] = 0
k[i]が偶数のとき) g[i] = (k-1) * (k-3) * (k-5) * ... * 3 * 1
となり、f(S)は g[0] * g[1] * ... * g[|S|] である
あとは各Sについてこれらを足し合わせていけば解けるけど、Sを全通り (2^(n-1)通り) 試すわけにはいかないからうまく状態をまとめて計算する必要がある

dp[v][x][p]: 頂点vを根とする部分木において、vを含む連結成分の頂点数がxで、部分木内で取り除いた辺の本数の偶奇がpとなるようなペア分けの仕方の個数
これを木の葉から根に向かって更新していけばいい
頂点0を木の根とすると答えは Σ (dp[0][i][0] - dp[0][i][1]) (1 <= i <= n) となる

部分木同士のdpをマージするとき、xの値として[0,n]の範囲を毎回見ているとO(n^2)かかり、マージはn-1回行われるからトータルでO(n^3)になってしまう
でも実際はサイズがXの部分木のdpではxの上限はXまでで十分
よっていまマージしようとしている2個の部分木それぞれの頂点数がXとYであるとするとO(XY)でマージできる
こうするとトータルでO(n^2)になる
これは木dpではめちゃくちゃよく使うテクニックらしい

#define int long long

int n, x, y, dp[5050][5050][2], dp2[5050][2], sz[5050], g[5050], res;
vector<int> e[5050];

void rec(int v, int p) {
	sz[v] = 1, dp[v][1][0] = 1;
	each(i,e[v]) if (i!=p) {
		rec(i,v);
		memset(dp2,0,sizeof(dp2));
		reps(x,1,sz[v]+1) reps(y,1,sz[i]+1) {
			// v-i間の辺を取り除く場合
			(dp2[x][0] += dp[v][x][0]*dp[i][y][1]%mod*g[y] + dp[v][x][1]*dp[i][y][0]%mod*g[y]) %= mod;
			(dp2[x][1] += dp[v][x][0]*dp[i][y][0]%mod*g[y] + dp[v][x][1]*dp[i][y][1]%mod*g[y]) %= mod;
			// 取り除かない場合
			(dp2[x+y][0] += dp[v][x][0]*dp[i][y][0] + dp[v][x][1]*dp[i][y][1]) %= mod;
			(dp2[x+y][1] += dp[v][x][0]*dp[i][y][1] + dp[v][x][1]*dp[i][y][0]) %= mod;
		}
		swap(dp[v],dp2);
		sz[v] += sz[i];
	}
}

signed main() {
	g[2] = 1;
	reps(i,4,5050) g[i] = g[i-2]*(i-1) %mod;
	cin >> n;
	rep(i,n-1) {
		cin >> x >> y;
		x--, y--;
		e[x].push_back(y), e[y].push_back(x);
	}
	rec(0,-1);
	reps(i,1,n+1) (res += (dp[0][i][0]-dp[0][i][1])*g[i]) %= mod;
	(res += mod) %= mod;
	cout << res << endl;
}

ARC096 E - Everything on It

春に解説pdfを見ても全く意味がわからなくてずっと放置してて、さっき解説放送見たらやっと理解できた
700点とかの問題と比べると恐ろしいほどむずいけど勉強になる問題だった

問題

あるラーメン屋はn種類のトッピングを提供している
各トッピングは乗せるか乗せないかを選べて、2^n通りのラーメンが注文できる
ここで、
1) トッピングの組み合わせが全く同じラーメンを複数注文しない
2) n種類のトッピングそれぞれが注文したラーメンのうち2杯以上に乗っている
という2つの条件を満たすようにラーメンを何杯か注文したい
そのような注文の仕方の総数を求めよ

2 <= n <= 3000

解法

求めたいものは
「"n個の要素からなる集合S" の部分集合2^n個からなる集合Tの部分集合Uのうち、Sの全ての要素がUの2個以上の互いに異なる要素に属するようなものの個数」
と言い換えられる
(Uは 2^(2^n) 個存在する)
2個以上のグループに属するというのはあまりにも求めづらいので、
f(k): Sのうち1個以下のグループに属するような要素がk個以上存在するようなグループ分けの仕方の個数 (残りn-k個は何個のグループに属してもいい)
とし、包除原理を用いると、答えは
Σ nCk * f(k) * (-1)^k (0 <= k <= n)
となる

次にf(k)を求めたい
n-k個は何個のグループに属しててもいいから、グループへの入れ方は 2^(2^(n-k)) 通りある
グループがx個あるとして、
dp[k][x]: k個の要素を(各要素が1個以下のグループに属するように)x個のグループに分ける場合の数
とすると、x個のグループそれぞれがn-k個の要素のうちどれを含むかというのが 2^(n-k)x 通りあるから
f(k) = Σ dp[k][x] * 2^(n-k)x * 2^(2^(n-k)) (0 <= x <= k)
となる

今度はdp[k][x]を求めたい
これは第二種スターリング数ってのとめっちゃ似てて、↓の遷移で求められる
dp[k][x] = dp[k-1][x-1] + dp[k-1][x] + dp[k-1][x]*x
第1項) 新しいグループを作ってそこにk個目の要素を入れる場合
第2項) k個目の要素をどのグループにも入れない場合
第3項) 既にあるx個のグループのどれか1つにk個目の要素を入れる場合

全部トータルでO(n^2)

実装

フェルマーの小定理 2^(mod-1) % mod = 1 より、
2 ^ (2^(n-k))
= 2 ^ (mod-1) * 2 ^ (mod-1) * ... * 2 ^ (2^(n-k) % (mod-1))
= 2 ^ (2^(n-k) % (mod-1)) (mod mod)
と変形できる

#define int long long

int n, mod, dp[3030][3030], p[10010010], res;

ll mop(ll a,ll b,ll m=mod) {ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r;}

const int MAXS = 10010;
ll fact[MAXS+1], factr[MAXS+1], inv[MAXS+1];
ll comb(ll n, ll r) {
	if (fact[0]==0) {
		fact[0] = factr[0] = inv[1] = 1;
		for (int i=2; i<=MAXS; i++) inv[i] = inv[mod%i] * (mod-mod/i) %mod;
		for (int i=1; i<=MAXS; i++) fact[i] = fact[i-1]*i %mod, factr[i] = factr[i-1]*inv[i] %mod;
	}
	if (r<0 || n<r) return 0;
	return fact[n]*factr[r] %mod *factr[n-r] %mod;
}

int f(int k) {
	int ret = 0;
	rep(x,k+1) (ret += dp[k][x] * p[(n-k)*x] %mod) %= mod;
	return ret * mop(2,mop(2,n-k,mod-1)) %mod;
}

signed main() {
	cin >> n >> mod;
	dp[0][0] = 1;
	reps(i,1,n+1) rep(j,n+1) {
			if (j) (dp[i][j] += dp[i-1][j-1]) %= mod;
			(dp[i][j] += dp[i-1][j]*(j+1)) %= mod;
	}
	p[0] = 1;
	reps(i,1,10010010) p[i] = p[i-1]*2 %mod;
	rep(k,n+1) (res += comb(n,k) * f(k) * (k%2 ? -1 : 1) %mod + mod) %= mod;
	cout << res << endl;
}

SRM555 Div1 Easy - CuttingBitString

問題

長さnで '0' と '1' のみからなる文字列sが与えられる
これを2進数として見るとき、全ての部分列がleading-zeroなしで5の冪乗になるようにいくつかの部分列に分けたい
最小でいくつの部分列に分ける必要があるか求めよ
不可能な場合は-1

1 <= n <= 50

解法

s[L,r]の左端が0じゃなくて5の冪乗になってたら頂点Lから頂点r+1への辺を引く
これを全L,rでやって出来たグラフでdfs

class CuttingBitString {
public:
	vector<int> e[55];
	int d[55];

	void rec(int v, int dis) {
		d[v] = dis;
		each(i,e[v]) rec(i,dis+1);
	}

	int getmin(string s) {
		set<ll> p;
		ll t = 1;
		while (t<(1ll<<55)) p.insert(t), t *= 5;
		int n = s.size();
		rep(i,n) reps(j,i,n) if (s[i]!='0') {
			ll sum = 0;
			reps(k,i,j+1) sum <<= 1, sum |= s[k]-'0';
			if (p.count(sum)) e[i].push_back(j+1);
		}
		rep(i,55) d[i] = 1<<30;
		rec(0,0);
		return (d[n]==1<<30 ? -1 : d[n]);
	}
};

SRM554 Div1 Easy - TheBrickTowerEasyDivOne

問題

高さrhの赤いブロックがrc個、高さbhの青いブロックがbc個ある
これらのブロックを1個以上使い、同じ色のブロックが隣接しないように積み上げてタワーを作る
タワーの高さとしてあり得るものの個数を求めよ

1 <= rh, rc, bh, bc <= 5*10^8くらい

解法

(rh=bhのとき)
rc=bcのとき) 答えは明らかにrc*2通り
rc≠bcのとき) 個数が多い方の色のブロックを底にして交互に積むとmin(rc,bc)*2+1通り作れる

(rh≠bhのとき)
赤と青のブロック1個ずつのセットを何個積むかをベースにして考える
セットは最小0個、最大min(rc,bc)個積める
0個積むとき) 赤か青のどっちかを1個積めるから2通り
k (1 <= k <= min(rc,bc)-1) 個積むとき) 何も積まないか赤or青を1個積めるから3通り
min(rc,bc)個積むとき) 何も積まないのが1通り、rc≠bcなら余ってる方のブロックをもう1個積めるからもう1通り

class TheBrickTowerEasyDivOne {
public:
	int find(int rc, int rh, int bc, int bh) {
		if (rh==bh) return min(rc,bc)*2 + (rc!=bc);
		return min(rc,bc)*3 + (rc!=bc);
	}
};

SRM553 Div1 Easy - Suminator

問題

suminatorという装置がある
この装置には最初無限に0が詰まったスタックが入っており、長さnの非負整数のみからなる数列aを入れると、
1) 数列aの各要素を手前から1個ずつ見ていき、a[i]が0のときはスタックから2個取り出してそれらの和をスタックに入れ、a[i]が0でないときはa[i]をスタックに入れる
2) スタックから1個取り出してその値を出力する
という操作をする

1つの要素だけ-1になっていて他は全て非負整数の数列aと非負整数xが与えられる
-1を好きな非負整数pに変えて、suminatorにaを入れるとxが出力されるようにしたい
これが可能な場合はpの最小値を、不可能な場合は-1を返せ

1 <= n <= 50
-1 <= a[i] <= 10^9
1 <= x <= 10^9

解法

まずp=0を試してみる
それでxにならなかったらp=1とp=2を試してみる
p=1のときのsuminatorの出力をv、p=2のときをuとする
suminatorは非負整数の足し算しか行わないから、uとvの関係としては
1) v=u (pの値がsuminatorの結果に影響しない場合)
2) u=v+1 (そうでない場合)
という2通りしかあり得ない
1)の場合はv=xならreturn 1、そうでなければreturn -1
2)の場合はvが既にxを超えていたらpとして適切な値は存在しないからreturn -1、そうでなければreturn 1+x-v

class Suminator {
public:
	ll sumi(vector<int> &a) {
		stack<ll> st;
		each(i,a) {
			if (i!=0) st.push(i);
			else if (st.size()>=2) {
				ll a = st.top(); st.pop();
				ll b = st.top(); st.pop();
				st.push(a+b);
			}
		}
		return (st.empty() ? 0 : st.top());
	}

	int findMissing(vector<int> a, int x) {
		int id = find(all(a),-1) - a.begin();
		a[id] = 0;
		if (sumi(a)==x) return 0;
		a[id] = 1;
		ll v = sumi(a);
		a[id] = 2;
		ll u = sumi(a);
		if (v==u) return (v==x ? 1 : -1);
		return (x<v ? -1 : 1+x-v);
	}
};

SRM552 Div1 Easy - FoxPaintingBalls

これはどういうことですかね

問題

1辺の長さがnである正三角形を成すようにボールが並べられている (合計n(n+1)/2個)
このball triangleは無限にある
ball triangleのボールを全て赤or緑or青で、隣り合う2つのボールは違う色であるように塗りたい
赤緑青で塗れるボールの個数は最大でそれぞれr, g, bであるとき、最大で何個のball triangleを塗り切れるか

0 <= r, g, b <= 10^18
1 <= n <= 10^9

解法

同じ色が隣り合わないという制約より、ball triangleの塗り方は1頂点だけ決めると残りは一意に定まる
またp = n(n+1)/2とすると、使う色の個数は
n(or p)を3で割った余りが1のとき) 2色はp/3個で残りのもう1色はp/3+1個
そうでないとき) 3色ともp/3個
となる (∵ 1,2,3,...を3で割った余りは1,2,0,1,2,0,...と繰り返されるため和をとっていくと余りは0か1しかあり得ない)

↑を踏まえて二分探索する
m個のtriangleを塗るとすると、まずnの余りに関係なく3色それぞれpm/3回は塗る必要がある
nの余りが1のときはこれに加えてm回(独立に)塗る必要がある
残っている色の個数の総和とmの大小関係だけでこれが可能かは判断できる

(追記)
nの余りが1じゃないときは明らかに二分探索が要らなかった
まあ結果は変わらないから・・🧐💦

実装

オーバーフローに注意
pm/3がlonglongの上限を超えてたら引くまでもなく不可能とわかるからそこで終了していい

何も考えないで(le+ri)/2も避けたけど答えの上限が3e18だから別にそこは大丈夫だった

class FoxPaintingBalls {
public:
	ll theMax(ll r, ll g, ll b, int n) {
		ll p = (ll)n*(n+1)/2, le = 0, ri = 5e18;
		while (ri-le>1) {
			ll m = (le-ri)/2+ri, x = r, y = g, z = b, ok = 1;
			if (p/3*m/m!=p/3) ok = 0;
			x -= p/3*m, y -= p/3*m, z -= p/3*m;
			if (x<0 || y<0 || z<0) ok = 0;
			if (x+y+z<p%3*m) ok = 0;
			(ok ? le : ri) = m;
		}
		return le;
	}
};

ARC102 E - Stop. Otherwise...

問題

1〜kが等確率で出るk面サイコロをn個振る
2 <= i <= 2kに対して、どの異なる2つのサイコロの出目の和もiにならないような出目の組の場合の数を求めよ
ただしサイコロ同士は区別しない

1 <= k <= 2000
2 <= n <= 2000

解法

どの2つの出目の和もtにならない組の個数を求めたい
これは a+b = t となる各(a,b)について、どちらか一方が現れない or 両方とも現れなければいい
(ただしtが偶数のときはk/2が1個以下しか現れないという条件も付く)
(a,b)の組の個数をxとし、どちらか一方が現れる組の個数をyとすると、答えは
(xからy個取る組み合わせの数) * (y組それぞれでどちらの数が現れるようにするか) * (残りn-y個の出目をk-2x+y個から重複を許して選ぶ組み合わせの数)
だけ増える (tが奇数のとき)
tが偶数でもk/2が0個現れる場合と1個現れる場合で2通り考えるだけ
これを1 <= y <= xの全てのyでやればいい

実装

comb(n,r): nCr
hcomb(n,r): nHr

signed main() {
	p[0] = 1;
	reps(i,1,2020) p[i] = p[i-1]*2 %mod;
	cin >> k >> n;
	reps(i,2,k*2+1) {
		ll x = 0, res = 0;
		reps(a,1,k+1) if (a<i-a && i-a<=k) x++;
		rep(y,x+1) {
			if (i%2==0) (res += comb(x,y)*p[y] %mod *(hcomb(k-x*2-1+y,n-y) + hcomb(k-x*2-1+y,n-y-1)) %mod) %= mod;
			else (res += comb(x,y)*p[y] %mod *hcomb(k-x*2+y,n-y) %mod) %= mod;
		}
		cout << res << endl;
	}
}