Wuyanru's blog
0%

[CF1738E] Balance Addicts

发表于 分类于 ，

一道有趣的数列题，然而场上没有做出来。

看完题解发现跟我想的差不多，就是我码风太屎。

里面分类讨论和组合数学的部分感觉出的很不错。

主要是对官方题解的翻译，并加入了我的理解。

题目链接。

题意

现在有一个数列 你需要将这个数列分为若干非空的段。

假设你将这个数列分成了 段，分成的所有段中，第 段中所有数字的和为 。

我们称一种分的方法为平衡的，当且仅当对于每一个 ，都有 。

求一共有多少种平衡的分法，对 取模。

多组数据。

题解

首先我们来考虑一个暴力的思路。

设 为区间 的答案，我们要求的就是 。

我们暴力枚举最左边和最右边区间的范围，进行转移。

时间复杂度是 的。

虽然这个时间复杂度无法接受，但是这个方法可以优化。

现在我们来看具体求一个区间 的方法，大力分类讨论：

  1. ，那么显然所有方法都可行，所以答案为 。

  2. ，我们设区间 最左边共有 个连续的 ，最右边一共有 个连续的 。

    如果分成的区间中，最左边和最右边 段的和都为 ，那么此时方案数为

    其中 表示将左边的 个 分成 段（左边的 段是上一行说的和为 的 段，最后一段给区间 最左边的一段分过去），并且其中 段要求非空的方案数， 同理。

    最后整个乘以 表示考虑了最左边和最右边的 段以后，中间切分的方案数。

    所以此时最终答案为 。

  3. 对于剩下的情况，我们设：

    最小的 使得存在一个 满足：。

    一个最大的 使得对于上述的 满足 。

    这个 和 可以使用双指针去找。

    然后再进行分类讨论：

    1. 如果 或 ，说明这个序列不存在分成 段的方案，所以此时答案为 。

      并且可以注意到，对于所有剩余的情况，肯定会有 ，并且 。

    2. 。

      可以知道，此时当且仅当 中所有元素在同一段里， 中所有元素在同一段里，这个切分方案就是合法的。

      所以此时答案为 。

    3. 对于剩下的所有情况，我们设区间 中最左边共有 个连续的 ，最右边共有 个连续的 。

      当且仅当满足这三个条件是，一个切分方案是合法的：

      1. 区间 在同一段， 在同一段。
      2. 区间 中和为 的段数=区间 中和为 的段数。
      3. 区间 的切分方案合法。

      所以我们还是枚举区间 中共有 段和为 。

      这时方案数为 。

      其中 表示将左边这些 分为 段（中间的 段是上面说的和为 的 段，最左边的一段给 ，最右边的一段给 ），并且中间 段非空的方案数。 同理。

      所以此时的方案数为 。

      之所以有一个 ，是因为存在方案，使得 全部属于 的最左边的一段， 全部属于 的最右边的一段。

直接递归就可以了，细节不算多，但是也不算特别少。

时间复杂度 。

需要预处理阶乘及其逆元，也可以做到 。

代码

我懒了亿点，预处理写的是 的。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
using ll=long long;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
ll qow(ll a,int b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll inv[200001];
ll jc[200001];
int pre[100001];
int a[100001];
int n;
inline void init()
{
    jc[0]=inv[0]=1;
    for(int i=1;i<=200000;i++)
    {
        jc[i]=jc[i-1]*i%mod;
        inv[i]=qow(jc[i],mod-2);
    }
}
inline ll C(int a,int b)
{
    return jc[a]*inv[b]%mod*inv[a-b]%mod;
}
inline ll solve(int l,int r)
{
    if(pre[r]-pre[l-1]==r-l+1) return qow(2,r-l);
    if(a[l]==0&&a[r]==0)
    {
        int x=0,y=0;
        while(a[l]==0) x++,l++;
        while(a[r]==0) y++,r--;
        ll ans=0;
        for(int i=0;i<=x&&i<=y;i++) ans=(ans+C(x,i)*C(y,i))%mod;
        ans=ans*solve(l,r)%mod;
        return ans;
    }
    ll suml=0,sumr=0;int x=l-1,y=r+1;
    while(suml!=sumr||suml==0)
    {
        if(suml<=sumr) suml+=a[++x];
        else sumr+=a[--y];
    }
    if(y==l||x==r) return 1;
    if(pre[y-1]-pre[x]==y-x-1) return qow(2,y-x);
    int l0=0,r0=0,nx=x+1,ny=y-1;
    while(a[nx]==0) l0++,nx++;
    while(a[ny]==0) r0++,ny--;
    ll ans=1;
    for(int i=0;i<=l0&&i<=r0;i++) ans=(ans+C(l0+1,i+1)*C(r0+1,i+1))%mod;
    return ans*solve(nx,ny)%mod;
}
int main()
{
    init();
    int T=read();
    while(T--)
    {
        n=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
            pre[i]=pre[i-1]+(a[i]==0);
        }
        printf("%lld\n",solve(1,n));
    }
    return 0;
}

感谢观看！