10.30T1 期望DP

6040 -- 【九校1D2T1】锻造

Description

“欢迎啊，老朋友。”
一阵寒暄过后，厂长带他们参观了厂子四周，并给他们讲锻造的流程。
“我们这里的武器分成若干的等级，等级越高武器就越厉害，并且对每一等级的武器都有两种属性值 b 和 c，但是我们初始只能花 a 个金币来生产 1 把 0 级剑……”
“所以你们厂子怎么这么垃圾啊，不能一下子就造出来 999 级的武器吗？”勇者不耐烦的打断了厂长的话。
“别着急，还没开始讲锻造呢……那我们举例你手中有一把 x 级武器和一把 y 级武器 (y = max(x−1,0))，我们令锻造附加值 k = min(cx ,by )，则你有k/cz的概率将两把武器融合成一把 x + 1 级的武器。”
“……但是，锻造不是一帆风顺的，你同样有 1 −k/cx的概率将两把武器融合成一把 max(x − 1,0) 级的武器……”
勇者听完后暗暗思忖，他知道厂长一定又想借此机会坑骗他的零花钱，于是求助这个村最聪明的智者——你，来告诉他，想要强化出一把 n 级的武器，其期望花费为多少？
由于勇者不精通高精度小数，所以你只需要将答案对 998244353(7 ×17 × 2^23 + 1，一个质数 ) 取模即可。

Input

第一行两个整数 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;
}

Output

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

Sample Input

1.4.1 样例 1 输入
0 6432
4602677 3944535 2618884 6368297 9477531
1.4.2 样例 1 输出
6432
1.4.3 样例 2 输入
1 3639650
6136976 5520115 2835750 9072363 9302097
1.4.4 样例 2 输出
150643649
1.4.5 样例 3 输入
10 2
2 33 6 66 2333333
1.4.6 样例 3 输出
976750710
1.4.7 样例 4 输入
200 5708788
0 0 0 0 1
1.4.8 样例 4 输出
696441597

Sample Output

 

Hint

 

 

 

 

 

 

 

然后我的AC代码MLE了>_<

code：

#include<iostream>
#include<cstdio>
#define N 10000005
using namespace std;
const int mod=998244353;
int b[N],c[N];
int E[N];
int bx,by,cx,cy,p;
int inv[N];
int main() {
//    freopen("forging.in","r",stdin);
//    freopen("forging.out","w",stdout);
    int n,a;
    cin>>n>>a;
    cin>>bx>>by>>cx>>cy>>p;
    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;
    }
    if(n==0) {
        cout<<a;
        return 0;
    }
    //////////
    inv[1]=1;
    for(int i=2; i<=p; i++)inv[i]=(long long)(mod-mod/i)*inv[mod%i]%mod;
    //////////
    E[0]=a;
    for(int i=1; i<=n; i++)
        E[i]=(((long long)E[i-1]*(long long)c[i-1])%mod*((long long)inv[c[i-1]<b[max(i-2,0)]?c[i-1]:b[max(i-2,0)]])%mod+(long long)E[max(i-2,0)])%mod;
    cout<<E[n]%mod;
    return 0;
}

over