题目链接
https://atcoder.jp/contests/agc032/tasks/agc032_f
题解
神仙题..
第一步转化利用了 \(\frac{1}{3}\)这个数特有的性质. 假设我们用红线标出每一次切割的位置, 再在每一次切割的位置顺时针 \(120\)度处用蓝线标出, 那么答案就等于红线与蓝线之间的最小夹角. 但是这样转化完了依然不好做 (而且似乎也没用到 \(\frac{1}{3}\) 的特殊性), 那么考虑如果在每一次切割的位置逆时针 \(120\)度处用绿线标出, 答案依然是不变的, 因为 \(|x-\frac{1}{3}|=|(1-x)-\frac{2}{3}|\). 那样我们就相当于将整个圆周分成了 \(3\)等份 (每一等份记作 \(\frac{1}{3}\)), 考虑其中的一份, 每次在其中随机一个位置随机三种颜色中的一种画上线(初始时在 \(0\) 处有一条红线 \(\frac{1}{3}\)处有一条蓝线), 答案等于不同颜色之间最短距离的期望.
不算首尾一共撒了 \((n-1)\)个点, 将 \([0,\frac{1}{3}]\)分成了 \(n\)份. 考虑如何算两端为不同颜色的份 (下称 "不同色段") 的最短长度的期望.
首先考虑一个弱化版问题: 没有颜色的限制, 用 \((k-1)\)个点把 \([0,1]\)分成 \(k\)份, 最小的一份的期望长度. 考虑答案大于等于 \(t\)的概率, 也就相当于 \(n\)个随机实数和为 \(1-kt\)的概率除以 \(n\)个随机实数和为 \(1\)的概率, 也就是 \((n-1)\)个随机实数和不超过 \(1-kt\)的概率除以 \((n-1)\)个随机实数和不超过 \(1\)的概率, 显然等于 \((1-kt)^{k-1}\). 那么对其进行积分,\(\int^\frac{1}{k}_0(1-kt)^{k-1}\text{d}t=\frac{1}{k}\int^1_0(1-t)^{k-1}dt=\frac{1}{k}\int^1_0t^{k-1}\text{d}t=\frac{1}{k^2}\). 并且把 \([0,1]\)换成 \([0,L]\)推一下可知答案关于 \(L\)是线性的, 即 \(\frac{L}{k^2}\).
对于有颜色限制的情况, 考虑枚举不同色段的个数, 分成两部分:(1)出现这种情况的概率;(2)在这种情况下答案的期望. 对于(2), 显然不同色段的总长度期望为 \(\frac{k}{3n}\), 因为上面问题的答案关于总长度是线性的, 因此答案的期望即为 \(\frac{1}{3nk}\). 对于(1), 可以用一个 DP 乘以组合数来求出, DP 不同色段的个数, 组合数插入同色段.
总时间复杂度 \(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;
- }
来源: http://www.bubuko.com/infodetail-3394640.html