厦门网站制作全程服务,app推广在哪里可以接单,爱途 中山网站制作,佛山网站建设官网Description 小C是一个算法竞赛爱好者#xff0c;有一天小C遇到了一个非常难的问题#xff1a;求一个序列的最大子段和。 但是小C并不会做这个题#xff0c;于是小C决定把序列随机打乱#xff0c;然后取序列的最大前缀和作为答案。 小C是一个非常有自知之明的人#xff0c… Description 小C是一个算法竞赛爱好者有一天小C遇到了一个非常难的问题求一个序列的最大子段和。 但是小C并不会做这个题于是小C决定把序列随机打乱然后取序列的最大前缀和作为答案。 小C是一个非常有自知之明的人他知道自己的算法完全不对所以并不关心正确率他只关心求出的解的期望值 现在请你帮他解决这个问题由于答案可能非常复杂所以你只需要输出答案乘上n!后对998244353取模的值显然这是个整数。 注最大前缀和的定义i∈[1,n],Sigma(aj)的最大值,其中1ji Solution 注意到前缀和的取值只有 \(2^n\) 种. 然后可以枚举每一个集合的元素当最大前缀和 , 那么这个集合的元素排列之后每一个后缀都必须大于 \(0\) , 且这个集合的补集排列之后必须保证每一个前缀和都小于 \(0\). 那么状压 \(DP\) 就行了 , 设 \(f[i]\) 表示集合 \(i\) 作为最大前缀和且排列之后每个后缀都大于 \(0\) 的方案数 , \(g[i]\) 表示集合 \(i\) 中元素排列之后每个前缀都小于 \(0\) 的方案数. 强制 \(f,g\) 必须在合法的时候才能转移就行了. #includebits/stdc.h
using namespace std;
const int N25,mod998244353;
int f[120],n,a[N],m,g[120],sum[120];
int main(){freopen(pp.in,r,stdin);freopen(pp.out,w,stdout);cinn,m(1n)-1;for(int i0;in;i)cina[i];for(int i0;in;i)for(int j0;jm;j)if(ji1)sum[j]a[i];for(int i0;in;i)f[1i]1,g[1i]1;for(int i0;im;i){if(sum[i]0){for(int j0;jn;j)if(~ij1)f[i^(1j)](f[i^(1j)]f[i])%mod;}else{for(int j0;jn;j)if(~ij1)g[i^(1j)](g[i^(1j)]g[i])%mod;}}g[0]1;int ans0;for(int i0;im;i)if(sum[m^i]0)ans(ans1ll*f[i]*sum[i]%mod*g[m^i])%mod;cout(ansmod)%mod;return 0;
}转载于:https://www.cnblogs.com/Yuzao/p/9304011.html
