P5369 [PKUSC2018]最大前缀和
2024-10-06 11:06:08
状态压缩
P5369
题意:求所有排列下的最大前缀和之和
一步转化: 求最大前缀和的前缀由数集S组成的方案数, 统计答案时直接乘上sum(S)即可
考虑最大前缀和的性质:
设最大前缀和为sum[i]
- 到i的后缀均为正数
- i后的前缀均为负数
令sum[i] = 集合 i 内所有数的和。
令f[i] = 集合 i内的数组成的排列,最大前缀和 = sum[i]的方案数。
令g[i] = 集合 i内的数组成的排列,所有的最大前缀和都 < 0 的方案数。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 25;
const int P = 998244353;
int n, a[N];
int f[1050050], g[1050050];
int sum[1050050];
inline int to(int x) {
return 1 << x;
}
int main() {
cin >> n; int all = to(n) - 1;
for (int i = 1;i <= n; i++)
cin >> a[i], f[to(i-1)] = 1, sum[to(i-1)] = a[i];
for (int i = 1;i <= all; i++)
sum[i] = sum[(i & -i)] + sum[i ^ (i & -i)];
g[0] = 1;
for (int i = 0;i < all; i++) {
if (sum[i] >= 0) {
for (int j = 1;j <= n; j++)
if (!(i & to(j-1)))
f[i | to(j-1)] = ((long long)f[i] + f[i | to(j-1)]) % P;
}
else {
for (int j = 1;j <= n; j++)
if (i & (to(j-1)))
g[i] = ((long long)g[i] + g[i ^ to(j-1)]) % P;
}
}
long long ans = 0;
for (int i = 1;i <= all; i++)
ans = (ans + (long long)f[i] * g[all^i] % P * sum[i] % P) % P;
cout << (ans % P + P) % P << endl;
return 0;
}
最新文章
- 判断字符串是否相等 isEqualToString:
- Delphi中的函数指针判断是否为空
- 理论沉淀:隐马尔可夫模型(Hidden Markov Model, HMM)
- 终端上设置git
- IoC容器Autofac正篇之类型注册(四)
- [置顶] 遇到难题(bug)的解决方法心得
- 【Luogu P2709 小B的询问】莫队
- 判定你的java应用是否正常(是否内存、线程泄漏)的一个简单方法
- 为UITextField增加MaxLength特性
- 【linux基础】关于ARM板子使用O3编译选项优化
- ftok()函数深度解析
- Django view 视图
- 015 在大数据中,关于mapreduce的粗略优化,以及mapreduce的处理过程解释
- 【Java】生成图形验证码
- 在线安装WordPress更新 失败的解决办法
- ESXi6.5中将虚拟机从厚置备转换为精简置备
- hdu 3951 硬币围成一圈(博弈)
- UVa 11925 Generating Permutations (构造法)
- .net core redis使用
- 20155302 2016-2017-2 《Java程序设计》第二周学习总结
热门文章
- Nacos高可用集群解决方案-Docker版本
- 【linux】【qt5】【信号槽示例】
- P3980 [NOI2008]志愿者招募 费用流 (人有多大胆地有多大产
- URAL-1982-Electrification Plan最小生成树或并查集
- CF 435B Little Pony and Harmony Chest
- codeforces E. DNA Evolution(树状数组)
- Java日志框架总结
- 【Offer】[20] 【表示数值的字符串】
- I don&#39;t Blame You that You don&#39;t Understand Me
- 010 深入理解Python语言