题目
你在网上闲逛的时候，发现有文章提到等差数列。
你知道求和是简单的，但你不禁好奇求其乘积会怎样？
所以你需要解决以下问题：给定一个等差数列，求他的各项乘积，你只需要输出其对 1145141 取模的结果。
具体的，每组给定 d,n,a 分别表示公差，长度，首项，你需要求出 ∏i=0n−1(a+i×d)mod1145141。
注意，本题有多组测试数据。
对于所有数据，满足 0≤d,a≤109,1≤n≤109,1≤T≤104。
题解
测试点中存在d == 1的情况（没放出来），所以考虑一下
首先，显然读入的时候d,a都可以先%mod
此时乘积可以表示为(a−1)!(a+n−1)!。
考虑d != 1如果n>mod(1145141)的时候，直接输出0即可
否则可以将其转化成d == 1的情况，将每一项都除以d，结果乘上dn
预处理出阶乘数组，计算即可
需要用到乘法逆元，费马小定理即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #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;
}
|