题目传送门qwq

对于当前的一个序列 $a_1,a_2,a_3\cdots a_n$ ,假设最大前缀和的终止位置为 $p$ ,考虑 $p$ 会满足什么条件:

首先,不存在一个 $k$ 使得 $\sum_{i=p+1}^{k}a_i\geq 0$ 。证明:假设有这么一个 $k$ ,那么终止位置显然不为 $p$ ,这个时候令终止位置为 $k$ 的收益更大,也就是说这样的局面下终止位置为 $k$ 而非 $p$ ,与之前的假设矛盾,不合法。

然后还有就是,很显然也不存在一个位置 $l(l>1)$ ,使得 $\sum_{i=l}^{p}a_i< 0$ 。显然这样子的话就 没必要取 $[l,k]$ 这一段区间的数了,这个时候 $l$ 作为最终位置一定比 $p$ 优,与之前的假设相矛盾,不合法。

将 $p$ 与 $p$ 前面的属于最大前缀和的数看作一个序列,$p$ 后面不属于最大前缀和的数看作一个序列。显然上面的两个条件可以理解为第一个序列必须满足每一个后缀的和都 $\geq 0$ ,第二个序列必须满足每一个前缀的和都 $<0$ ,分别求方案数即可。


设 $f(S)$ 表示选择了 $S$ 集合中的数,组成满足"每一个后缀(除去整体,也就是长度为 $|S|$ 的那一个后缀,毕竟题目要求了最大前缀和不能为空)的和都 $\geq0$ "条件的序列的方案数。

设 $g(S)$ 表示选择了 $S$ 集合中的数,组成满足"每一个前缀的和都 $\leq0$ "条件的序列的方案数。

最后的答案显然就是 $\sum_{S}f(S)\times g(2^n-1-S)\times sum(S)$ ,其中 $sum(S)$ 表示集合 $S$ 中所有数字的和。


最后只需要考虑如何求 $f(S)$ 与 $g(S)$ 了。

转移很简单,每一次枚举一个没有加入过的数 $a[i]$ 加入进来,然后判断一下新的前缀/后缀是否满足要求即可。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=22;
const int M=(1<<20)+1;
const ll mod=998244353;
int n,limit;
ll a[N],f[M],g[M],sum[M];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int main() {
    IN(n),limit=(1<<n)-1;
    for(int i=1;i<=n;++i) IN(a[i]),f[1<<(i-1)]=1;
    for(int S=1;S<=limit;++S)
        for(int i=1;i<=n;++i) if(S&(1<<(i-1))) sum[S]+=a[i];
    g[0]=1;
    for(int S=0;S<=limit;++S)
        for(int i=0;i<n;++i) if(S&(1<<i)) {
            if(sum[S^(1<<i)]>=0) (f[S]+=f[S^(1<<i)])%=mod;
            if(sum[S]<0) (g[S]+=g[S^(1<<i)])%=mod;
        }
    ll ans=0;
    for(int S=0;S<=limit;++S) (sum[S]+=mod)%=mod;
    for(int S=1;S<=limit;++S)
        (ans+=1ll*f[S]*sum[S]%mod*g[limit^S]%mod)%=mod;
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 12 月 11 日 01 : 43 PM