题解 CF15E Triangles

Tenderfoot · 2021-09-27 22:19:30 · 题解

我们先观察小三角形

从顶点 A 出发并回到顶点 A，有以下逆时针路径：

1. A\rightarrow B\rightarrow C
2. A\rightarrow D\rightarrow F\rightarrow A
3. A\rightarrow B\rightarrow E\rightarrow C\rightarrow A
4. A\rightarrow D\rightarrow E\rightarrow C\rightarrow A
5. A\rightarrow B\rightarrow E\rightarrow F\rightarrow A

共 5 条路径。因此加上顺时针路径，我们共 10 条路径可以选择。

我们令 Ans 为从点 u 向下走，再从点 v 返回上来的方案数。对于上图来说，我们可以分为以下几种来进行讨论：

1. 从边下到底再从中间上来，如方案 2,4 所述。则此时逆时针路径的贡献为 Ans。
2. 从中间下去，从边上回来，如方案 2,5 所述。此时逆时针路径的贡献为 Ans。
3. 从边上下去，从边上返回。如方案 2 所述。此时逆时针路径贡献为 Ans。

对于情况 1,2，由于顺时针和逆时针相互对称，因此可以得到贡献为 8\times Ans，对于情况 3，同样的，我们有贡献为 2\times Ans^2。因此总贡献为

观察题目中所给的图形，因为不能经过黑色区域，所以对于第 i 层，我们最多从边上向中间行进 i-2 个点。不难发现，如果我们向中间前进 i 个点，那么就有 2^{i+1} 种方案。

以此类推，经过 k 层时，我们有方案数 2^k-3。

最后加上返回操作。其情况类似于上面的分类讨论，不过多叙述。我们有总方案数

代码

#include<bits/stdc++.h>

#define Mod 1000000009
#define int long long
#define MAXN 1000010
#define Enter puts("")
#define Space putchar(' ')
#define Test_Begin Enter , puts("Test--------------")
#define Test_End Enter , puts("--------------------")

using namespace std;

constexpr int INF = 2147483647;

static inline int Read()
{
    int Ans = 0;
    char Ch = getchar(), Las = ' ';
    while (!isdigit(Ch))
    {
        if (Ch == '-')
            Las = '-';
        Ch = getchar();
    }
    while (isdigit(Ch))
    {
        Ans = Ans * 10 + Ch - '0';
        Ch = getchar();
    }
    if (Las == '-')
        Ans = -Ans;
    return Ans;
}

static inline void Write(int x)
{
    if (x < 0)
    {
        x = -x;
        putchar('-');
    }
    if (x >= 10)
        Write(x / 10);
    putchar(x % 10 + '0');
}

int Res[MAXN] , Pow[MAXN];
int Ans;

signed main()
{
    int n = Read();
    n >>= 1;
    Res[1] = Pow[0] = 1;
    for(register int i = 1; i <= n; i++)
        Pow[i] = Pow[i - 1] * 2 % Mod;
    for(register int i = 2; i <= n; i++)
        Res[i] = Res[i - 1] * (Pow[i] - 3) % Mod;
    for(register int i = 2; i <= n; i++)
        Ans = (Ans + 4 * Res[i]) % Mod;
    int _Ans(10 + 8 * Ans % Mod + 2 * Ans * Ans % Mod);
    Write(_Ans % Mod);
    return 0;
}