首页 > 其他分享 >「LOJ3405」Gem Island 2

「LOJ3405」Gem Island 2

时间:2023-06-05 19:55:05浏览次数:65  
标签:min int Island sum LOJ3405 max binom aligned Gem

题目

点这里看题目。


有一个长度为 \(n\) 的序列 \(a_1,a_2,\dots,a_n\)。初始时,\(\forall 1\le i\le n,a_i=1\)。

接下来进行 \(d\) 轮操作。每一轮操作会以 \(\frac{a_i}{\sum_{j=1}^na_j}\) 的概率选出 \(i\) 并令 \(a_i\gets a_i+1\)。

求 \(d\) 轮操作后,\(a\) 的前 \(r\) 大的元素之和的期望。答案对 \(998244353\) 取模。

所有数据满足 \(1\le n,d\le 1.5\times 10^7,1\le r\le n\)。

分析

为了后续推导的方便,我们考虑对 \(p_i=a_i-1\) 计算,这样只需要对答案加上 \(r\) 就 OK 了。

首先研究特定的 \(p\) 出现的概率,如下所示:

\[\left(d!\prod_{i=1}^n\frac 1{(p_i)!}\right)\left(\frac{1}{n^{\overline d}}\prod_{i=1}^n(p_i)!\right)=\binom{n+d-1}{d}^{-1} \]

将操作考虑为一个 \([n]^d\) 中的序列,则第一块计算了“产生的序列满足 \(p\)”的个数,第二块计算了“这样的序列产生的概率”。


接下来,我们不妨先考虑 \(r=1\) 的情况,即计算 \(\mathbb E[\max a]=1+\mathbb E[\max p]\)。

控制 \(\max p\) 最简单的方法就是枚举上界 \(m\) 并钦定 \(p\) 中所有元素都 \(<m\)。不过因为其扩展性较弱(或者,要扩展必须得引入新的元,显得非常抽象),我们这里采用 min-max 反演处理。

把这个式子列出来:

\[\mathbb E[\max p]=\sum_{S\subseteq [n],S\neq \varnothing}(-1)^{|S|-1}\mathbb E\left[\min_{x\in S}p_x\right] \]

很容易想到 \(\mathbb E\left[\min_{x\in S}p_x\right]\) 仅仅和 \(|S|\) 有关,我们记这个期望的 \(\binom{n+d-1}{d}\) 倍为 \(f_{|S|}\)。计算 \(f_{k}\) 同样可以枚举一个下界 \(m\),于是得到:

\[\begin{aligned} f_k &=[x^d]\left(\frac{1}{1-x}\right)^{n-k}\sum_{m\ge 1}\left(\frac{x^m}{1-x}\right)^k\\ &=\sum_{m\ge 1}\binom{d-mk+n-1}{n-1} \end{aligned} \]

看起来很抽象,但是注意到这是一个倍数求和的形式,且每一项仅仅和 \(mk\) 相关。这意味着我们可以用 Dirichlet 后缀和快速算出 \(f\),复杂度为 \(O(d\log\log d)\)。

最后算答案就可以 \(O(n)\) 了。


而后考虑普遍情况。这里 min-max 反演处理的好处就出来了,因为有:

\[k\operatorname{th-max}S=\sum_{T\subseteq S,|T|\ge k}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min T \]

它将所有第若干大都变成了最小值。相应地,答案就应该为:

\[\begin{aligned} \binom{n+d-1}{d}\sum_{j=1}^r\mathbb E[j\operatorname{th-max}p] &=\sum_{j=1}^r\sum_{k=j}^n(-1)^{k-j}\binom{k-1}{j-1}\binom{n}{k}f_k\\ &=\sum_{k=1}^n\binom{n}{k}f_k\sum_{j=1}^{\min\{r,k\}}(-1)^{k-j}\binom{k-1}{j-1} \end{aligned} \]

后面这个怎么处理?组合数下指标求和本身很难算,但是对于若干个 \(k\) 都要算出来则可以考虑直接递推

