网站源码资源,怎么做网站搜索引擎优化,做网站如何挑选服务器,马鞍山网站建设兼职https://atcoder.jp/contests/abc318/tasks/abc318_h
先转为概率#xff0c; f i f_i fi 表示 i i i 个点两人都AC的概率#xff0c; g i g_i gi 表示恰好一个人AC的概率。
两个人都AC#xff0c;只能为全部自环#xff0c; f i 1 i ! f_i\frac 1 {i!} fii!1
…https://atcoder.jp/contests/abc318/tasks/abc318_h
先转为概率 f i f_i fi 表示 i i i 个点两人都AC的概率 g i g_i gi 表示恰好一个人AC的概率。
两个人都AC只能为全部自环 f i 1 i ! f_i\frac 1 {i!} fii!1
现在求 g n g_n gn。然后有个定理 n n n 个点形成的图形 n n n 所在的环的大小在 [ 1 , n ] [1,n] [1,n] 内随机生成。很好证明
然后考虑枚举 n n n 所在的环大小为 i i i先考虑由 f f f 推向 g g g 的情况。剩下 n − i n-i n−i 个点两个人都AC所以为 f n − i f_{n-i} fn−i。那么当前这个环只能有一个人AC所以环大小至少为2。
此时谁AC都可以所以最小的那条边有两个选择即 2 i \frac 2 i i2。因此 f → g f\to g f→g 的答案为 g n ∑ i 2 n 2 i f n − i n \Large g_n\frac{\sum_{i2}^n\frac 2 if_{n-i}}n gnn∑i2ni2fn−i
现在考虑 g → g g\to g g→g 的贡献。之后的贡献为 g n − i g_{n-i} gn−i。发现他已经保证了恰好一个人AC而且已经确定了这个人是谁。那么当前这个环的选择唯一但大小可以使1因为即使两个人在这个环内同时AC也无所谓。 g n ∑ i 1 n 1 i g n − i n \Large g_n\frac{\sum_{i1}^n\frac 1 ig_{n-i}}n gnn∑i1ni1gn−i
结合起来就是 g n ∑ i 1 n ( 2 i f n − i ( i ≠ 1 ) 1 i g n − i ) n \Large g_n\frac{\sum_{i1}^n(\frac 2 if_{n-i}\small{(i\ne 1)}\Large\frac 1 ig_{n-i})}n gnn∑i1n(i2fn−i(i1)i1gn−i)
令 a i 2 i a_i\frac 2 i aii2 且 a 1 0 a_10 a10 b i 1 i b_i\frac 1 i bii1
然后上面就变成了 g n ∑ i 1 n ( a i f n − i b i g n − i ) n \Large g_n\frac{\sum_{i1}^n(a_if_{n-i}b_ig_{n-i})}n gnn∑i1n(aifn−ibign−i)
前面NTT后面是个分治NTT即可。
