乱択
https://codeforces.com/blog/entry/61587 の必要なところのメモ
乱数生成
rand()
乱数生成の質が微妙なのでやめよう
こどふぉだと最大値が32767しかないのでさらにまずい
mt19937
C++11以上で追加された機能でメルセンヌツイスターで乱数を生成する
- 高速
- 最大値が2³¹-1
- 乱数の質もいい
64bitの乱数がほしいならmt19937_64を使うとできる
乱数のseedが他人にバレるとまずい
chrono::steady_clock::now().time_since_epoch().count()
とか
(uint64_t) new char
とかを使おう
一様乱数の生成
rand() % 1000 → 一様にならないのでだめ
uniform_int_distribution → これを使おう
配列のシャッフル
random_shuffle → 内部でrandを使ってるのでやめよう
shuffle → こっちを使おう
一様乱数を生成するコード
struct dice { mt19937 mt; dice() : mt(chrono::steady_clock::now().time_since_epoch().count()) {} // [0, x)の一様乱数 ll operator()(ll x) { return this->operator()(0, x - 1); } // [x, y]の一様乱数 ll operator()(ll x, ll y) { uniform_int_distribution<ll> dist(x, y); return dist(mt); } } rnd; int main() { cout << rnd(100) << endl; cout << rnd(30, 80) << endl; }
rand()をどうやって落とす?
Codeforces Round #539 (Div. 2) F. Sasha and Interesting Fact from Graph Theory
解法
頂点a,bを結ぶパスの辺をe本と固定したときの組み合わせ数を求める。まずn-2個の頂点からパス上のe-1個の頂点を選ぶ方法がP(n-2, e-1)通りである。次にパス上の辺の重みを決定する方法について考える。mをe分割する方法はm個のボールの間(m-1個)にe-1個の仕切りを入れると考えることができC(m-1, e-1)通りである。
パス以外の辺の重みは自由に決められるのでm^(n-1-e)通りである。ラベルつきの森が何通りあるか求めるにはCayley's_formulaを用いればよい。頂点数n、連結成分数kの森はk*n^(n-1-k)通りである。今回の条件設定に当てはめると(e+1)*n^(n-2-e)通りである。e=n-1のときに注意。
まとめると辺数がeのときP(n-2,e-1)*C(m-1,e-1)*m^(n-1-e)*(e+1)*n^(n-2-e)通りとなる。これを1<=e<=n-1について足せばよい。
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; template<ll MOD> struct modint { ll x; modint(): x(0) {} modint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {} ll get() const { return x; } // e乗 modint pow(ll e) { ll a = 1, p = x; while(e > 0) { if(e%2 == 0) {p = (p*p) % MOD; e /= 2;} else {a = (a*p) % MOD; e--;} } return modint(a); } ll extgcd(ll a, ll b, ll &x, ll &y) { ll g = a; x = 1, y = 0; if(b != 0) g = extgcd(b, a%b, y, x), y -= (a/b) * x; return g; } modint inv() { ll s, t; extgcd(x, MOD, s, t); return modint(s); } // Comparators bool operator <(modint b) { return x < b.x; } bool operator >(modint b) { return x > b.x; } bool operator<=(modint b) { return x <= b.x; } bool operator>=(modint b) { return x >= b.x; } bool operator!=(modint b) { return x != b.x; } bool operator==(modint b) { return x == b.x; } // increment, decrement modint operator++() { x++; return *this; } modint operator++(signed) { modint t = *this; x++; return t; } modint operator--() { x--; return *this; } modint operator--(signed) { modint t = *this; x--; return t; } // Basic Operations modint &operator+=(modint that) { x += that.x; if(x >= MOD) x -= MOD; return *this; } modint &operator-=(modint that) { x -= that.x; if(x < 0) x += MOD; return *this; } modint &operator*=(modint that) { x = (ll)x * that.x % MOD; return *this; } modint &operator/=(modint that) { x = (ll)x * that.inv().x % MOD; return *this; } modint &operator%=(modint that) { x = (ll)x % that.x; return *this; } modint operator+(modint that) const { return *this += that; } modint operator-(modint that) const { return *this -= that; } modint operator*(modint that) const { return *this *= that; } modint operator/(modint that) const { return *this /= that; } modint operator%(modint that) const { return *this %= that; } }; using mint = modint<1000000007>; // Input/Output ostream &operator<<(ostream& os, mint a) { return os << a.x; } istream &operator>>(istream& is, mint &a) { return is >> a.x; } ll binpow(ll x, ll e) { ll ret = 1, p = x; while(e > 0) { if(e&1) {(ret *= p) %= MOD; e--;} else {(p *= p) %= MOD; e /= 2;} } return ret; } template<bool bigN=false> ll combi(ll N_, ll K_, ll mo=MOD) { const int NUM_=1e6+10; static ll fact[NUM_+1]={},factr[NUM_+1]={},inv[NUM_+1]={}; auto binpow = [&](ll x, ll e) -> ll { ll a = 1, p = x; while(e > 0) { if(e%2 == 0) {p = (p*p) % mo; e /= 2;} else {a = (a*p) % mo; e--;} } return a; }; if (fact[0]==0) { fact[0] = factr[0] = inv[0] = 1; FOR(i, 1, NUM_+1) fact[i] = fact[i-1] * i % MOD; factr[NUM_] = binpow(fact[NUM_], mo-2); for(int i=NUM_-1; i>=0; --i) factr[i] = factr[i+1] * (i+1) % MOD; // bigNがないならいらない // REP(i, NUM_+1) inv[i] = binpow(i, MOD-2); } if(K_<0 || K_>N_) return 0; // 前計算 O(max(N,K)) クエリ O(1) if(!bigN) return factr[K_]*fact[N_]%MOD*factr[N_-K_]%MOD; // Nが大きいけどKが小さい場合に使う 前計算 O(Klog(mod)) クエリ O(K) ll ret = 1; for(;K_>0;N_--,K_--) (ret *= N_%MOD) %= MOD, (ret *= inv[K_]) %= MOD; return ret; } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n, m, a, b; cin >> n >> m >> a >> b; mint ret = 0, fact = 1; FOR(e, 1, n) { mint tmp = fact; tmp *= combi(m-1, e-1); tmp *= binpow(m, n-1-e); if(e != n-1) { tmp *= e+1; tmp *= binpow(n, n-2-e); } fact *= n-e-1; ret += tmp; } cout << ret << endl; return 0; }
エクサウィザーズ 2019 E - Black or White
考えたこと
- i回目までに両方ある/白しかない/黒しかない確率をそれぞれ求めたい
- これがわかればi回目の答えは (両方ある確率)/2 + (黒しかない確率) になるので解ける
- 黒しかないを知るには黒がj個あるがわかるとよさそう
- dp[i番目][黒がj個] = 確率 をやろうとする
- どうがんばってもインラインDPにはならない
- 確率を直接求めてみる
- 両方ある確率を求めるより白しかない/黒しかない確率を求めた方が楽そう
- 白しかない→i回目までに黒をB個取った
- i<Bならありえないので0
- それ以外なら C(i,B) (1/2)^i とかになりそう
- 黒しかないのも同様
- 書いてみるとサンプルが合わない
- i回目以前ですでに白/黒だけになってる分がおかしい
- 白/黒だけになったらそれ以降はずっと同じ操作をするので変わらない
- sum_{j=0}^i C(j-1,B-1) (1/2)^i でよさそう
- O(B+W)で求められるので解けた
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; struct mint { ll x; mint(): x(0) { } mint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {} ll get() const { return x; } // e乗 mint pow(ll e) { ll a = 1, p = x; while(e > 0) { if(e%2 == 0) {p = (p*p) % MOD; e /= 2;} else {a = (a*p) % MOD; e--;} } return mint(a); } // Comparators bool operator <(mint b) { return x < b.x; } bool operator >(mint b) { return x > b.x; } bool operator<=(mint b) { return x <= b.x; } bool operator>=(mint b) { return x >= b.x; } bool operator!=(mint b) { return x != b.x; } bool operator==(mint b) { return x == b.x; } // increment, decrement mint operator++() { x++; return *this; } mint operator++(signed) { mint t = *this; x++; return t; } mint operator--() { x--; return *this; } mint operator--(signed) { mint t = *this; x--; return t; } // Basic Operations mint &operator+=(mint that) { x += that.x; if(x >= MOD) x -= MOD; return *this; } mint &operator-=(mint that) { x -= that.x; if(x < 0) x += MOD; return *this; } mint &operator*=(mint that) { x = (ll)x * that.x % MOD; return *this; } mint &operator/=(mint that) { x = (ll)x * that.pow(MOD-2).x % MOD; return *this; } mint &operator%=(mint that) { x = (ll)x % that.x; return *this; } mint operator+(mint that) const { return mint(*this) += that; } mint operator-(mint that) const { return mint(*this) -= that; } mint operator*(mint that) const { return mint(*this) *= that; } mint operator/(mint that) const { return mint(*this) /= that; } mint operator%(mint that) const { return mint(*this) %= that; } }; // Input/Output ostream &operator<<(ostream& os, mint a) { return os << a.x; } istream &operator>>(istream& is, mint &a) { return is >> a.x; } template<bool bigN=false> ll combi(ll N_, ll K_, ll mo=MOD) { const int NUM_=5e5; static ll fact[NUM_+1]={},factr[NUM_+1]={},inv[NUM_+1]={}; auto binpow = [&](ll x, ll e) -> ll { ll a = 1, p = x; while(e > 0) { if(e%2 == 0) {p = (p*p) % mo; e /= 2;} else {a = (a*p) % mo; e--;} } return a; }; if (fact[0]==0) { fact[0] = factr[0] = inv[0] = 1; FOR(i, 1, NUM_+1) fact[i] = fact[i-1] * i % MOD; factr[NUM_] = binpow(fact[NUM_], mo-2); for(int i=NUM_-1; i>=0; --i) factr[i] = factr[i+1] * (i+1) % MOD; // bigNがないならいらない // REP(i, NUM_+1) inv[i] = binpow(i, MOD-2); } if(K_<0 || K_>N_) return 0; // 前計算 O(max(N,K)) クエリ O(1) if(!bigN) return factr[K_]*fact[N_]%MOD*factr[N_-K_]%MOD; // Nが大きいけどKが小さい場合に使う 前計算 O(Klog(mod)) クエリ O(K) ll ret = 1; for(;K_>0;N_--,K_--) (ret *= N_%MOD) %= MOD, (ret *= inv[K_]) %= MOD; return ret; } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll b, w; cin >> b >> w; mint prob1_a = 0, prob2_a = 0; REP(i, b+w) { // 白しかない mint prob1; if(i < b) prob1 = 0; else prob1 = (mint(1) / 2).pow(i) * combi(i-1, b-1); prob1_a += prob1; // 黒しかない mint prob2; if(i < w) prob2 = 0; else prob2 = (mint(1) / 2).pow(i) * combi(i-1, w-1); prob2_a += prob2; // 両方ある mint prob3 = mint(1) - prob1_a - prob2_a; mint ret = prob2_a + prob3 / 2; cout << ret << endl; } return 0; }
エクサウィザーズ 2019 D - Modulo Operations
考えたこと
- sの順列でX%s_1%s_2%s_3…を求める
- 制約を見るとDPをしてくださいと言っている
- dp[i番目][modがj]みたいなの
- 挿入DP?みたいな感じになりそうだけど遷移がやばそう
- ここでmodの性質を思い出すとmod xをしたあとにmod y(y >= x)をしても値は変わらない
- sをソートしておくとよさそう
- 昇順ソートして考えるけどi番目を順列の先頭に入れるみたいになって嬉しくない
- 降順ソートすれば順列の最後に入るのでよさそう
- dp[k][j%a[i]] += dp[i][j] (i<k) に遷移すれば書けるけど明らかにTLE
- i番目が値に影響しないときの遷移を入れればいい
- 使わない場合a[i]を順列の後ろのどこかに挿入する
- 挿入する場所はn-1-i通りあるので dp[i+1][j] += dp[i][j] * (n-1-i) とかける
- 使う場合も前一箇所だけ見ればよくなるので dp[i+1][j%s[i]] += dp[i][j] でかける
- 遷移がO(1)なので間に合う
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; struct mint { ll x; mint(): x(0) { } mint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {} ll get() const { return x; } // e乗 mint pow(ll e) { ll a = 1, p = x; while(e > 0) { if(e%2 == 0) {p = (p*p) % MOD; e /= 2;} else {a = (a*p) % MOD; e--;} } return mint(a); } // Comparators bool operator <(mint b) { return x < b.x; } bool operator >(mint b) { return x > b.x; } bool operator<=(mint b) { return x <= b.x; } bool operator>=(mint b) { return x >= b.x; } bool operator!=(mint b) { return x != b.x; } bool operator==(mint b) { return x == b.x; } // increment, decrement mint operator++() { x++; return *this; } mint operator++(signed) { mint t = *this; x++; return t; } mint operator--() { x--; return *this; } mint operator--(signed) { mint t = *this; x--; return t; } // Basic Operations mint &operator+=(mint that) { x += that.x; if(x >= MOD) x -= MOD; return *this; } mint &operator-=(mint that) { x -= that.x; if(x < 0) x += MOD; return *this; } mint &operator*=(mint that) { x = (ll)x * that.x % MOD; return *this; } mint &operator/=(mint that) { x = (ll)x * that.pow(MOD-2).x % MOD; return *this; } mint &operator%=(mint that) { x = (ll)x % that.x; return *this; } mint operator+(mint that) const { return mint(*this) += that; } mint operator-(mint that) const { return mint(*this) -= that; } mint operator*(mint that) const { return mint(*this) *= that; } mint operator/(mint that) const { return mint(*this) /= that; } mint operator%(mint that) const { return mint(*this) %= that; } }; // Input/Output ostream &operator<<(ostream& os, mint a) { return os << a.x; } istream &operator>>(istream& is, mint &a) { return is >> a.x; } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n, x; cin >> n >> x; vector<ll> s(n); REP(i, n) cin >> s[i]; sort(ALL(s), greater<>()); auto dp = make_v<mint>(n+1, 100001); dp[0][x] = 1; REP(i, n) REP(j, 100001) { dp[i+1][j%s[i]] += dp[i][j]; dp[i+1][j] += dp[i][j] * (n-1-i); } mint ret = 0; REP(i, 100001) ret += dp[n][i] * i; cout << ret << endl; return 0; }
エクサウィザーズ 2019 C - Snuke the Wizard
考えたこと
- i番目にいた人が消える条件は何か?で考えるけどまともな形にならない
- 方針転換して二分探索をすることにする
- 消える人数を固定したところで何も嬉しくない
- i番目が左に消えるときi-1番目も左に消えることに気がつく
- 単調性があるので二分探索ができる
- 判定にO(Q)かけていいのでこれは解けた
自分の二分探索のlb,ubの境界の決め方
条件が真であるときにlb=midなのかub=midなのか考える
前者なら[lb,ub)、後者なら(lb,ub]として扱う
初期値を区間に入ってる方は有効な値のぎりぎり、入ってない方は有効な値の外側になるようにする
解候補の範囲の外でも判定がちゃんと動くなら入ってない方を適当な値にしても動くので思考がサボれる
答えは前者ならlb,後者ならub
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n, q; cin >> n >> q; string s; cin >> s; vector<char> t(q), d(q); REP(i, q) cin >> t[i] >> d[i]; ll a, b; { auto check = [&](ll mid) { ll idx = mid; REP(i, q) { if(s[idx] == t[i]) { if(d[i]=='L') idx--; else idx++; if(idx < 0) return true; } } return false; }; ll lb=-1, ub=n; while(ub-lb > 1) { ll mid = (lb+ub)/2; if(check(mid)) lb = mid; else ub = mid; } a = lb; } { auto check = [&](ll mid) { ll idx = mid; REP(i, q) { if(s[idx] == t[i]) { if(d[i]=='L') idx--; else idx++; if(idx >= n) return true; } } return false; }; ll lb=-1, ub=n; while(ub-lb > 1) { ll mid = (lb+ub)/2; if(check(mid)) ub = mid; else lb = mid; } b = ub; } if(b <= a) { cout << 0 << endl; } else { cout << b-a-1 << endl; } return 0; }
Codeforces Round #548 (Div. 2) D. Steps to One
考えたこと
- gcd=gと決め打つと長さの期待値が割と簡単に求まる気がする
- 長さnの確率は (gの倍数の確率)^(n-1) * (gの倍数以外の確率) っぽい
- g=2,3 の両方で 6, 6, 6, 6,…, 1みたいなのを重複して数えてる
- 約数系包除で数えられそう
- 期待値をちゃんと求める
- m以下のgの倍数の個数をcntとする
- 期待値 = sum_{n=1}^{無限} n * (cnt/m)^(n-1) * (1-cnt/m)
- 公比掛けて引くやつでこのsumは求まる
- 整理すると期待値 = m/(m-cnt)
- gの倍数の分を余計に数えてるので dp[g] -= dp[gの倍数] とする
- 調和級数でO(mlogm)なので間に合いそう
- sample3が1ずれてる
- 実装が間違ってるのかと思って手計算するけど手計算もサンプルとずれてる
- 何が間違ってるのかよくわからない
-----コンテスト終わり----- - 期待値計算でn=1のときの確率が1-cnt/mとなっているが正しくは1/m
- ここの値をちゃんと直すと通った
この立式のn=1がコーナーになってるの全く気づけませんが… 立式パートでやたら式変形に時間を溶かしたのだめ
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<typename T> istream& operator >> (istream& is, vector<T>& vec){ for(T& x: vec) {is >> x;} return is; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; struct mint { ll x; mint(): x(0) { } mint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {} ll get() const { return x; } // e乗 mint pow(ll e) { ll a = 1, p = x; while(e > 0) { if(e%2 == 0) {p = (p*p) % MOD; e /= 2;} else {a = (a*p) % MOD; e--;} } return mint(a); } // Comparators bool operator <(mint b) { return x < b.x; } bool operator >(mint b) { return x > b.x; } bool operator<=(mint b) { return x <= b.x; } bool operator>=(mint b) { return x >= b.x; } bool operator!=(mint b) { return x != b.x; } bool operator==(mint b) { return x == b.x; } // increment, decrement mint operator++() { x++; return *this; } mint operator++(signed) { mint t = *this; x++; return t; } mint operator--() { x--; return *this; } mint operator--(signed) { mint t = *this; x--; return t; } // Basic Operations mint &operator+=(mint that) { x += that.x; if(x >= MOD) x -= MOD; return *this; } mint &operator-=(mint that) { x -= that.x; if(x < 0) x += MOD; return *this; } mint &operator*=(mint that) { x = (ll)x * that.x % MOD; return *this; } mint &operator/=(mint that) { x = (ll)x * that.pow(MOD-2).x % MOD; return *this; } mint &operator%=(mint that) { x = (ll)x % that.x; return *this; } mint operator+(mint that) const { return mint(*this) += that; } mint operator-(mint that) const { return mint(*this) -= that; } mint operator*(mint that) const { return mint(*this) *= that; } mint operator/(mint that) const { return mint(*this) /= that; } mint operator%(mint that) const { return mint(*this) %= that; } }; // Input/Output ostream &operator<<(ostream& os, mint a) { return os << a.x; } istream &operator>>(istream& is, mint &a) { return is >> a.x; } ll binpow(ll x, ll e) { ll ret = 1, p = x; while(e > 0) { if(e&1) {(ret *= p) %= MOD; e--;} else {(p *= p) %= MOD; e /= 2;} } return ret; } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll m; cin >> m; if(m == 1) { cout << 1 << endl; return 0; } vector<mint> dp(m+1); for(ll i=m; i>=2; --i) { ll cnt = m / i; dp[i] = mint(m) / (m-cnt); dp[i] -= mint(m - cnt) / m; for(ll j=2*i; j<=m; j+=i) { dp[i] -= dp[j]; } } mint ret = mint(1) / m; FOR(i, 2, m+1) ret += dp[i]; cout << ret << endl; return 0; }
FII Code Round #1 Sugarel in Love
解法
dp[i][j] = (頂点i以下の部分木で使用したパスにおいて頂点iの次数がjのときの最大値) としてdpする。(頂点vの部分木において)頂点vを端点とする辺を使用しない場合、子の部分木はどのような選び方をしていたとしても問題ないため遷移は dp[v][0] = sum(max(dp[child[v]][j])) となる。
頂点vの子の頂点aとの辺を利用したとすると頂点aの分の距離はdp[a][1]+(辺v-aの重み)で頂点a以外の他の子bの分はsum(max(dp[b][j]))となる。頂点vに隣接した辺を使わない場合から辺v-aを使った場合に変化させたとき、dpの値の変化はdp[a][1] + (辺v-aの重み) - max(dp[a][i])となる。この変化する値が大きい上位2つを保持することでつなげるべき辺を求めることができdpの更新を行うことができる。
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<typename T> istream& operator >> (istream& is, vector<T>& vec){ for(T& x: vec) {is >> x;} return is; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 998244353; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; vector<vector<PII>> g(n); REP(i, n-1) { ll x, y, z; cin >> x >> y >> z; x--, y--; g[x].push_back({y, z}); g[y].push_back({x, z}); } vector<vector<ll>> dp(n, vector<ll>(3)); function<void(ll,ll)> dfs = [&](ll v, ll p) { ll ma1 = 0, ma2 = 0, su = 0; for(auto to: g[v]) { if(to.first == p) continue; dfs(to.first, v); ll mx = max({dp[to.first][0], dp[to.first][1], dp[to.first][2]}); su += mx; if(ma1 < dp[to.first][1] + to.second - mx) { ma2 = ma1; ma1 = dp[to.first][1] + to.second - mx; } else if(ma2 < dp[to.first][1] + to.second - mx) { ma2 = dp[to.first][1] + to.second - mx; } } dp[v][0] = su; dp[v][1] = ma1 + su; dp[v][2] = ma1 + ma2 + su; }; dfs(0, -1); cout << max({dp[0][0], dp[0][1], dp[0][2]}) << endl; return 0; }