HDU6574 江西省赛(概率+前缀和)

hdu6574

正难则反,先算不相交

对于区间$[l1,r1]$和$[l2,r2]$

$l2>r1或者r2<l1$

容易发现两种情况对称概率相同,所以只算$l2>r1$

$n$不大,可以枚举$r1$

所以$r1$有$n$种取值,概率分别是$\frac{1}{n}$

假设$r1=1$,此时只要满足$l2>1$即可

那么当$r2=1$时满足$l2>1$的概率是$\frac{0}{1}$

当$r2=2$时是$\frac{1}{2}$

当$r2=3$时是$\frac{2}{3}$

…

所以此时概率是$\frac{1}{n}\ast \frac{1}{n}\ast (\frac{0}{1}+\frac{1}{2}+\frac{2}{3}..+\frac{n-1}{n})$

当$r1=2$时概率是$\frac{1}{n}\ast \frac{1}{n}\ast (\frac{0}{1}+\frac{0}{2}+\frac{1}{3}..+\frac{n-2}{n})$

可以发现枚举$r1$后,变化的只是后面的系数,我们用$one$来维护

处理$\sum _{i=2}^{i=n}\frac{1}{i}$前缀和可以$O(1)$转移$one$

#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=2e6+10; const int mod=1e9+7; int pre[maxn],inv[maxn]; signed main() { int n; cin >> n; inv[1]=1; for(int i=2;i<=2000000;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int one=0,ans=0; for(int i=2;i<=n;i++) { one = (one+(i-1)*inv[i]%mod )%mod; pre[i]=( pre[i-1]+1*inv[i] )%mod; } for(int i=1;i<=n;i++)//l2>r1时 { ans = (ans+inv[n]*inv[n]%mod*one%mod)%mod; one = (one-(pre[n]-pre[i])+mod )%mod; } cout << ((1-ans*2)%mod+mod)%mod << '\n'; }