526互联

slojP2105. 锻造

发布时间 2023-06-17 10:08:56作者: cztq

题目背景

勇者虽然武力值很高，但在经历了多次战斗后，发现怪物越来越难打，于是开始思考是不是自己平时锻炼没到位，

于是苦练一个月后发现……自己连一个史莱姆都打不过了。

勇者的精灵路由器告诉勇者其实是他自己的武器不好，并把他指引到了锻造厂。

题目描述

“欢迎啊，老朋友。”

一阵寒暄过后，厂长带他们参观了厂子四周，并给他们讲锻造的流程。

“我们这里的武器分成若干的等级，等级越高武器就越厉害，并且对每一等级的武器都有两种属性值 \(b\) 和 \(c\) ，但是我们初始只能花 \(a\) 个金币来生产 \(1\) 把 \(0\) 级剑……”

“所以你们厂子怎么这么垃圾啊，不能一下子就造出来 \(999\) 级的武器吗？”勇者不耐烦的打断了厂长的话。

“别着急，还没开始讲锻造呢……那我们举例你手中有一把 \(x\) 级武器和一把 \(y\) 级武器 \(y = \max(x - 1,0)\) ,我们令锻造附加值 \(k = \min(cx,by)\)，则你有 \(\frac {k}{cx}\)的概率将两把武器融合成一把 \(x+1\) 级的武器。”

“……但是，锻造不是一帆风顺的，你同样有 \(1 - \frac {k}{cx}\) 的概率将两把武器融合成一把 \(\max(x-1,0)\) 级的武器……”

勇者听完后暗暗思忖，他知道厂长一定又想借此机会坑骗他的零花钱，于是求助这个村最聪明的智者——你，来告诉他，想要强化出一把 \(n\) 级的武器，其期望花费为多少？

由于勇者不精通高精度小数，所以你只需要将答案对 \(998244353(7×17×223+17×17×223+1)\) 一个质数，取模即可。

输入格式

第一行两个整数 \(n, a\)，含义如题所示。 为了避免输入量过大，第二行五个整数 \(bx, by, cx, cy, p\)，按照下列代码来生成 \(b\) 和 \(c\) 数组。

b[0]=by+1;c[0]=cy+1;
for(int i=1;i<n;i++){
	b[i]=((long long)b[i-1]*bx+by)%p+1;
	c[i]=((long long)c[i-1]*cx+cy)%p+1;
}

输出格式

输出一行一个整数，表示期望花费。

样例

输入数据 1

0 6432
4602677 3944535 2618884 6368297 9477531

输出数据 1

6432

输入数据 2

1 3639650
6136976 5520115 2835750 9072363 9302097

输出数据 2

150643649

输入数据 3

10 2
2 33 6 66 2333333

输出数据 3

976750710

数据规模与约定

对于 \(100\%\) 的数据，\(0 ≤ a ≤ 10^{7},0 ≤ bx, by, cx, cy < p < 10^{7},0 ≤ n ≤10^{7}\)

题解

期望，又是一个算不来的玩意

首先很明显的一点是这题需要对小数取模

那么O(n)求逆元这种东西就有用了

我们能从题目中知道：

如果我们需要合成一把 \(i\) 级的武器，

成功后我们会消耗 \(i-1\) 级的武器与\(\max(i-2,0)\) 级的武器，

失败后我们会消耗 \(i - 1\) 级的武器与\(\max(i-2,0)\) 级的武器，

但会得到 \(\max(i-2,0)\) 级的武器，相当于只损失了 \(i - 1\) 级的武器

有木有 \(dp\) 的想法了

我们再来看如何推出这玩意的状态转移方程式

设 \(dp[n]\) 为升到 \(n\) 级武器的期望花费这不废话吗

易得 \(dp[0] = a\)

对于 \(dp[n]\) 而言，我们需要 \(n - 1\) 和 \(n - 2\) 级的剑，

由于失败后也会剩下一把 \(n-2\) 级的剑，所以我们只用考虑另外一把剑的概率加上 \(dp[n-2]\)

