基本 バブルソートの交換回数=転倒数 転倒数はBITを使って簡単に求められます（BITは区間和をO(logN)で求められるデータ構造です）。以下そのアルゴリズムを述べます。 与えられた数列xの要素を左から順番に見ていくことにして、要素a, b(a

はじめに 先日のABC159で無事黄色になることができたので、いわゆる色変記事を書こうと思います。 黄色になりました！！！！！！！！！！ pic.twitter.com/9BO5Zo0LqN— まさよし＠今日も１日１AC (@masayoshi361) March 22, 2020 やったこと AtCoderを始める…

部分木のサイズに比例する大きさのdpテーブルをマージしていくタイプのDPの計算量はO(n2) void dfs(int v, int p){ sz[v] = 1; dp[v] = {INF, s[v]}; for(auto &nv:g[v]){ if(nv == p) continue; dfs(nv, v); vl merged(sz[v]+sz[nv]+1, INF); rep(i, sz[v]+…

こんな感じで書けばいいと思うよ //n = 桁数 //k = 状態数(余りか最後の桁が多い) vector<mat<ll>> dp(n+1, mat<ll>(k, vl(2))); dp[0][0][1] = 1;//0桁の時 rep(i, n)rep(j, k){ rep(d, 10){ dp[i+1][f(j ,d)][0] += dp[i][j][0];//前の状態がdp[i][j][0]でi+1桁目をdに</ll></mat<ll>…