设 \(g_k=\sum_{j=1}^{\min\{r,k\}}(-1)^{k-j}\binom{k-1}{j-1}\),则容易发现当 \(k\le r\) 时 \(g_k=[k=1]\)。当 \(k>r\) 时研究其递推关系:

\[\begin{aligned} g_k &=\sum_{j=1}^r(-1)^{k-j}\binom{k-1}{j-1}\\ &=\sum_{j=1}^r(-1)^{k-j}\left(\binom{k-2}{j-1}+\binom{k-2}{j-2}\right)\\ &=-\sum_{j=1}^r(-1)^{k-1-j}\binom{k-2}{j-1}+\sum_{j=1}^{r-1}(-1)^{k-1-j}\binom{k-2}{j-1}\\ &=(-1)^{k-r}\binom{k-2}{r-1} \end{aligned} \]

好吧,没有递推关系。好消息是我们直接得到了 \(g\) 的通项,那就可以 \(O(1)\) 算单项了。

最终可以以 \(O(d\log\log d+n)\) 的复杂度解决这道题。

代码

#include <bits/stdc++.h>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int mod = 998244353;
const int MAXN = 1.5e7 + 5, MAXP = 1e6 + 5;

template<typename _T>
inline void Read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) Write( x / 10 );
    putchar( x % 10 + '0' );
}

int f[MAXN];
int fac[MAXN << 1], ifac[MAXN << 1];

int prime[MAXP], pn;
bool isPrime[MAXN];

int N, D, R;

inline int Qkpow( int, int );
inline int Inv( const int &a ) { return Qkpow( a, mod - 2 ); }
inline int Mul( int x, const int &v ) { return 1ll * x * v % mod; }
inline int Sub( int x, const int &v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, const int &v ) { return ( x += v ) >= mod ? x - mod : x; }

inline int& MulEq( int &x, const int &v ) { return x = 1ll * x * v % mod; }
inline int& SubEq( int &x, const int &v ) { return ( x -= v ) < 0 ? ( x += mod ) : x; }
inline int& AddEq( int &x, const int &v ) { return ( x += v ) >= mod ? ( x -= mod ) : x; }

inline int C( int n, int m ) { return n < m ? 0 : Mul( fac[n], Mul( ifac[m], ifac[n - m] ) ); }

inline int Qkpow( int base, int indx ) {
    int ret = 1;
    while( indx ) {
        if( indx & 1 ) MulEq( ret, base );
        MulEq( base, base ), indx >>= 1;
    }
    return ret;
}

inline void EulerSieve( const int &n ) {
    for( int i = 2 ; i <= n ; i ++ ) {
        if( ! isPrime[i] ) prime[++ pn] = i;
        for( int j = 1 ; j <= pn && 1ll * i * prime[j] <= n ; j ++ ) {
            isPrime[i * prime[j]] = true;
            if( ! ( i % prime[j] ) ) break;
        }
    }
}

inline void Init( const int &n ) {
    fac[0] = 1; rep( i, 1, n ) fac[i] = Mul( fac[i - 1], i );
    ifac[n] = Inv( fac[n] ); per( i, n - 1, 0 ) ifac[i] = Mul( ifac[i + 1], i + 1 );
}

int main() {
    Read( N ), Read( D ), Read( R );
    EulerSieve( D ), Init( D + N );
    rep( i, 1, D ) f[i] = C( D - i + N - 1, N - 1 );
    for( int i = 1 ; i <= pn ; i ++ )
        for( int j = D / prime[i] ; j >= 1 ; j -- )
            AddEq( f[j], f[j * prime[i]] );
    f[1] = C( D + N - 1, N );
    int ans = Mul( N, f[1] );
    rep( i, R + 1, N ) {
        int res = Mul( f[i], Mul( C( N, i ), C( i - 2, R - 1 ) ) );
        ( i - R ) & 1 ? SubEq( ans, res ) : AddEq( ans, res );
    }
    Write( Add( R, Mul( ans, Inv( C( N + D - 1, D ) ) ) ) ), putchar( '\n' );
    return 0;
}

