题解 多边形

OK，这是本蒟蒻的第3个题解

---

注意看，首先，如果你是一名初学者，不要灰心，因为请看VCR

n在1~3的测试点里仅小于等于3，并且题目中n的数据范围是 $\large 3 ≤ n ≤ 5000$
所以就说明n=3，那么你只需要写一个最简单的三角形三边的判断就行了

int solve1(){
    if(l[0]+l[1]>l[2]&&l[0]+l[2]>l[1]&&l[1]+l[2]>l[0])return 1;
    return 0;
}

时间复杂度是 $\large O(1)$
爆砍12分，爽不爽！！！

---

如果你是一名略懂位运算的小白，不要慌张因为依旧看VCR

不难看出，数据非常小，让我们来思考一下
如果将每次选哪几根木棒转化成一个n位的二进制数，第 i 位为 1 代表选，第 i 位为 0 代表不选
举个栗子，$\large n=5$，一个二进制数 $\large (10101)_{2}$，就是选第 1,3,5 根木棒
那么是不是就可以直接枚举就行了，去掉空集 ( 即n位二进制数每一位都是0 ) 那么从 1 开始枚举到 $\large 2^{n}-1$
然后内层再跑个循环，去枚举选没选第 i 个数，最后再判断

void solve2(){
    int ans=0;
    for(int mask=1;mask<(1<<n);mask++){//枚举每一种方案
        int sum=0,maxn=0,cnt=0;//分别表示总长度，最大长度和棒子数
        for(int i=0;i<n;i++){
            if(mask&(1<<i)){//判断是否选了第i位，即mask的第i位是否为1
                sum+=l[i];//累加长度
                maxn=max(maxn,l[i]);//更新最大值
                cnt++;//更新边数
            }
        }
        if(sum>maxn+maxn&&cnt>=3)ans=(ans+1)%mod;//满足条件，ans+1
    }
    cout<<ans;//输出
}

时间复杂度是 $\large O(2^{n}\cdot n-n)$
爆砍40分，够用了

---

但如果你还略懂一点数学，那么事情又不一样了

哇塞，全是1耶，怎么搞
那不就是直接一个用 $\large 总方案数-(n=0)方案数-(n=1)方案数-(n=2)方案数$
哇塞，好高级，但是为甚么
因为当$\large n ≥ 3$时，绝对能组成$\large C^{i}_{n}$当且仅当$(3 ≤ i ≤ n)$种，但那样计算起来肥肠的让人相思，所以直接反着来
那么只要计算$\large 2^{n}-C^{0}_{n}-C^{1}_{n}-C^{2}_{n}$
也就是$\large 2^{n}-1-n-\frac{n\cdot(n-1)}{2}$就OK了

void solve3(){//前提是l[i]全是1
    ll tot=qpow(2LL,(ll)n,(ll)mod);//跑一遍快速幂，此处不做展示
    ll c0=1LL;
    ll c1=(ll)n%mod;
    ll c2=n*(n-1)/2%mod;
    cout<<((tot-c0-c1-c2)%mod+mod)%mod;//计算合法方案数，+mod防负数
}

时间复杂度$\large O(logn)$
在刚才的代码的基础上加上它，直接就是一个64分，这不直接拿1等

---

最后，你是不是想问，如果我非常的乐色，第三题不会前缀异或怎么办，难道我的一等梦要陨落了吗
OK，那么直接想办法拿下剩下的36分
想一想，我们现在为什么无法通过剩下的测试点，因为时间复杂度是 $\large O(2^{n}\cdot n-n)$，根本过不了$n=500$和$n=5000$
那么我们就要将时间复杂度降低
我们还是原来的思路，用 $\large 总方案数-不合理方案数$
总方案数就是$\large 2^{n}-1$，虽然空集是不合理的，但是提前减掉，后面就不用再去算了，你也可以输出的时候用
$\large 2^{n}-不合理方案数-1$，本质上都是一样的，因为在循环内部我们不会去计算空集

这样的话，我们的任务就明朗了，就是计算不合理方案数
注意看，我们改一下约束式子

$$\Large 长度和>长度最大值\times2$$

$$\Large 其余长度和+长度最大值>长度最大值\times2$$

$$\Large 其余长度和>长度最大值$$

