CF1153F Serval and Bonus Problem 【期望】

题目链接：洛谷

作为一只沉迷数学多年的蒟蒻OIer，在推柿子和dp之间肯定要选推柿子的！

首先假设线段长度为1，最后答案乘上$l$即可。

对于$x$这个位置，被区间覆盖的概率是$2x(1-x)$（线段端点分别在$x$的两边），不被区间覆盖的概率为$1-2x(1-x)$。

$$Ans=\sum_{i=k}^n {n\choose i}\int_{0}^1(2x(1-x))^i(1-2x(1-x))^{n-i}dx$$

$$=\sum_{i=k}^n {n\choose i}\int_{0}^1(2x(1-x))^i\sum_{j=0}^{n-i}(-1)^j{n-i\choose j}(2x(1-x))^jdx$$

$$=\sum_{i=k}^n{n\choose i}\sum_{j=0}^{n-i}(-1)^j2^{i+j}{n-i\choose j}\int_0^1x^{i+j}(1-x)^{i+j}dx$$

$$F_i=\int_0^1x^i(1-x)^idx$$

$$=\int_0^1x^i\sum_{j=0}^i(-1)^j{i\choose j}x^jdx$$

$$=\sum_{j=0}^i(-1)^j{i\choose j}\int_0^1x^{i+j}dx$$

$$=\sum_{j=0}^i(-1)^j{i\choose j}\frac{1}{i+j+1}$$

预处理$F_i$之后计算，时间复杂度$O(n^2)$。

 #include<bits/stdc++.h>

 #define Rint register int

 using namespace std;

 typedef long long LL;

 const int N = , mod = ;

 int fac[N], inv[N], invfac[N], po[N];

 inline void init(int m){

     fac[] = ;

     for(Rint i = ;i <= m;i ++) fac[i] = (LL) i * fac[i - ] % mod;

     inv[] = ;

     for(Rint i = ;i <= m;i ++) inv[i] = (LL) (mod - mod / i) * inv[mod % i] % mod;

     invfac[] = ;

     for(Rint i = ;i <= m;i ++) invfac[i] = (LL) invfac[i - ] * inv[i] % mod;

     po[] = ;

     for(Rint i = ;i <= m;i ++) po[i] = (po[i - ] << ) % mod;

 }

 inline int C(int n, int m){

     if(n < m || m < ) return ;

     return (LL) fac[n] * invfac[n - m] % mod * invfac[m] % mod;

 }

 int n, k, l, ans, f[N];

 int main(){

     scanf("%d%d%d", &n, &k, &l);

     init(n <<  | );

     for(Rint i = k;i <= n;i ++)

         for(Rint j = ;j <= i;j ++){

             int t = (LL) C(i, j) * inv[i + j + ] % mod;

             if(j & ) f[i] = (f[i] + mod - t) % mod; else f[i] = (f[i] + t) % mod;

         }

     for(Rint i = k;i <= n;i ++){

         int t1 = ;

         for(Rint j = ;j <= n - i;j ++){

             int t2 = (LL) po[i + j] * C(n - i, j) % mod * f[i + j] % mod;

             if(j & ) t1 = (t1 + mod - t2) % mod; else t1 = (t1 + t2) % mod;

         }

         ans = (ans + (LL) t1 * C(n, i) % mod) % mod;

     }

     printf("%d", (LL) l * ans % mod);

 }

CF1153F

据说这个式子还可以用NTT优化到$O(n\log n)$？有兴趣的各位可以思考一下反正我是没兴趣了

upd（2019-10-18）:

貌似有一个东西叫做Beta Function.

$$\begin{aligned}\Beta(x,y)&=\int_0^1t^x(1-t)^y\mathrm{d}t & (x,y\in \R_+)\\ \Gamma(z)&=\int_0^{+\infty}x^{z-1}e^{-x}\mathrm{d}x & (\Re(z)>0)\end{aligned}$$

有一些不知道为什么的结论。

$$\begin{aligned}\Gamma(n)&=(n-1)! & (n\in \N_+) \\ \Beta(x,y)&=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}\end{aligned}$$

于是上面的$F_i$直接就做完了。稍微化化就可以用NTT来做了。

巴特西

CF1153F Serval and Bonus Problem 【期望】

最新文章

热门文章