問題#
あなたがオンラインでブラウジングしていると、等差数列について言及している記事を見つけました。
和を求めるのは簡単ですが、その積はどうなるのか気になってしまいます。
そこで、次の問題を解決する必要があります：与えられた等差数列の各項の積を求め、その結果を $1145141$ で割った余りを出力してください。
具体的には、各グループで $d,n,a$ がそれぞれ公差、長さ、首項を表し、$\prod_{i=0}^{n-1} (a+i\times d) \mod 1145141$ を求める必要があります。
注意：この問題には複数のテストデータがあります。
すべてのデータに対して、$0\le d,a \le 10^9,1\le n\le 10^9,1\le T\le 10^4$ が成り立ちます。
解答#
テストケースには d == 1 の場合が存在するため（公開されていません）、考慮する必要があります。
まず、明らかに読み込むときに $d, a$ は先に%modを取ることができます。
このとき、積は $\frac {(a+n-1)!}{(a-1)!}$ として表すことができます。
d != 1 の場合、もし $n > mod (1145141)$ であれば、直接0を出力すればよいです。
そうでなければ、d == 1 の場合に変換し、各項を d で割り、結果に $d^n$ を掛けます。
階乗配列を前処理して計算します。
乗法逆元を使用する必要があり、フェルマーの小定理を使います。
コード#
#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;
}