补充内容

如果在 \(r>1\) 的时候还要枚举上界 \(m\) 并 \(\max p\) 来算答案该怎么办?

尝试在 GF 中引入第二个元 \(y\) 表示“有多少个元素不小于 \(m\)”,那么就应有:

\[\begin{aligned} \binom{n+d-1}{d}\sum_{j=1}^r\mathbb E[j\operatorname{th-max} p] &=\sum_{j=1}^n\min\{j,r\}[x^dy^j]\sum_{m\ge 1}\left(\frac{1-x^m+yx^m}{1-x}\right)^n\\ &=\sum_{j=1}^n\min\{j,r\}\binom{n}{j}[x^d]\sum_{m\ge 1}\frac{x^{mj}(1-x^m)^{n-j}}{(1-x)^n}\\ &=\sum_{j=1}^n\sum_{k=0}^{n-j}(-1)^{k}\binom{n}{j}\binom{n-j}{k}\min\{j,r\}\sum_{m\ge 1}\binom{d-m(j+k)+n-1}{n-1}\\ &=\sum_{j=1}^n\sum_{k=0}^{n-j}(-1)^k\binom{n}{j}\binom{n-j}{k}\min\{j,r\}f_{j+k} \end{aligned} \]

尝试转而枚举 \(t=j+k\),答案变为:

\[\begin{aligned} \binom{n+d-1}{d}\sum_{j=1}^r\mathbb E[j\operatorname{th-max} p] &=\sum_{t=1}^nf_t\sum_{j=1}^t(-1)^{t-j}\binom{n}{j}\binom{n-j}{t-j} \min\{j,r\}\\ &=\sum_{t=1}^n\binom{n}{t}f_t\sum_{j=1}^t(-1)^{t-j}\binom{t}{j}\min\{j,r\} \end{aligned} \]

这和 min-max 反演产生的结果已经很接近了,但是后面那个和式里面的东西还不太一样。我们分类讨论一下:

  • 对于 \(j\le r\) 的部分:

    \[\sum_{j=1}^{\min\{t,r\}}(-1)^{t-j}\binom{t}{j}j=t\sum_{j=1}^{\min\{t,r\}}(-1)^{t-j}\binom{t-1}{j-1} \]

    比较一下:多了一个 \(t\),其它部分没差。

  • 对于 \(j>r\) 的部分:

    \[\begin{aligned} \sum_{j=r+1}^t(-1)^{t-j}\binom{t}{j}r &=r\sum_{j=r+1}^t(-1)^{t-j}\left(\binom{t-1}{j}+\binom{t-1}{j-1}\right)\\ &=r\cdot (-1)^{t-r-1}\binom{t-1}{r}\\ &=(t-1)\cdot (-1)^{t-r-1}\binom{t-2}{r-1} \end{aligned} \]

把两部分凑起来看。当 \(t\le r\) 的时候,只有 \(j\le r\) 的部分需要考虑,而它的结果和 \(g_t\) 一样,都是 \([t=1]\)。当 \(t>r\) 的时候,\(j\le r\) 的部分算出来为 \(t\cdot (-1)^{t-r}\dbinom{t-2}{r-1}\),与 \(j>r\) 的部分抵消后恰好和 \(g_t\) 相同。


至于为什么这种 \(g\) 可以产生递推?

\[\sum_{j=0}^r\binom{n}{j}x^j=(1+x)\left(\sum_{j=0}^r\binom{n-1}{j}x^j\right)-\binom{n-1}{r}x^{r+1} \]

标签:min,int,Island,sum,LOJ3405,max,binom,aligned,Gem
From: https://www.cnblogs.com/crashed/p/17458797.html