也就是说，我们可以先给原数组排个序，设当前第 i 个为长度最大值，在内部去跑一个循环 $\large 0 ≤ j ≤ l_{i}$，因为不合理方案数是不满足上述不等式的，也就是不合理方案数满足$\large 其余长度和≤长度最大值$，排序则是为了保证第 i 根木棒是前缀最大值
j 便是其余长度和，我们可以定义一个$\large dp[j]$表示前$\large i-1$根木棒长度为 j 的方案数
那么就是让$\large 不合理方案数+dp[j]$
然后再去更新dp数组，使用01背包的方法，$\large dp[j]=dp[j]+dp[j-l[i]]$
什么，你说你不会01背包，没关系，过会注释里会让你看明白
这里有个点要注意，两个内层for是不能换位置的，因为你以 $\large l[i]$ 为最大值时，统计的是$\large 0 ≤ j ≤ l_{i}$，其余长度和为j的方案数
而更新 dp 数组是更新从$\large l[i]$开始到5000结束的，会包含$l[i]$，也就是如果两段交换，$l[i]$就会记录更新过的值，导致答案错误

void solve4(){
    vector<ll>dp(5005,0);//看数据，l[i]最大为5000
    ll tot=((qpow(2LL,(ll)n,(ll)mod))-1+mod)%mod;//算总方案数，+mod防负数
    sort(l.begin(),l.end()-1);//这里-1是因为我的l开了n+1的空间，正常数组不用-1，正常sort就行
    dp[0]=1;//空集方案数为1
    ll bad=0;//用来统计不合理方案数
    for(int i=0;i<n;i++){
        for(int j=0;j<=l[i];j++){//遍历其余长度和
            bad=(bad+dp[j])%mod;//累加
        }
        for(int j=5000;j>=l[i];j--){//倒序遍历防重复，因为先更新大的后面小的是用不到的，如果先更新小的，可能后面大的会用到，会重复计算
            //j=5000是因为l[i]最大就5000
            //j>=l[i]是因为选择l[i]会增加长度和，不选l[i]长度和不变，但一定不会低于l[i]的长度，也就是只选第i根
            dp[j]=(dp[j]+dp[j-l[i]])%mod;
            //dp[j]表示不选第i根，方案数还是dp[j]
            //dp[j-l[i]]的意思是选了第i根后，要使长度和还是j，那么其余长度和必须为j-l[i]，那么方案数为dp[j-l[i]]
            //两者相加，表示新的方案数，这里如果看不明白可以喂给AI或者去洛谷，毕竟我也只是蒟蒻
        }
    }
    cout<<(tot-bad+mod)%mod;//计算合理方案数,+mod防负数
}

时间复杂度$\large O(n\cdot max(l[i]))$，同时l[i]最大只有5000，所以差不多就是$\large O(n\cdot 5000)$
这样又能砍掉36分，拿下100分

接下来，是完整代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int mod=998244353;
typedef long long ll;
int n;
vector<int>l;
ll qpow(ll a,ll b,ll p){
    ll res=1;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int solve1(){
    if(l[0]+l[1]>l[2]&&l[0]+l[2]>l[1]&&l[1]+l[2]>l[0])return 1;
    return 0;
}
void solve2(){
    int ans=0;
    for(int mask=1;mask<(1<<n);mask++){
        int sum=0,maxn=0,cnt=0;
        for(int i=0;i<n;i++){
            if(mask&(1<<i)){
                sum+=l[i];
                maxn=max(maxn,l[i]);
                cnt++;
            }
        }
        if(sum>maxn+maxn&&cnt>=3)ans=(ans+1)%mod;
    }
    cout<<ans;
}
void solve3(){
    ll tot=qpow(2LL,(ll)n,(ll)mod);
    ll c0=1LL;
    ll c1=(ll)n%mod;
    ll c2=n*(n-1)/2%mod;
    cout<<((tot-c0-c1-c2)%mod+mod)%mod;
}
void solve4(){
    vector<ll>dp(5005,0);
    ll tot=((qpow(2LL,(ll)n,(ll)mod))-1+mod)%mod;
    sort(l.begin(),l.end()-1);
    dp[0]=1;
    ll bad=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=l[i];j++){
            bad=(bad+dp[j])%mod;
        }
        for(int j=5000;j>=l[i];j--){
            dp[j]=(dp[j]+dp[j-l[i]])%mod;
        }
    }
    cout<<(tot-bad+mod)%mod;
}
int main(){
    cin>>n;
    bool all_one=1;
    l.resize(n+1,0);
    for(int i=0;i<n;i++){
        cin>>l[i];
        if(l[i]!=1)all_one=0;
    }                                          
    if(n<=3){                                               
        cout<<solve1();
    }else if(n<=20){                                                                                                                   
        solve2();
    }else if(all_one){
        solve3();
    }else{
        solve4();
    }
    return 0;
}

有用的话点个赞吧，制作不易，谢谢观看