首页 > 其他分享 >CF891E Lust 题解

CF891E Lust 题解

时间:2024-08-30 15:15:10浏览次数:12  
标签:ch int 题解 CF891E Lust 1ll ini prod define

题目链接

点击打开链接

题目解法

会不了 \(egf\) /ll

我们把贡献变成 \(\prod\limits_{j\neq i}a_j=\prod\limits_{j=1}^na_j-\prod\limits_{j=1}^n (a_i-[i=j])\)
即答案为一开始的乘积 \(-\) \(k\) 次操作之后所有数乘积的期望

因为有顺序,所以用 \(egf\) 的形式表示最后乘积的期望:
\(f_i(x)=\sum\limits_{j=0}^{\infty} \frac{(a_i-j)x^j}{j!}=a_ie^x-xe^x=(a_i-x)e^x\)
\(F(x)=\prod f_i(x)=e^{nx}\prod (a_i-x)\)
后面的东西可以背包暴力求出(或者分治 \(ntt\))

最终的答案形式是:\(\frac{f_i\frac{n^{k-i}}{(k-i)!}\times k!}{n^k}=\frac{f_ik^{\underline {i}}}{n_i}\)
时间复杂度 \(O(n^2)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=5010,P=1e9+7;
int n,k,a[N],f[N];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
inline void dec(int &x,int y){ x-=y;if(x<0) x+=P;}
int qmi(int x,int y){
    int res=1;for(;y;y>>=1){ if(y&1) res=1ll*res*x%P;x=1ll*x*x%P;}
    return res;
}
int main(){
    read(n),read(k);
    int ini=1;
    F(i,1,n) read(a[i]),ini=1ll*ini*a[i]%P;
    f[0]=1;
    F(i,1,n) DF(j,i,0){
        f[j]=1ll*f[j]*a[i]%P;
        if(j) dec(f[j],f[j-1]);
    }
    int ans=0,mul=1,inv=qmi(n,P-2);
    F(i,0,min(n,k)){
        inc(ans,1ll*f[i]*mul%P);
        mul=1ll*mul*(k-i)%P*inv%P;
    }
    dec(ini,ans);
    printf("%d\n",ini);
    return 0;
}

标签:ch,int,题解,CF891E,Lust,1ll,ini,prod,define
From: https://www.cnblogs.com/Farmer-djx/p/18388815

相关文章

  • UVA12421 (Jiandan) Mua (I) - Lexical Analyzer题解
    没什么废话、超级珂爱的大模拟。本蒟蒻写了2h才过。其实就是按题意模拟即可,不需要什么高深的算法。本人就是错在了符号中的“=”,因为如果是连续的两个等于号,只能输出“==”,而不能输出“=”“==”,然后本人就卡在这个地方卡了1.5h。代码量也不大,主要是毒瘤细节模拟题。......
  • P6192 【模板】最小斯坦纳树 题解
    Description给定一个包含\(n\)个结点和\(m\)条带权边的无向连通图\(G=(V,E)\)。再给定包含\(k\)个结点的点集\(S\),选出\(G\)的子图\(G'=(V',E')\),使得:\(S\subseteqV'\);\(G'\)为连通图;\(E'\)中所有边的权值和最小。你只需要求出\(E'\)中所有边的权值......
  • BZOJ 4403序列统计题解
    缅怀zxc......
  • CSP-J 2021 初赛试题解析(第三部分:完善程序(2))
    完善程序二完整程序代码#include<iostream>usingnamespacestd;structpoint{intx,y,id;};boolequals(pointa,pointb){returna.x==b.x&&a.y==b.y;}boolcmp(pointa,pointb){returna.x!=b.x?a.x<b.x:a.y<b.y;}......
  • AT_arc170_b 的题解
    (一)因为\(a_i\)较小,那么可以对每一个\(i\),求出它右边离他最近的值为\(j\)的位置。枚举左端点和中间那个数\(a_j\),那么可以求出最小的\(k\)。这样就求出了每个左端点可以取到的最小的\(k\),记为\(b_i\)再从右到左\(b_i=\min(b_i,b_{i+1})\)。(二)AC代码。#include<bi......
  • AGC041D Problem Scores 题解
    在分值不降的条件下,要使任意一个大小为\(k\)的子集\(S\)内题目的分值之和少于任意一个大小为\(k+1\)的子集\(T\)内题目的分值之和,容易发现只需要取\(S\)为后\(k\)道题目,\(T\)为前\(k+1\)道题目时满足限制即可。换而言之,只需要对满足\(a\)的每一段长为\(k+......
  • P7075 [CSP-S2020] 儒略日 题解
    P7075[CSP-S2020]儒略日题面:题目描述为了简便计算,天文学家们使用儒略日(Julianday)来表达时间。所谓儒略日,其定义为从公元前4713年1月1日正午12点到此后某一时刻间所经过的天数,不满一天者用小数表达。若利用这一天文学历法,则每一个时刻都将被均匀的映射到数轴......
  • AT_ddcc2017_final_d なめらかな木 题解
    首先考虑暴力DP,设\(f(i,v_1,v_2,now)\)为已经将前\(i\)个数填入,\(i\)填在\(v_1\),\(j\)填在\(v_2\)点,已经填完点的状态是\(now\)(状压一下存在一个longlong里)的方案数。转移时直接枚举下一个点暴力转移,只需要保证新的点没有被访问过,并且填上新点后,\(v_1\)的所有邻接......
  • Luogu P4425 转盘 题解 [ 黑 ] [ 线段树 ] [ 贪心 ] [ 递归 ]
    转盘:蒟蒻的第一道黑,这题是贪心和线段树递归合并的综合题。贪心破环成链的trick自然不用多说。首先观察题目,很容易发现一个性质:只走一圈的方案一定最优。这个很容易证,因为再绕一圈回来标记前面的和等前面的标记完之后继续走是等价的,并且再绕一圈甚至可能更劣。于是,我们只用走......
  • 题解:P9938 [USACO21OPEN] Acowdemia II B
    前言:原来的tj干了一堆什么建图啊之类的,但其实不要这么复杂。注:下文中\(n\)是各成员名字列表。从\(K=1\)开整。如果情况是\(n_i<n_{i+1}<\cdots<n_j\),那么显然,咱就不知道关于成员\(n_i,\cdots,n_j\)的相对资历的信息。也许所有这帮成员都做出了相同的贡献。......