题目大意

武器的每个级别有固定的两种属性\(b_i\)和\(c_i\)

可以用\(a\)的代价得到一把\(0\)级的武器。

可以将\(x\)级武器和\(y=\max(x-1,0)\)级武器融合锻造，

有\(\frac{\min(b_y,c_x)}{c_x}\)的概率可以升级成\(x+1\)级武器。

反之降级成\(y\)级武器。

问得到\(n\)级武器的期望代价（模意义下）。

思考历程

一开始想了个特别简单的DP。

然后发现有后效性……

搞不出来，然后心态崩了……

看到\(p=0\)的情况（也就是除了\(i=0\)之外，其它时候的\(b_i\)和\(c_i\)都为\(1\)，也就是百分百成功率）。

这样就可以特殊计算\(f_0\)和\(f_1\)，后面的像斐波拉契数列一样转移就可以了。

正解

正解的DP是没有后效性的。

正解的DP的目光更加长远，我想到的只是转移了一步的，但是正解是转移了很多步的。

状态还是\(f_i\)表示造\(i\)级武器的期望代价。

设成功率为\(x\)，则方程为\(f_i=f_{i-2}+f_{i-1}+(1-x)(f_i-f_{i-2})\)

前面半段是锻造的代价，后面是没有成功时的代价。

由于没有成功的时候还可以有\(i-2\)级的武器留下来，所以就在下一次锻造的时候将它的代价减去。

方程移项之后显然是没有后效性的。

然而这题卡时间。

比如要打\(O(n)\)求逆元，还有各种小常数优化。

代码

卡常数卡到极尽的代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #define N 10000010#define mo 998244353int n,a;int bx,by,cx,cy,p;int inv[N],f[N];int main(){    freopen("forging.in","r",stdin);    freopen("forging.out","w",stdout);    scanf("%d%d%d%d%d%d%d",&n,&a,&bx,&by,&cx,&cy,&p);    inv[1]=1;    for (register int i=2,k;i<=p;++i){        k=mo/i;        inv[i]=(long long)(mo-k)*inv[mo-i*k]%mo;    }    int b=by+1,c=cy+1;    f[0]=a;    f[1]=(f[0]+(long long)f[0]*(b>=c?1:(long long)inv[b]*c%mo))%mo;    for (register int i=2;i<=n;++i){        c=((long long)c*cx+cy)%p+1;        f[i]=(f[i-2]+(long long)f[i-1]*(b>=c?1:(long long)inv[b]*c%mo))%mo;        b=((long long)b*bx+by)%p+1;    }    printf("%d\n",f[n]);    return 0;}