题目背景
勇者虽然武力值很高，但在经历了多次战斗后，发现怪物越来越难打，于是开始思考是不是自己平时锻炼没到位，
于是苦练一个月后发现……自己连一个史莱姆都打不过了。
勇者的精灵路由器告诉勇者其实是他自己的武器不好，并把他指引到了锻造厂。
题目描述
“欢迎啊，老朋友。”
一阵寒暄过后，厂长带他们参观了厂子四周，并给他们讲锻造的流程。
“我们这里的武器分成若干的等级，等级越高武器就越厉害，并且对每一等级的武器都有两种属性值 \(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博客
证明如下 ↩︎