题号很吉利我们把这个正多边形展开成一条线段，转化成经典区间DP问题。毕竟n3的算法也不是很多
然后，对于题目中要求两条连线不能相交，相当于线段上的两个区间要么相离，要么相切，要么包含。对于不能连的两个点，在DP的时候特判一下就行。
#include<bits/stdc++.h> using namespace std; #define int long long const int N=666; int dp[N][N][6],n,a[N][N]; const int mod=1e9+7; signed main(){ //l97gtl87fr8l cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) cin>>a[i][j]; dp[i][i][0]=1; } for(int len=2;len<=n;len++){ for(int l=1,r=len;r<=n;l++,r++){ if(a[l][r]) { for(int k=l;k<r;k++){ dp[l][r][0]+=(dp[l][k][0]+dp[l][k][1])*(dp[k+1][r][0]+dp[k+1][r][1]); dp[l][r][0]%=mod; } } for(int k=l+1;k<r;k++){ if(!a[l][k]) continue; dp[l][r][1]+=dp[l][k][0]*(dp[k][r][0]+dp[k][r][1]); dp[l][r][1]%=mod; } } } cout<<(dp[1][n][0]+dp[1][n][1])%mod; //otf8o7fr8ol6fr8o6fr return 0; }