Mocha的数据包

NC219001. Mocha的数据包

描述

Mocha 沉迷发送数据包，她一共需要发送 $n$ 个相同的数据包。

Mocha 可以进行任意次如下操作：

假设 Mocha 还剩 $k$ 个数据包没有发送，她可以选择 $i \in [1,k]$ 个数据包将其发送，并花费 $F_{n-i+1}$ 的代价，其中 $F_{i}$ 表示斐波那契数列第 $i$ 项的值。每个被发送的数据包有 $\dfrac{p}{q}$ 的概率发送成功，且每个数据包是否发送成功相互独立。发送失败的数据包视为没有发送，需要在接下来继续发送它。

斐波那契数列的定义如下：

$F_i = \begin{cases} 0, &i = 0 \\ 1, &i = 1 \\ F_{i-1}+F_{i-2}, &i \ge 2 \end{cases}$

Mocha 想最小化发送数据包所花费的代价，她想请你帮她算算，如果采取最优策略，将所有数据包全部发送的期望代价是多少。

输入描述

仅有一行，三个正整数  () 和  (，)，表示 Mocha 需要发送数据包的数量，以及每个数据包发送成功概率的分子和分母。

输出描述

一个正整数，表示在最优策略下将所有数据包全部发送的期望代价对  取模的结果。

示例1

输入:

1 7 10

输出:

570425346

说明:

只有一个物品，每次发送花费代价为 $F_1=1$ ，容易得到期望代价为 $\dfrac{10}{7} \equiv 570425346 \pmod {998244353}$ 。

示例2

输入:

3 7 10

输出:

723843564

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 303ms, 内存消耗: 23240K, 提交时间: 2021-05-10 00:58:41

#include<stdio.h>
typedef long long ll;
#define M 998244353

int i,j,k,n,m;
ll c[2050][2050],sb,sb2,f[2050]={0,1},dp[2050];
ll ksm(ll a,ll p){ll res=1;while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res;}

int main(){
	c[0][0]=1;
	scanf("%d%lld%lld",&n,&sb,&sb2);
	sb=sb*ksm(sb2,M-2)%M;
	sb2=(-sb+M+1)%M;
	for(i=2;i<=2000;i++){
		f[i]=(f[i-1]+f[i-2])%M;
	}
	for(i=1;i<=n;i++){
		dp[i]=f[n+1-i];c[i][0]=c[i][i]=1;
		for(j=1;j<i;j++){
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%M;
			dp[i]+=c[i][j]*ksm(sb2,j)%M*ksm(sb,i-j)%M*dp[j]%M;
		}
		dp[i]=dp[i]%M*ksm((M-ksm(sb2,i)%M+1)%M,M-2)%M;
	}
	printf("%lld",dp[n]);
}

上一题

下一题

详情