相关文章

  • Generative AI 新世界 | 大语言模型(LLMs)在 Amazon SageMaker 上的动手实践
    在上一篇《GenerativeAI新世界:大型语言模型(LLMs)概述》中,我们一起探讨了大型语言模型的发展历史、语料来源、数据预处理流程策略、训练使用的网络架构、最新研究方向分析(AmazonTitan、LLaMA、PaLM-E等),以及在亚马逊云科技上进行大型语言模型训练的一些最佳落地实践等。本期文章......
  • VulnHub-Gemini Inc: 1
    靶机地址:https://www.vulnhub.com/entry/gemini-inc-1,227/目标:Identifyanyvulnerabilitiespossiblewiththegoalofcompletesystemcompromisewithrootprivilege.Todemonstratethelevelofaccessobtained,pleaseprovidethecontentofflag.txtlocatedint......
  • leetcode 463. Island Perimeter
    Youaregivenamapinformofatwo-dimensionalintegergridwhere1representslandand0representswater.Gridcellsareconnectedhorizontally/vertically(notdiagonally).Thegridiscompletelysurroundedbywater,andthereisexactlyoneisland(i......
  • wordpress插件:用WP Media Category Management管理媒体库分类
    一,安装插件:搜索WPMediaCategoryManagement点击立即安装 安装完成后,点击启用点击启用后页面会报错,忽略它返回前一个页面,点这里:提示要自动更新,跳过,也可选允许并继续按默认设置,点SaveSettings二,应用插件:1,添加分类2,修改图片所属分类3,从媒体库选择时:......
  • Islands Architecture-孤岛架构
    IslandsArchitecture是什么IslandsArchitecture(孤岛架构)的概念最初是由「Etsy」的前端架构师 「KatieSylor-Miller」 在2019年提出,并由Preact作者「JasonMiller」在islands-architecture[1]一文中推广。这是一套基于SSR(服务端渲染)的架构。要了解他的特点,我们需要先了解......
  • NIST SP 800-37 Risk Management Framework for Information Systems and Organizatio
    NISTSP800-37RiskManagementFrameworkforInformationSystemsandOrganizationsASystemLifeCycleApproachforSecurityandPrivacy Itstructuredinto3levelorganizationview,businessmissionandinformationsystemview.800-37isshortforNIST......
  • Get-MMagent 是一个命令,通常用于查询与 Microsoft Management Agent (MMAgent) 相关的
    Get-MMagent是一个命令,通常用于查询与MicrosoftManagementAgent(MMAgent)相关的属性和配置信息。MMAgent是一款基于云计算技术的软件代理程序,用于帮助配置管理、安全性和监视方案。在Windows平台上,MMAgent通常用于实现高效的云端管理和自动化操作,包括AzureMonitor等相......
  • CF1824B2 LuoTianyi and the Floating Islands (Hard Version) - 概率期望 - 树的重心
    题目链接:https://codeforces.com/contest/1824/problem/B2题解:考虑一棵\(n\)个点的树,假如已经选定了\(k\)个特殊点,如何判断某一个点是否为好点?显然将这个点提到根没有影响,那么好点的充要条件是对于所有子树的\(S_u\)值都\(\leqk/2\),这里\(S\)代表\(u\)子树中的特殊......
  • spring-transaction源码分析(2)EnableTransactionManagement注解
    概述(Javadoc)该注解开启spring的注解驱动事务管理功能,通常标注在@Configuration类上面用于开启命令式事务管理或响应式事务管理。@Configuration@EnableTransactionManagementpublicclassAppConfig{@BeanpublicFooRepositoryfooRepository(){//c......
  • SpringSecurity过滤器之SessionManagementFilter
    SessionManagementFilter检测用户自请求开始以来是否已通过身份验证,如果已通过,则调用SessionAuthenticationStrategy以执行任何与会话相关的活动,例如激活会话固定保护机制或检查多个并发登录。配置如下:@ConfigurationpublicclassMySecurityConfigextendsWebSecurityConfigur......