D Madoka and The Corruption Scheme

我們可以將所有的比賽看成有 $2^n$ 個(gè)葉子節(jié)點(diǎn)的二叉樹
問題轉(zhuǎn)換為對(duì)每個(gè)非葉子結(jié)點(diǎn)規(guī)定左/右兒子贏，并規(guī)定葉子節(jié)點(diǎn)編號(hào)
使得在修改k個(gè)非葉子節(jié)點(diǎn)的狀態(tài)后最后贏家編號(hào)最小
那么我們可以先約定每個(gè)非葉子節(jié)點(diǎn)的左兒子贏
從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)經(jīng)過n條邊
我們規(guī)定從當(dāng)前節(jié)點(diǎn)走向左兒子代表一個(gè)字符‘L’
另一邊為字符‘R’
那么每個(gè)葉子節(jié)點(diǎn)代表一個(gè)LR序列
如果想要一個(gè)葉子節(jié)點(diǎn)成為最后贏家，那么我們需要修改所有R的位置
那么代表葉子結(jié)點(diǎn)的修改權(quán)值為R的數(shù)量
如果修改次數(shù)為k，那么所有LR序列中R的數(shù)量小于等于k的都可以成為最后贏家
LR序列中R的個(gè)數(shù)為 $i$ 的有 $C_n^i$ 個(gè)
那么我們貪心的對(duì)修改權(quán)值從小到大的放入1到$2^n$
答案即為 $\sum _{i=0}^k{C}_n^i$

PS:

賽時(shí)其實(shí)是畫二叉樹找規(guī)律找出來的，本來是想貪心的構(gòu)造一個(gè)序列
但是在計(jì)算了一下每個(gè)葉子節(jié)點(diǎn)的權(quán)值時(shí)發(fā)現(xiàn)了經(jīng)典組合數(shù) $1331$
之后粘了個(gè)組合數(shù)板子就秒了，啟發(fā)就是以后可以計(jì)算節(jié)點(diǎn)地位或者說節(jié)點(diǎn)的權(quán)值
然后放置編號(hào)，那么思路會(huì)明確的多

ll n, m, k;namespace cnm {const int FN = 1e5 + 5;ll fac[FN];//階乘數(shù)組ll ifc[FN];//階乘逆元ll inv[FN];//逆元void init(int n){fac[0] = fac[1] = ifc[0] = ifc[1] = inv[1] = 1;rep(i, 2, n){fac[i] = fac[i - 1] * i % mod;inv[i] = (mod - mod / i) * inv[mod % i] % mod;ifc[i] = ifc[i - 1] * inv[i] % mod;}}ll A(ll n, ll m){ return fac[n] * ifc[n - m] % mod; }ll C(ll n, ll m){if (n < m) return 0;return fac[n] * ifc[m] % mod * ifc[n - m] % mod;}ll lucas(ll n,ll m)//當(dāng)n,m超過1e5,mod比較小時(shí){if (n < mod && m < mod) return C(n, m);return (C(n % mod, m % mod) * lucas(n / mod, m / mod)) % mod;} } using cnm::C; using cnm::A; using cnm::lucas; using cnm::fac; using cnm::ifc; using cnm::inv;void solve() {cin >> n >> k;if (k >= n) cout << ksm(2ll, n, mod) << endl;else{cnm::init(n);ll ans = 0;rep(i, 0, k) ans = (ans + C(n, i)) % mod;cout << ans << endl;} }

E Madoka and The Best University

這題賽時(shí)沒過，賽后補(bǔ)的
一開始不會(huì)歐拉篩，先去學(xué)了下歐拉篩
題目是求$\sum _{a+b+c=n}lcm(c,gcd(a,b))$
首先看題解我們知道了 $gcd(a,b)=gcd(a,a+b)=gcd(a,n?c)$
我們?cè)O(shè) $gcd(a,n?c)=d$，那么 $gcd(\frac{a}{d},\frac{n?c}{d})=1$
因?yàn)?$a+b=n?c$，所以 $\frac{a}{d}<\frac{n?c}{d}$ 并且 $\frac{a}{d}$ 與 $\frac{n?c}{d}$ 互質(zhì)
即 $\frac{a}{d}$ 的數(shù)量為歐拉函數(shù) $?(\frac{n?c}{d})$ （歐拉函數(shù)定義）
而我們可以 $O(n)$ 求出 1 到 n 的歐拉函數(shù) （歐拉篩）
但是如果我們?nèi)绻杜e $c$，再質(zhì)因數(shù)分解 $n?c$
我們的復(fù)雜度為 $O(n\sqrt{n}logn)$ ($logn$為$gcd$的復(fù)雜度)
但如果我們枚舉 $d$，再枚舉 $n?c$ ($n?c$為$d$的倍數(shù))
我們的復(fù)雜度就降為 $O((nloglogn)logn)$
($logn$為$gcd$的復(fù)雜度，$nloglogn$為埃氏篩的復(fù)雜度)
特別要注意的是 $a<n?c$ 所以 $d$ 取不到 1
我們直接讓歐拉函數(shù) $phi[1]=0$ 即可（本來是等于1的）

ps:

感覺數(shù)學(xué)題中 $lcm$ 和 $gcd$ 很容易滿足積性函數(shù)的性質(zhì)
之后遇到類似的題目，如果沒有思路，可以猜測是否為積性函數(shù)

int n, m, k;bool np[N];//非質(zhì)數(shù) int p[N], pn;//質(zhì)數(shù) 質(zhì)數(shù)個(gè)數(shù) template<typename T> void get_f(int n, T f[]) {f[1] = 0;rep(i, 2, n){if (!np[i]) p[++pn] = i, f[i] = i - 1;rep(j, 1, pn){if (i * p[j] > n) break;np[i * p[j]] = true;if (i % p[j] == 0){f[i * p[j]] = f[i] * p[j];break;}f[i * p[j]] = f[i] * (p[j] - 1);}} }int phi[N];void solve() {cin >> n;get_f(n, phi);ll ans = 0;for (ll d = 1; d < n; d++){for (ll i = 1; i * d < n; i++){ll c = n - i * d;ans += c * d / gcd(c, d) * phi[i] % mod;ans %= mod;}}cout << ans << endl; }

F 大佬說是用網(wǎng)絡(luò)流過的，還沒學(xué)，留個(gè)坑

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #818 (Div. 2)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。