P2675三角圣地

Posted on Edited on In Word count in article: 362 Reading time ≈ 1 mins.
Lucas

P2675 《瞿葩的数字游戏》T3-三角圣地

emmmmm, 这眨眼一看像是个杨辉三角之类的东西, 定眼一看好像不太对啊

每次把上面两堆合并起来, 显然越靠近中间在最后的结果中出现次数越多, 越靠近两端次数越少, 考虑贪心

所以数列大概长成这个样子: \[ 2, 4, 6,\cdots,2(k-1),2k,2k-1,\cdots,5,3,1 \] 所以可以得出: \(2k-1\)与\(2k\)出现的频率是相通的并没啥用

答案可以记为:

\[ Ans = \sum\limits_{i=1}^nc_i\cdot A_i \] 打一个表, 与似乎发现系数就\(TM\)是杨辉三角了啊, 模数很小, 快乐\(Lucas\)

Code

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
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e6 + 10, Mod = 1e4 + 7;
int N, Ans;
int Num[Maxn], Fac[Maxn] = {1}, Inv[Maxn] = {1};

inline int Pow(int X, int Y)
{
    int Ans(1);
    while (Y)
    {
        if (Y & 1) Ans = Ans * X % Mod;
        X = X * X % Mod;
        Y >>= 1;
    }
    return Ans;
}

inline void Init()
{
    for (int i = 1; i <= N; ++i) Fac[i] = Fac[i - 1] * i % Mod;
    for (int i = 1; i <= N; ++i) Inv[i] = Pow(Fac[i], Mod - 2);
}

inline int C(int N, int M)
{
    if (M > N) return 0;
    return Fac[N] * Inv[M] % Mod * Inv[N - M] % Mod; 
}

inline int Lucas(int N, int M)
{
    if (!M) return 1;
    return Lucas(N / Mod, M / Mod) * C(N % Mod, M % Mod) % Mod;
}

int main()
{
    scanf ("%d", &N);
    Init();
    for (int i = 2; i <= N; i += 2) Num[i >> 1] = i;
    for (int i = 1; i <= N; i += 2) Num[N - (i >> 1)] = i;
    for (int i = 1; i <= N; ++i) Ans = (Ans + Num[i] % Mod * Lucas(N - 1, i - 1) % Mod) % Mod;
    printf ("%d\n", Ans % Mod);
    system("pause");
}