凸多边形 [动态规划, 计数]

凸多边形


color{red}{正解部分}

一个 多边形 若为 凸多边形, 则需满足: 除去 最大边 所有边的权值和要 大于 最大边 的权值 .

f[i,j]f[i, j] 表示前 ii 个数字, 凑成 jj 的方案数,
g[i,j]g[i,j] 表示前 ii 个数字, 凑成 jj 的所有方案的权值和, 状态转移 如下:

f[i,j]=f[i1,ji]+f[i1,j]g[i,j]=g[i1,ji]+f[i1,ji]+g[i1,j]f[i,j] = f[i-1,j-i]+f[i-1,j] \ g[i, j] = g[i-1, j-i]+f[i-1,j-i] + g[i-1,j]

最大边ii 的方案数为 j=i+1i(i1)2g[i1,j]sumlimits_{j=i+1}^{frac{i(i-1)}{2}}g[i-1, j] , ans=i=1Nj=i+1i(i1)2(g[i1,j]+f[i1,j])ans = sumlimits_{i=1}^Nsumlimits_{j=i+1}^{frac{i(i-1)}{2}}(g[i-1, j] + f[i-1, j]), 时间复杂度 O(N3)O(N^3) .

考虑 补集转换, 对 最大边 ii, 计算 res=i=1Nj=0i(g[i1,j]+f[i1,j])res = sumlimits_{i=1}^Nsumlimits_{j=0}^{i} (g[i-1, j] + f[i-1, j]), 然后使用 “总方案权值和”: tot=i=1Nj=0i(i1)2(g[i1,j]+f[i1,j])tot = sumlimits_{i=1}^Nsumlimits_{j=0}^{frac{i(i-1)}{2}}(g[i-1, j] + f[i-1, j]) 减去 resres 得到 ansans,

现在考虑如何快速求 tottot, 其意义为计算出 ii 必须被选, [1,i1][1, i-1] 所有挑选数字方案的权值和, 再加起来,

对每个 ii, 其对 tottot 贡献为 2i2(i1)+2i12^{i-2}(i-1)+2^{i-1}, 所以 tot=i=1N2i2(i1)+2i1tot = sumlimits_{i=1}^N 2^{i-2}(i-1)+2^{i-1} .

特别地, i=1i=1tottot 的贡献为 11 .

tottot 可以 O(N)O(N) 预处理, 于是 总时间复杂度 O(N2)O(N^2) .


color{red}{实现部分}

#include<bits/stdc++.h>
#define reg register

const int maxn = 1005;
const int mod = 1e9 + 7;

int N;
int pw[maxn];
int tot[maxn];
int f[maxn][maxn];
int g[maxn][maxn];
int gsum[maxn][maxn];

int Ksm(int a, int b){ int s=1; while(b){ if(b & 1) s = 1ll*s*a%mod; a=1ll*a*a%mod; b >>= 1; } return s; }

void Init(){
        f[0][0] = 1;
        pw[0] = 1; for(reg int i = 1; i < maxn; i ++) pw[i] = 2ll*pw[i-1] % mod;
        for(reg int i = 1; i < maxn; i ++)
                for(reg int j = 0; j < maxn; j ++){
                        f[i][j] = f[i-1][j], g[i][j] = g[i-1][j];
                        if(j >= i){
                                f[i][j] += f[i-1][j-i]; 
                                if(f[i][j] >= mod) f[i][j] -= mod; 
                                g[i][j] += (g[i-1][j-i] + f[i-1][j-i]) % mod; 
                                if(g[i][j] >= mod) g[i][j] -= mod;
                        } 
                }
        for(reg int i = 0; i < maxn; i ++) 
                for(reg int j = 0; j < maxn; j ++){
                        if(j) gsum[i][j] += gsum[i][j-1];
                        gsum[i][j] += g[i][j];
                        if(gsum[i][j] >= mod) gsum[i][j] -= mod;
                        gsum[i][j] += f[i][j];
                        if(gsum[i][j] >= mod) gsum[i][j] -= mod;
                }
        tot[1] = 1;
        for(reg int i = 2; i < maxn; i ++){
                tot[i] = tot[i-1];
                tot[i] += (1ll*pw[i-2]*(i-1)%mod + pw[i-1]) % mod;
                if(tot[i] >= mod) tot[i] -= mod;
        }
}

void Work(){
        scanf("%d", &N);
        int res = 0;
        for(reg int i = 1; i <= N; i ++){
                res += gsum[i-1][i];
                if(res >= mod) res -= mod;
        }
        int Ans = (tot[N]-res+mod) % mod;
        Ans = 1ll*Ans*Ksm(Ksm(2, N), mod-2) % mod;
        printf("%d
", Ans);
}

int main(){
        Init();
        int T; scanf("%d", &T);
        while(T --) Work();
        return 0;
}
原文地址:https://www.cnblogs.com/zbr162/p/11822432.html