Description

详见OJ

Solution

这题看题目就知道是期望\(DP\)了。

先刚了2h\(DP\)式，得到\(f[i]=f[i-1]+f[i-2]+f[i-1]*(1-p)+...\)，然后不会化简，最后崩盘。

正解也是设f[i]表示生成第i级的剑的期望费用。

可以得到\(f[i] = f[i - 1] + f[i - 2] + (1 - p) * (f[i] - f[i - 2])\)

解方程即可，得到：

\[f[i] = f[i - 2] + f[i - 1] * (k/c[i - 1])\]（\(k\)为题目所给的\(k\)）

要用逆元（考场逆元直接用成了\(/(k!)\)，而需要的是\(/k\)。。。）

\[f[i] = f[i - 2] + f[i - 1] * k * ny[c[i - 1]] * jc[c[i - 1] - 1]\]

此题需要卡常！！！

Code

#include 
    
     #include 
     
      #define N 10000010#define ll long long#define mo 998244353#define fo(x, a, b) for (register int x = a; x <= b; x++)#define fd(x, a, b) for (register int x = a; x >= b; x--)using namespace std;const int maxn = 10000000;int n, A, bx, by, cx, cy, p, k;int b[N], c[N], f[N], jc[N], ny[N];inline int read(){    int x = 0; char c = getchar();    while (c < '0' || c > '9') c = getchar();    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();    return x;}int ksm(int x, int y){    int s = 1;    while (y)    {        if (y & 1) s = (ll)s * x % mo;        x = (ll)x * x % mo; y >>= 1;    }    return s;}void ycl(){    jc[0] = jc[1] = 1;    fo(i, 2, maxn) jc[i] = (ll)jc[i - 1] * i % mo;    ny[maxn] = ksm(jc[maxn], mo - 2);    fd(i, maxn - 1, 1) ny[i] = (ll)ny[i + 1] * (i + 1) % mo;}int main(){    freopen("forging.in", "r", stdin);    freopen("forging.out", "w", stdout);    n = read(), A = read();    if (n == 0) {printf("%d\n", A); return 0;} ycl();    bx = read(), by = read(), cx = read(), cy = read(), p = read();    b[0] = by + 1, c[0] = cy + 1;    fo(i, 1, n - 1)    {        b[i] = ((ll)b[i - 1] * bx + by) % p + 1;        c[i] = ((ll)c[i - 1] * cx + cy) % p + 1;    }    f[0] = A; k = std::min(c[0], b[0]);    f[1] = (f[0] + (ll)f[0] * c[0] % mo * ny[k] % mo * jc[k - 1] % mo) % mo;    fo(i, 2, n)    {        k = std::min(c[i - 1], b[i - 2]);        f[i] = (f[i - 2] + (ll)f[i - 1] * c[i - 1] % mo * ny[k] % mo * jc[k - 1] % mo) % mo;    }    printf("%d\n", f[n]);    return 0;}