題目鏈接

https://atcoder.jp/contests/agc032/tasks/agc032_f

題解

神仙題。。
第一步轉(zhuǎn)化利用了\(\frac{1}{3}\)這個(gè)數(shù)特有的性質(zhì)。假設(shè)我們用紅線標(biāo)出每一次切割的位置，再在每一次切割的位置順時(shí)針\(120\)度處用藍(lán)線標(biāo)出，那么答案就等于紅線與藍(lán)線之間的最小夾角。但是這樣轉(zhuǎn)化完了依然不好做(而且似乎也沒(méi)用到\(\frac{1}{3}\)的特殊性)，那么考慮如果在每一次切割的位置逆時(shí)針\(120\)度處用綠線標(biāo)出，答案依然是不變的，因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(|x-\frac{1}{3}|=|(1-x)-\frac{2}{3}|\). 那樣我們就相當(dāng)于將整個(gè)圓周分成了\(3\)等份(每一等份記作\(\frac{1}{3}\))，考慮其中的一份，每次在其中隨機(jī)一個(gè)位置隨機(jī)三種顏色中的一種畫(huà)上線(初始時(shí)在\(0\)處有一條紅線\(\frac{1}{3}\)處有一條藍(lán)線)，答案等于不同顏色之間最短距離的期望。
不算首尾一共撒了\((n-1)\)個(gè)點(diǎn)，將\([0,\frac{1}{3}]\)分成了\(n\)份。考慮如何算兩端為不同顏色的份(下稱“不同色段”)的最短長(zhǎng)度的期望。
首先考慮一個(gè)弱化版問(wèn)題: 沒(méi)有顏色的限制，用\((k-1)\)個(gè)點(diǎn)把\([0,1]\)分成\(k\)份，最小的一份的期望長(zhǎng)度。考慮答案大于等于\(t\)的概率，也就相當(dāng)于\(n\)個(gè)隨機(jī)實(shí)數(shù)和為\(1-kt\)的概率除以\(n\)個(gè)隨機(jī)實(shí)數(shù)和為\(1\)的概率，也就是\((n-1)\)個(gè)隨機(jī)實(shí)數(shù)和不超過(guò)\(1-kt\)的概率除以\((n-1)\)個(gè)隨機(jī)實(shí)數(shù)和不超過(guò)\(1\)的概率，顯然等于\((1-kt)^{k-1}\). 那么對(duì)其進(jìn)行積分，\(\int^\frac{1}{k}_0(1-kt)^{k-1}\textze8trgl8bvbqt=\frac{1}{k}\int^1_0(1-t)^{k-1}dt=\frac{1}{k}\int^1_0t^{k-1}\textze8trgl8bvbqt=\frac{1}{k^2}\). 并且把\([0,1]\)換成\([0,L]\)推一下可知答案關(guān)于\(L\)是線性的，即\(\frac{L}{k^2}\).
對(duì)于有顏色限制的情況，考慮枚舉不同色段的個(gè)數(shù)，分成兩部分：(1)出現(xiàn)這種情況的概率；(2)在這種情況下答案的期望。對(duì)于(2)，顯然不同色段的總長(zhǎng)度期望為\(\frac{k}{3n}\), 因?yàn)樯厦鎲?wèn)題的答案關(guān)于總長(zhǎng)度是線性的，因此答案的期望即為\(\frac{1}{3nk}\)。對(duì)于(1)，可以用一個(gè)DP乘以組合數(shù)來(lái)求出，DP不同色段的個(gè)數(shù)，組合數(shù)插入同色段。
總時(shí)間復(fù)雜度\(O(n)\).

代碼

#include<bits/stdc++.h> #define llong long long using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int N = 1e6; const llong P = 1e9+7; const llong INV3 = 333333336ll; llong fact[N+3],finv[N+3];llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++) {if(y&(1ll<<i)) {ret = ret*cur%P; y-=(1ll<<i);} cur = cur*cur%P;}return ret; } llong comb(llong x,llong y) {return x<0||y<0||x<y?0ll:fact[x]*finv[y]%P*finv[x-y]%P;}llong f[N+3][3]; int n;void updsum(llong &x,llong y) {x = x+y>=P?x+y-P:x+y;}int main() {fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P;finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;scanf("%d",&n);f[0][0] = 1ll;for(int i=1; i<=n; i++) for(int j=0; j<3; j++) for(int k=0; k<3; k++) {if(k!=j) updsum(f[i][j],f[i-1][k]);}llong ans = 0ll;for(int i=1; i<=n; i++){llong cur = f[i][1]*comb(n,i)%P*finv[i]%P*fact[i-1]%P; updsum(ans,cur);}ans = ans*finv[n]%P*fact[n-1]%P*quickpow(INV3,n)%P;printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的AtCoder AGC032F One Third (组合计数、DP、概率期望、微积分)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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