对于 \(n - 1\) 的剑，期望锻造的次数是\(\dfrac{1}{p} = \dfrac{c[n-1]}{\min(c[n-1],b[n-2])}\)（ \(p\) 为成功概率）

因为后面要取模，所以应该是 \(dp[n-1] \times inv[\min(c[n-1],b[n-2])] \times c[n-1]\) （ \(inv\) 为逆元）

所以完整的方程是 \(dp[i] = (dp[i-1] \times inv[\min(c[i-1],b[i-2])] \times c[i-1] \%mod+ dp[i-2])\%mod\)

丢个证明在末尾[1]

代码

#include<bits/stdc++.h> 
#define mod 998244353
#define N 10000010
using namespace std;
int n,a,b[N],c[N],inv[N],dp[N];
int main(){
	scanf("%d%d",&n,&a);
	int bx,by,cx,cy,p;
	scanf("%d%d%d%d%d",&bx,&by,&cx,&cy,&p);
	inv[1] = 1;
	for(int i = 2;i<=1e7;i++)
		inv[i] = 1ll*(mod-mod/i)*inv[mod%i]%mod;
	b[0] = by+1;
	c[0] = cy+1;
	for(int i = 1;i<=n;i++){
		b[i] = (1ll*b[i-1]*bx+by)%p+1;
		c[i] = (1ll*c[i-1]*cx+cy)%p+1;
	}
	dp[0] = a;
	dp[1] = (a+1ll*a*inv[min(b[0],c[0])]%mod*c[0]%mod)%mod;
	for(int i = 2;i<=n;i++)
		dp[i] = (1ll*dp[i-1]*inv[min(c[i-1],b[i-2])]%mod*c[i-1]%mod+dp[i-2])%mod;
	printf("%d",dp[n]);
	return 0;
}

对于 \(n = 1\) 的期望

\[E = 2a \times p + 3a \times p \times (1-p) + 4a \times p \times (1-p)^2+··· \]

其中 \(p\) 为合成成功的概率，即 \(\frac{\min(c_0,b_0)}{c_0}\)

表示买两把零级剑就合成成功，买三把就合成成功，买四把合成成功……的情况

提个公因数：

\[E = a\times p \times \lim_{n \to + \infty} [ 2 + 3(1-p) + 4(1-p)^2 +···+n(1-p)^{n-2}] \]

设 \(t = 1-p\)，要化简的部分为：

\[S = \lim_{n \to + \infty}(2+3t+4t^2+5t^3+···+nt^n-2) \]

等比数列错位相减：

\[\begin{align*} (t-1)S =& \lim_{n \to +\infty} [(2t+3t^2+4t^3+5t^4+···+nt^{n-1})-(2+3t+4t^2+5t^3+···+nt^{n-2})]\\ =&\ \lim_{n \to + \infty} (nt^{n-1} - \sum_{i = 1}^{n-2} t^i - 2) \\ =&\ \lim_{n \to + \infty} (nt^{n-1} - \dfrac{t^{n-1}-t}{t-1} - 2) \\ S =&\ \dfrac{\lim\limits_{n \to + \infty} (nt^{n-1}-\dfrac{t^{n-1}-t}{t-1}-2)}{t-1} \end{align*} \]

所以：

\[E = ap \times \frac{p+1}{p^2} = a \frac{p+1}{p} \]

在这个基础上考虑 \(dp\)，设 \(dp[i]\) 表示合成 \(i(i \ge 1)\) 级剑的期望花费，如果合成失败，相当于少了一把 \(i − 1\)级剑，而对\(i − 2\)级剑没有影响，从概率上来说合成 \(\dfrac{1}{p}\) ( \(p\) 是 \(i\) 级剑合成成功的概率）次，就能合成成功，所以就要消耗 \(\dfrac{1}{p}\) 把 \(i − 1\)级剑，一把 \(i − 2\)级剑，于是

\[dp[i] = \frac{1}{p} dp[i-1]+dp[i-2] \]

证明部分来自 锻造 (forging)_ixRic的博客-CSDN博客

  1. 证明如下 ↩︎