[Luogu] P2044 [NOI2012]随机数生成器

(Link)

Description

有一个随机数列({X_n})，其中(X_{n+1}=(aX_n+c)mod{m})，求(X_nmod{g})。((n,m,a,c,X_0le{10^{18}},1le{g}le{10^8}))

Solution

有矩阵快速幂的做法，不过也可以直接推式子。

易知(X_n=a^nX_0+c(1+a+a^2+...+a^{n-1}))。但是千万不能用等比数列求和，因为这样会产生逆元，而这题没有保证(gcd(a,m)=1)。

所以可以递归求解等比数列之和。设(sum(n)=sumlimits_{i=0}^{n-1}a^i)，分两种情况讨论：

当(n)为偶数时，(displaystyle sumlimits_{i=0}^{n-1}a^i=sumlimits_{i=0}^{frac{n}{2}-1}a^i+sumlimits_{i=frac{n}{2}}^{n-1}a^i=(1+a^{frac{n}{2}})sumlimits_{i=0}^{frac{n}{2}-1}a^i)。

当(n)为奇数时，(displaystyle sumlimits_{i=0}^{n-1}a^i=sumlimits_{i=0}^{frac{n-1}{2}-1}a^i+sumlimits_{i=frac{n-1}{2}}^{n-2}a^i+a^{n-1}=(1+a^{frac{n-1}{2}})sumlimits_{i=0}^{frac{n-1}{2}-1}a^i+a^{n-1})。

边界：(sum(1)=1)。

要用快速乘，防止爆(long long)。

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll m, a, c, x0, n, g;

ll read()
{
	ll x = 0ll, fl = 1ll; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') fl = -1ll; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = (x << 1ll) + (x << 3ll) + ch - '0'; ch = getchar();}
	return x * fl;
}

ll mul(ll x, ll y)
{
	ll rs = 0ll;
	while (y)
	{
		if (y & 1ll) rs = (rs + x) % m;
		x = (x + x) % m;
		y >>= 1ll;
	}
	return rs;
}

ll qpow(ll base, ll p)
{
	ll rs = 1;
	while (p)
	{
		if (p & 1ll) rs = mul(rs, base);
		base = mul(base, base);
		p >>= 1ll;
	}
	return rs;
}

ll calc(ll t)
{
	if (t == 0ll) return 0ll;
	if (t == 1ll) return 1ll;
	ll sum = 0;
	if (t % 2ll == 0ll) sum = (sum + mul(calc(t / 2ll), (1ll + qpow(a, t / 2ll))) % m) % m;
	else sum = (sum + qpow(a, t - 1ll) + mul(calc((t - 1ll) / 2ll), (1ll + qpow(a, (t - 1ll) / 2ll))) % m) % m;
	return sum % m;
}

int main()
{
	m = read(); a = read(); c = read(); x0 = read(); n = read(); g = read();
	c %= m; x0 %= m; a %= m;
	printf("%lld
", ((mul(qpow(a, n), x0) + mul(c, calc(n))) % m + g) % g);
	return 0;
}