C++ 解法, 执行用时: 2623ms, 内存消耗: 48364K, 提交时间: 2022-04-08 09:54:01

#include <bits/stdc++.h>
#define F(x, y, z) for (int x = (y); x <= (z); ++x)
#define DF(x, y, z) for (int x = (y); x >= (z); --x)
using namespace std;
typedef long long ll;
const int maxn = 12252240;
namespace modular {
const int mod = 998244353;
int add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }
int dec(int x, int y) { return add(x, mod - y); }
int mul(int x, int y) { return 1ll * x * y % mod; }
int Pow(int x, int y) {
    int res = 1;
    for (; y; y >>= 1, x = mul(x, x))
        if (y & 1) res = mul(res, x);
    return res;
}
} using namespace modular;
int n, a0, x, y, k, M;
int f[maxn];
int main() {
    cin >> n >> a0 >> x >> y >> k >> M;
    int ans = 0, xs = mul(k, Pow(n, k - 1));
    F(i, 0, n - 1) {
        ++f[a0 % maxn];
        ans = add(ans, mul(a0 - a0 % maxn, xs));
        a0 = (1ll * a0 * x + y) % M;
    }
    F(i, 1, k) {
        int t = Pow(n, k - i);
        F(j, 0, maxn - 1) {
            ans = add(ans, mul(mul(f[j], j), t));
            if (j % i) f[j - j % i] = add(f[j - j % i], f[j]), f[j] = mul(f[j], n - 1);
            else f[j] = mul(f[j], n);
        }
    }
    cout << ans << endl;
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 945ms, 内存消耗: 94344K, 提交时间: 2022-11-24 11:36:29

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 998244353;
const int N = 1e7+10,M = 1e6;
LL a[N],fn[20],f[2][M];
int main(){
//	freopen("a.txt","r",stdin);
	LL n,x,y,M,k;
	cin>>n>>a[0]>>x>>y>>k>>M;
	for(int i = 1;i<n;++i)a[i]=(a[i-1]*x+y)%M;
	fn[0] = 1;
	for(int i = 1;i<20;++i)fn[i] = fn[i-1]*n%MOD;
	LL L = 1;
	for(LL i = 1;i<=16;++i){
		L = L*i/__gcd(L,i);
//		cout<<a[i]<<" ";
	}
//	cout<<L<<'\n';
//	puts("");
	LL ans = 0;
	for(int i = 0;i<n;++i){
		(ans += a[i]/L*L%MOD*fn[k-1]%MOD*k%MOD)%=MOD;
		a[i]%=L;
		f[0][a[i]]++;
	}
	for(int i = 0;i<k;++i){
		for(int j = 0;j<L;++j){
			(ans += f[i&1][j]*j%MOD*fn[k-i-1]%MOD)%=MOD;
//			if(f[i&1][j]*j%MOD)
//			cout<<f[i&1][j]<<" "<<k-i-1<<" "<<fn[k-i-1]<<"\n ";
		}
		memset(f[(i+1)&1],0,sizeof f[(i+1)&1]);
		for(int j = 0;j<L;++j){
			(f[(i+1)&1][j] += (f[i&1][j]*(n-1)%MOD))%=MOD;
			(f[(i+1)&1][j-j%(i+1)] += f[i&1][j]%MOD)%=MOD;
		}
	}
	cout<<ans<<'\n';
	return 0;
}