东莞网站建设网站排名优化网络营销策划书1500字

原题链接：E - Avoid K Partition

题意：给长度为n的数组，将数组划分成任意份，但是每一份的总和都不能是k，问有多少种分割方法。

思路：dp，f[i]，代表前i个元素满足题意的划分的总和，那么转移方程就是，j是从1到i-1，然后如果从j到i这一段的总和是k，那么就减去f[j]，对于任意的f[i]来说，这样是不重不漏的，那么可以很容易写出一个n*2的算法，可以观察到，这个算法的瓶颈是在减去j到i总和是k的这一步上，从前缀和的角度考虑，对于每个从j到i总和为k来说，从1到j的总和都是一样的值，那么就可以用map来记录一下，从1到j总和为键，从1到j的划分方法为值，这样时间复杂度就可以了。

//冷静，冷静，冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
#define count2(x) __builtin_popcountll(x)
#define is2(x) __builtin_ffsll(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=998244353;
ll pre[N],p[N],f[N];
void Jiuyuan()
{ll n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>p[i];pre[i]=pre[i-1]+p[i];}map<ll,ll> op;op[0]=1;f[0]=1;ll sum=1;for(int i=1;i<=n;i++){f[i]=(sum-op[pre[i]-k]%mod+mod)%mod;op[pre[i]]=(op[pre[i]]+f[i])%mod;sum=(sum+f[i])%mod; }cout<<f[n];
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;
//	cin>>T;while(T--){Jiuyuan();}return 0;
}