题目#

你在网上闲逛的时候，发现有文章提到等差数列。

你知道求和是简单的，但你不禁好奇求其乘积会怎样？

所以你需要解决以下问题：给定一个等差数列，求他的各项乘积，你只需要输出其对 $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$

预处理出阶乘数组，计算即可

需要用到乘法逆元，费马小定理即可

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4
#define int long long
5
const int mod = 1145141;
6
int fact[mod * 2 + 10];
7
int read()
8
{
9
  int f = 1, x = 0;
10
  char ch = getchar();
11
  while(ch < '0' || ch > '9')
12
  {
13
    if(ch == '-') f = -1;
14
    ch = getchar();
15
  }
16

17
  while(ch >= '0' && ch <= '9')
18
  {
19
    x = x * 10 + ch - '0';
20
    ch = getchar();
21
  }
22

23
  return f * x;
24
}
25

26
int fast_pow(int a, int n)
27
{
28
  int ans = 1;
29
  while(n)
30
  {
31
    if(n & 1)
32
    {
33
      ans = ans * a % mod;
34
    }
35
    n >>= 1;
36
    a = 1ll * a * a % mod;
37
  }
38
  return ans;
39

40
}
41

42
int T, d, n, a;
43

44
signed main()
45
{
46
  freopen("sequence.in", "r", stdin);
47
        freopen("sequence.out", "w", stdout);
48
  fact[0] = 1;
49
  for(int i = 1;i <= mod * 2;i++)
50
  {
51
    fact[i] = 1ll * i * fact[i - 1] % mod;
52
  }
53
  T = read();
54

55
  while(T --)
56
  {
57
    d = read() % mod, n = read(), a = read() % mod;
58
    if(d == 0)
59
    {
60
      printf("%lld\n", fast_pow(a, n));
61
    }
62
    else if(n > mod)
63
    {
64
      printf("0\n");
65
    }
66
    else if(a == 0)
67
    {
68
      printf("0\n");
69
    }
70
    else
71
    {
72
      a = 1ll * a * fast_pow(d, mod - 2) % mod;
73
      printf("%lld\n", (1ll * fast_pow(d, n) % mod * fact[a + n - 1] % mod * fast_pow(fact[a - 1], mod - 2) % mod) % mod);
74
    }
75

76
  }
77
  return 0;
78
}

等差

https://blog.histcat.top/posts/sequence/

作者

Histcat

发布于

2023-09-29

许可协议

CC BY-NC-SA 4.0

阶乘

正方形