题解：AT_arc037_d [ARC037D] Chaotic Polygons

· · 题解

题目大意

已经说的很清楚了

思路分析

首先注意到谢宾斯基三角形有自相似性，猜测前一层的答案可以用于求出这一层的答案，考虑递推。

令 f_i 为 i 阶谢宾斯基三角形内的简单多边形数量。
根据定义可以得知，这个三角形由上、左、右三个 i-1 阶谢宾斯基三角形（后称其子三角形）组成，于是 f_i 至少包含了 3f_{i-1}。

这三个部分各自的贡献已经求完了，考虑求合并起来的贡献，也就是会跨越子三角形的多边形。
可以发现，这个多边形一定会经过三个子三角形的三个交点，那么不妨把它拆成三部分，也就是在一个三角形内，从一个顶点到另一个定点的合法路径数量。

令 g_i 为这个东西，考虑从右下角到左下角的情况，可以发现有两种情况：经过 / 不经过上面的子三角形。

于是推出 g_{i+1}=g_i^2+g_i^3。
但这样对吗？
考虑经过上子三角形的情况，会发现我们不能保证正下方那个点是否被使用。
考虑转换思路，我们希望更有力地控制它的路径，就需要定义更多的状态，于是，我们让 g_i 表示从一个顶点到另一个顶点，且经过第三个点的合法路径数，h_i 表示从一个顶点到另一个顶点，且不经过第三个点的合法路径数。

因为我不会容斥，所以考虑硬推，手玩一下可以看见这么多种情况：

细细数一数，就可以得到一个不用容斥的递推式了：

\begin{aligned} g_{i+1}&=2g_i^2h_i+g_ih_i^2\\ h_{i+1}&=h_i^2+h_i^3+2g_ih_i+2g_ih_i^2+g_i^2\\ f_{i+1}&=3f_i+(g_i+h_i)^3 \end{aligned}

代码展示

// 为观感已删去 %mod
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+5,mod=1e9+7;
int L;
int f[N],g[N],h[N];

signed main(){
    cin>>L;
    f[0]=1;
    g[0]=1;
    h[0]=1;
    for(int i=1;i<=L;i++){
        g[i]=(2*g[i-1]+h[i-1])*g[i-1]*h[i-1];
        h[i]=((((h[i-1]*h[i-1]+h[i-1]*h[i-1]*h[i-1])+2*g[i-1]*h[i-1])+g[i-1]*g[i-1])+2*g[i-1]*h[i-1]*h[i-1]);
        f[i]=(3*f[i-1]+(g[i-1]+h[i-1])*(g[i-1]+h[i-1])*(g[i-1]+h[i-1]));
    }
    cout<<f[L];
    return 0;
}