原题 这题涉及到了一些求逆元的知识，我们刚好回顾一下。

首先很明显这题答案是： $$ \sum_{i=0}^{n-1} a_i C_{n-1}^i \bmod 10. $$

数据范围也不大，可以暴力 O(n2) 求组合数，或者你直接模拟题意就行。

但作为Acmer必然要考虑更高效的做法。如果模数不是10而是一个质数 p，那么可以直接使用费马小定理来直接计算组合数分母的那些阶乘的逆元： $$ a^p \equiv a \space (\bmod \space p). $$

但是这题的10显然不是质数，怎么办呢？诶，我们还有个欧拉定理： $$ a^{\phi(b)} \equiv 1\space (\bmod \space b),\gcd(a,b)=1. $$

只要我们要求逆元的数 a 和10互质，就可以用欧拉定理求出它的逆元，即 aϕ(10) − 1 = a3.

可以考虑先将 a 中的质因子2和5全都提出。考虑我们要求的组合数 $C_n^m=\frac{n!}{m!(n-m)!}$，我们先考虑提出 m! 和 (n − m)! 中所有的2和5的质因子： $$ C_n^m = \dfrac{n!}{2^{k_2{(m!)}}5^{k_5{(m!)}}left(m!) \times 2^{k_2{((n-m)!)}}5^{k_5{((n-m)!)}}left((n-m)!)}. $$

emmm，left(m!) 就是 m! 除去所有2和5质因子的剩下的部分，有点抽象，毕竟我数学不好不知道怎么科学地表示。

我们可以用欧拉定理很容易求出 left(m!) 和 left((n − m)!) 的逆元，但是对于质因子部分，我们似乎无计可施。

这里是整个题最难的部分，就是你得先猜个结论：设 a 是 x! 中质数 p 的幂的个数，b 是 y! 中质数 p 的幂的个数，c 是 (x + y)! 中质数 p 的幂的个数，则有： a + b ≤ c.

怎么证明呢？我也不会，但是可以感性证明：(x + y)! 首先把 x! 中 p 的幂数消耗掉了，剩下的是从 x + 1 一直乘到 x + y，这些中每个数都和 1 到 y 一一对应，即分别是它的倍数，自然也能消耗掉 y! 所有的幂。

当然正常的证明可能需要用到质数幂计数公式（Legendre公式），涉及到级数，很抽象。

因此我们可以将 n! 也提出2和5的幂，然后除去 m! 和 (n − m)! 的2和5的幂，得到的肯定是个整数。

假设剩下的2的幂的个数有 x 个，那么它遵循着一个循环节，你可以手玩一下，循环节是 [2, 4, 8, 6]，而5的幂模10只能是5。

因此这题就做完了，给个代码吧： 

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
class Solution {
public:
    const int MOD2[4] = {2, 4, 8, 6};
    int p2[1010];
    int p5[1010];
    int f[1010] = {1};
    int invf[1010] = {1};

    int powmod(int x, int k)
    {
        x %= 10;
        int ret{1};
        while(k)
        {
            if(k & 1) ret = ret * x % 10;
            x = x * x % 10;
            k >>= 1;
        }
        return ret;
    }

    void init(int n)
    {
        for(int i = 1; i <= n; ++i)
        {
            int cnt2{}, cnt5{};
            int x{i};
            while(x % 2 == 0)
            {
                ++cnt2;
                x /= 2;
            }
            while(x % 5 == 0)
            {
                ++cnt5;
                x /= 5;
            }
            f[i] = f[i-1] * x % 10;
            invf[i] = powmod(f[i], 3);
            p2[i] = p2[i-1] + cnt2;
            p5[i] = p5[i-1] + cnt5;
        }
    }

    int C(int n, int k)
    {
        return f[n] * invf[k] % 10 * invf[n-k] % 10
            * (p2[n] - p2[k] - p2[n-k] > 0 ? MOD2[(p2[n] - p2[k] - p2[n-k] - 1) % 4] : 1) % 10
            * (p5[n] - p5[k] - p5[n-k] > 0 ? 5 : 1) % 10;
    }

    int triangularSum(vector<int>& nums) {
        int n = nums.size();
        int ans{0};
        init(n);
        for(int i = 0; i < n; ++i)
        {
            ans += nums[i] * C(n-1, i) % 10;
            ans %= 10;
        }
        return ans;
    }
};

当然这题也有个Lucas定理的做法。