Arithmetic - histcat

Problem#

While browsing online, you came across an article mentioning arithmetic sequences.

You know that summing them is straightforward, but you can't help but wonder what the product would be like?

So you need to solve the following problem: given an arithmetic sequence, calculate the product of its terms, and you only need to output the result modulo $1145141$.

Specifically, for each set of inputs $d,n,a$ representing the common difference, length, and first term respectively, you need to calculate $\prod_{i=0}^{n-1} (a+i\times d) \mod 1145141$.

Note that there are multiple test cases for this problem.

For all data, the constraints are $0\le d,a \le 10^9,1\le n\le 10^9,1\le T\le 10^4$.

Solution#

There are cases in the test points where d == 1 (not disclosed), so consider this.

First, it is clear that when reading the input, both $d$ and $a$ can be taken modulo mod.

At this point, the product can be expressed as $\frac{(a+n-1)!}{(a-1)!}$.

For the case of d != 1, if $n > mod(1145141)$, you can directly output 0.

Otherwise, you can convert it to the case of d == 1 by dividing each term by $d$, and multiplying the result by $d^n$.

Precompute the factorial array and calculate accordingly.

You will need to use the multiplicative inverse, which can be derived using Fermat's Little Theorem.

Code#

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int mod = 1145141;
int fact[mod * 2 + 10];
int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}

	return f * x;
}

int fast_pow(int a, int n)
{
	int ans = 1;
	while(n)
	{
		if(n & 1)
		{
			ans = ans * a % mod;
		}
		n >>= 1;
		a = 1ll * a * a % mod;
	}
	return ans;

}

int T, d, n, a;

signed main()
{
	freopen("sequence.in", "r", stdin);
        freopen("sequence.out", "w", stdout);
	fact[0] = 1;
	for(int i = 1;i <= mod * 2;i++)
	{
		fact[i] = 1ll * i * fact[i - 1] % mod;
	}
	T = read();

	while(T --)
	{
		d = read() % mod, n = read(), a = read() % mod;
		if(d == 0)
		{
			printf("%lld\n", fast_pow(a, n));
		}
		else if(n > mod)
		{
			printf("0\n");
		}
		else if(a == 0)
		{
			printf("0\n");
		}
		else
		{
			a = 1ll * a * fast_pow(d, mod - 2) % mod;
			printf("%lld\n", (1ll * fast_pow(d, n) % mod * fact[a + n - 1] % mod * fast_pow(fact[a - 1], mod - 2) % mod) % mod);
		}

	}
	return 0;
}