题目地址：TopCoder Arena：Practice – TopCoder Arena、vjudge：MaximalTriangle – TopCoder 12054 – Virtual Judge

题目描述

You are given ints n and z. We have a regular n-gon: a convex polygon with n sides, in which all sides have the same length and all internal angles are equal. We want to draw (n-3) non-intersecting diagonals in some way. Once we do that, we will have the polygon divided into exactly (n-2) triangles. We want to produce a situation in which one of these (n-2) triangles has a strictly larger area than each of the remaining (n-3).
The vertices of the polygon are labeled 1 through n in clockwise order. Two sets of diagonals are different if one of them contains a diagonal that is not present in the other one. Count all sets of (n-3) non-intersecting diagonals that produce an arrangement with the above property. Return that count modulo z.
求一个正n边形的三角剖分方案中面积最大的三角形唯一的方案数。给出n和模数k。

定义名

类名：MaximalTriangle
函数名：howMany
参数：int, int
返回值：int
函数声明：int howMany(int n, int z)

样例

样例#1：

4
1000000000

样例#1结果：

0

其他样例参见原网站。

说明

n will be between 3 and 444, inclusive.
z will be between 1 and 1,000,000,000 (10^9), inclusive.

题解

其实这个题把我折磨了一下午。官方题解只有文字（英文）没有程序，我半天想不出来怎么写，然后学习使用TopCoder Arena进Practice Room抄代码才解决了这个题。在这里推荐各位在vjudge上交，TC真的很难学。附官方题解：SRM 547 – TopCoder Wiki。这道题是SRM 547 Div 1 Level 3。
让我们从浅入深地揭示这个出题人卡常毒瘤的实质。
首先，我们考虑最开始的想法，就是想一种动规去解决这个问题。我们考虑枚举面积最大的那个三角形，它最多将多边形分为3块，就像下面这个多边形。

我们分别对这三块进行DP处理里面的三角剖分方案。我们考虑类似卡特兰数的计算方法，在一块中先找一个面积小于最大三角形的三角形，然后它会把这块再割成两块，再乘法原理将两块的答案乘起来。定义dp[i]为跨越i条边的一块的三角剖分方案数，转移方程即
dp[i] = \sum (dp[j] * dp[i - j])
如果我们给顶点命名为A1…An，那么上式能够转移的条件是A1、Ai、Aj组成的三角形面积小于最大三角形。
最后的答案应该是枚举的每一种三角形的三边跨越的边数的dp值乘起来，再把每种枚举情况的答案加起来。
枚举需要O(n^2)复杂度，而DP也需要O(n^2)，因此总体复杂度应该是O(n^4)的。但是这会被毒瘤出题人卡掉常数。下面就是一些官方提供的卡常手段。

• DP可以只计算到最大三角形三边最长的边跨越多少原多边形边数。比如示例图中最长边是1或3，跨越的边数就是3。
• 如果有一块剖出来的小块里面所有的三角形都小于最大三角形，那么这里的答案就是卡特兰数（详情见卡特兰数在多边形剖分上的应用），即 dp[i]=c[i - 1] 。实现上可以先把卡特兰数算出来。
• DP过程中，经常会发现dp[j] * dp[i - j]在后面变成了dp[i - j] * dp[j]，在求和中出现了两次。我们考虑只算一次然后乘个2，实现上就是每个dp值在最后乘个2。实现上，就是我们考虑以割出来的一块中最长的那条边为三角形的一条边，然后枚举顶点，这个顶点一定是在对面的中间部分三角形面积比较大。如果这个时候三角形面积已经比最大三角形面积小了，那么就算卡特兰数，否则在这里停止DP，因为后半部分的DP是对称的。下面是“中间位置”的演示。
  • 
• unsigned long long可以存很大的数，不用每乘一次都取模，可以考虑乘多个几次，到快超了的时候再取模，具体而言，这个题比较安全的分界点是8 \times 10^{18}。

上面就是官方提供的卡常办法。实际上这个题的实现难度也是有的。比如快速搞出来正多边形内部各种三角形的面积。下面是这一段的代码。

for(int i = 0; i < n; i++) {
    ang[i] = 2 * PI * i / n ;
}
for(int i = 1; i < n; i++) {
    for(int j = 1; j < n - i; j++) {
        area[i][j] = fabs(sin(ang[i]) + sin(ang[j]) - sin(ang[i + j]));
    }
}

