Znzryb's Blog
0%

ABC - 370 - E - Avoid K Partition

Posted on Edited on

AC代码

这题题意很简单，把一段序列分为若干个子序列，要求这些子序列的和≠k，统计这种子序列的分法，mod 998244353

样例的计算过程如下

3 3
1 2 3

问分法种数，即2种

推出思路是这样的，不断枚举末尾

image

O（n^2）优化嘛就是用map维护之前的j
// 我们需要sumA[j]!=sumA[i]-k; 那为何不反过来想，把==的排除掉不就好了吗？

主要思路如上

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=2e5+10,mod=998244353;
ll n,k,A[N],sumA[N],dp[N];      // dp[i]的意思是以i为结尾时，有多少种分法可行
map<ll,ll> occSum;              // occSum[i]  i表示对应sum值，occSum[i]表示该sum值累计方案数  occ即occurred简写
ll currSum;                     // i之前的现在的方案数总和
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i) {
        cin>>A[i];
        sumA[i]=sumA[i-1]+A[i];
    }
    dp[0]=1;
    occSum[0]=1;
    currSum+=dp[0];
    for(int i=1;i<=n;++i) {
        // 我们需要sumA[j]!=sumA[i]-k;那为何不反过来想，把==的排除掉不就好了吗？
         if(occSum.count(sumA[i]-k))
             dp[i]=(dp[i]%mod+currSum%mod-occSum[sumA[i]-k]%mod+mod)%mod;
        else
            dp[i]=currSum%mod;
        occSum[sumA[i]]=(occSum[sumA[i]]%mod+dp[i]%mod+mod)%mod;
        currSum=(currSum%mod+dp[i]%mod+mod)%mod;
        // for(int j=i-1;j>=0;--j) {
        //     if(sumA[i]-sumA[j]!=k)
        //         dp[i]=(dp[i]%mod+dp[j]%mod)%mod;
        // }
    }
    cout<<dp[n]<<endl;
}
// 哈哈，第一次提交忘记mod了   https://atcoder.jp/contests/abc370/submissions/59317169
// AC https://atcoder.jp/contests/abc370/submissions/59320083

心路历程（WA，TLE，MLE……）

如果发现WA的比较多，但是又觉得没啥问题，可能是没mod的问题

WA，原因就是C++的%是取余，而题目要求取模，故要在%的时候加一个mod。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=2e5+10,mod=998244353;
ll n,k,A[N],sumA[N],dp[N];      // dp[i]的意思是以i为结尾时，有多少种分法可行
map<ll,ll> occSum;              // occSum[i]  i表示对应sum值，occSum[i]表示该sum值累计方案数  occ即occurred简写
ll currSum;                     // i之前的现在的方案数总和
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i) {
        cin>>A[i];
        sumA[i]=sumA[i-1]+A[i];
    }
    dp[0]=1;
    occSum[0]=1;
    currSum+=dp[0];
    for(int i=1;i<=n;++i) {
        // 我们需要sumA[j]!=sumA[i]-k;那为何不反过来想，把==的排除掉不就好了吗？
         if(occSum.count(sumA[i]-k))
             dp[i]=(dp[i]+currSum-occSum[sumA[i]-k])%mod;
        else
            dp[i]=currSum%mod;
        occSum[sumA[i]]=(occSum[sumA[i]]+dp[i])%mod;
        currSum=(currSum+dp[i])%mod;
        // for(int j=i-1;j>=0;--j) {
        //     if(sumA[i]-sumA[j]!=k)
        //         dp[i]=(dp[i]%mod+dp[j]%mod)%mod;
        // }
    }
    cout<<dp[n]<<endl;
}
// 哈哈，第一次提交忘记mod了   https://atcoder.jp/contests/abc370/submissions/59317169