「题解」锻造 forging(未完待续)

题目链接:GMOJ 6271

题目

题目描述

输入格式

输出格式

样例输入输出

#1

  • Input:

  • Output:

数据范围

题解

本题有多种解法。

解法 A (暴力解法)

分数据点编号讨论
未完待续

解法 B (数学公式)

解法 C (解法 B 的优化)

#include<cstdio>
#include<cmath>
#include<algorithm>
using std::min;
using std::max;
typedef long long ll;
#define MOD 998244353ll
const int MAXA=10000000+5;
const int MAXN=10000000+5;
const int MAXP=10000000+5;
int n,a;
int bx,by,cx,cy,p;
int b[MAXN],c[MAXN];
ll f[MAXN];
ll inv[MAXP];
void Init(void);
int main(void){
    //freopen("forging.in","r",stdin);
    //freopen("forging.out","w",stdout);
    register int i;
    Init();
    f[0]=a,f[1]=(a*inv[min(c[0],b[0])]%MOD*c[0]+a)%MOD;
    for(i=2;i<=n;++i)
        f[i]=(f[i-1]*inv[min(b[i-2],c[i-1])]%MOD*c[i-1]%MOD+f[i-2])%MOD;
    printf("%lld\n",f[n]);
    return 0;
}
void Init(void){
    register int i;
    int Max;
    scanf("%d%d",&n,&a);
    scanf("%d%d%d%d%d",&bx,&by,&cx,&cy,&p);
    b[0]=by+1;c[0]=cy+1;
    Max=max(b[0],c[0]);
    for(i=1;i<n;++i){
        b[i]=((ll)b[i-1]*bx+by)%p+1;
        c[i]=((ll)c[i-1]*cx+cy)%p+1;
        Max=max(Max,max(b[i],c[i]));
    }
    inv[1]=1;
    for(i=2;i<=Max;++i)
        inv[i]=((MOD-MOD/i)*inv[MOD%i])%MOD;
    return;
}

解法 D (解法 C 的优化)

#include<cstdio>
#include<cmath>
#include<algorithm>
using std::min;
using std::max;
typedef long long ll;
#define MOD 998244353ll
const int MAXA=10000000+5;
const int MAXN=10000000+5;
const int MAXP=10000000+5;
int n,a;
int bx,by,cx,cy,p;
int b[MAXN],c[MAXN];
ll f0,f1,f2;
ll inv[MAXP];
void Init(void);
int main(void){
    //freopen("forging.in","r",stdin);
    //freopen("forging.out","w",stdout);
    register int i;
    Init();
    f0=a,f1=(a*inv[min(c[0],b[0])]%MOD*c[0]+a)%MOD;
    for(i=2;i<=n;++i){
        f2=(f1*inv[min(b[i-2],c[i-1])]%MOD*c[i-1]%MOD+f0)%MOD;
        f0=f1;
        f1=f2;
    }
    if(n==0)
        printf("%lld\n",f0);
    else if(n==1)
        printf("%lld\n",f1);
    else
        printf("%lld\n",f2);
    return 0;
}
void Init(void){
    register int i;
    int Max;
    scanf("%d%d",&n,&a);
    scanf("%d%d%d%d%d",&bx,&by,&cx,&cy,&p);
    b[0]=by+1;c[0]=cy+1;
    Max=max(b[0],c[0]);
    for(i=1;i<n;++i){
        b[i]=((ll)b[i-1]*bx+by)%p+1;
        c[i]=((ll)c[i-1]*cx+cy)%p+1;
        Max=max(Max,max(b[i],c[i]));
    }
    inv[1]=1;
    for(i=2;i<=Max;++i)
        inv[i]=((MOD-MOD/i)*inv[MOD%i])%MOD;
    return;
}