area[i][j]的意思是规定一个点不变，从这个点顺时针走i条边到达的顶点和逆时针走j条边到达的顶点（当然你可以反着定义）三个点构成的三角形的一个面积的表示。这个的原理是什么呢。我们看下面这张图。

实际上在这个图里，若我们规定这个正八边形的中心到各顶点的距离为1，以α为内角的三角形面积为\frac{1}{2} \sin \alpha，相似地，剩下两个小三角形面积分别为\frac{1}{2} \sin \beta、\frac{1}{2} \sin \gamma。我们观察到\gamma = 2 \pi - \alpha - \beta，而\alpha = \frac{2 \pi}{n} \cdot i, \beta = \frac{2 \pi}{n} \cdot j, 2 \pi - \gamma = \frac{2 \pi}{n} \cdot (i + j)。那么我们把每个\sin(\frac{2 \pi}{n} \cdot i)都处理出来不就好办了嘛。至于上面的1/2，就不管它了，反正这个值能代表这个三角形的面积。
剩下的实现并不是很有难度，但是优化难理解。可以对照代码注释和上面的卡常手段一起对比理解。

代码

由于TopCoder要求实现一个class，下面的代码并不是标准输入/输出格式（传统OI题目）的实现方式，但是把调试注释给去掉就可以用标准输入/输出了。

// Code by KSkun, 2018/3
//#include <cstdio>
#include <cmath>
#include <cstring>

typedef long long LL;

const int MAXN = 505;
const double PI = 2 * acos(0.0), EPS = 1e-9;
const LL INF = 8e18;

class MaximalTriangle {
public:
    int MO;
    double ang[MAXN], area[MAXN][MAXN];
    LL cat[MAXN], dp[MAXN];

    inline void add(LL &x, LL y) {
        x += y;
        if(x >= INF) x %= MO;
    } 

    void caldp(double s, int m) {
        dp[0] = 0;
        dp[1] = 1 % MO; // 这是出题人的一个坑，模数可以为1，但是其实我很反感这种坑，考着玩可以，但是这根算法真的没啥关系吧
        for(int i = 2; i <= m; i++) {
            int mid = i / 2; 
            if(area[mid][i - mid] + EPS < s) { // “中间位置”的三角形最大，如果这个三角形都比最大三角形小，那么直接取卡特兰数
                dp[i] = cat[i];
                continue;
            }
            dp[i] = 0;
            for(int j = 1; area[j][i - j] + EPS < s; j++) {
                add(dp[i], dp[j] * dp[i - j]); // 如果当前枚举到的这个三角形符合条件，那么可以DP转移
            }
            dp[i] %= MO;
            dp[i] += dp[i]; // 重复一遍，因为转移的情况是对称的，可以避免重复计算
            dp[i] %= MO;
        }
    }

    int howMany(int n, int z) {
        MO = z;
        // 下面是预处理卡特兰数
        memset(cat, 0, sizeof cat);
        cat[1] = 1 % MO;
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j < i; j++) {
                add(cat[i], cat[j] * cat[i - j]);
            }
            cat[i] %= MO;
        }
        // 下面是预处理各种三角形的面积
        for(int i = 0; i < n; i++) {
            ang[i] = 2 * PI * i / n ;
        }
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < n - i; j++) {
                area[i][j] = fabs(sin(ang[i]) + sin(ang[j]) - sin(ang[i + j]));
            }
        }
        // 下面是解题的核心
        LL ans = 0;
        for(int i = 1; i < n; i++) {
            for(int j = i; j < n - i; j++) {
                int k = n - i - j, comb = n; // i, j, k分别代表最大三角形三边分别跨越了多少原多边形的边
                if(k < j) continue; // 总是使i, j, k递增，保证枚举的情况不重
                if(i == j && j == k) comb /= 3; // 如果发现是正三角形，那么旋转n次中会有2/3的情况重叠
                if(i != j && j != k) comb *= 2; // 如果发现三条边都不一样，那么把这个情况对称过来又是一种情况，这里避免重复计算
                caldp(area[i][j], k);
                add(ans, (comb * dp[i] % MO) * (dp[j] * dp[k] % MO));
            }
        }
        return ans % MO;
    }
};

/*int main() {
    MaximalTriangle t;
    int n, z;
    scanf("%d%d", &n, &z);
    printf("%d", t.howMany(n, z));
    return 0;
}*/