洛谷 P10893 城市化发展委员会 题解

· · 题解

Description

定义一个序列为「安全的」当且仅当其所有前缀和均大于 0。

先给定一个长度为 n 的序列 A_0，将进行如下操作 k 次：

求 \dfrac{|A_{k+1}|}{|A_k|}。

Solution

首先考虑 k=0 的情况。

我们只需统计满足以第 t 位开头的序列是「安全的」的 t 的个数（我们称满足条件的 t 所代表的位置是「被标记的」）。

则我们需要用到前缀和的极小值，线段树或树状数组维护即可。

接着拓展到 k>0 的情况，我们令 f(p) 表示 A_p 中「被标记的」位置的个数，考虑如何计算 f(p)。

首先，在前一个序列 A_p 中「被标记的」位置在当前序列 A_{p+1} 一定是「被标记的」，并且 A_{p+1} 的长度是 A_p 的 f(p) 倍。

那么有 \forall p\in[1,k],f(p)\ge f^2(p-1)。

接着考虑是否会出现新的「被标记的」位置。

如图，若设红色的圈表示在 A_p 中「被标记的」的位置，绿色的圈表示 A_{p+1} 中新出现的「被标记的」的位置，则各个颜色所代表的矩形对应相同，且各矩形的前缀和一定大于 0。

那么在 A_p 中，以绿色的圈开头也是一个「安全的」序列，矛盾。

因此 f(p)=f^2(p-1)，依次计算 f(p),p\in[1,k]，答案即为 f(p)。

AC Code

#include <bits/stdc++.h>
using namespace std;
const int p=998244353;
int n,k;
long long a[2000005];
struct Node{
    int l,r;
    long long Min;
}tree[8000005];
void build(int p,int l,int r){
    tree[p].l=l,tree[p].r=r;
    if (l==r){
        tree[p].Min=a[l];
        return;
    }
    int Mid=(l+r)>>1;
    build(p<<1,l,Mid);
    build(p<<1|1,Mid+1,r);
    tree[p].Min=min(tree[p<<1].Min,tree[p<<1|1].Min);
}
long long query(int p,int l,int r){
    if (l<=tree[p].l&&tree[p].r<=r) return tree[p].Min;
    int Mid=(tree[p].l+tree[p].r)>>1;
    long long res=1e18;
    if (l<=Mid) res=query(p<<1,l,r);
    if (r>Mid) res=min(res,query(p<<1|1,l,r));
    return res;
}
int qpow(int a,int b){
    int res=1;
    for (;b;b>>=1,a=1ll*a*a%p) if (b&1) res=1ll*res*a%p;
    return res;
}
int main(){
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i+n]=a[i];
    for (int i=1;i<=2*n;i++) a[i]+=a[i-1];
    build(1,1,2*n);
    int ans=0;
    for (int i=1;i<=n;i++) if (query(1,i,i+n-1)>a[i-1]) ans++;
    for (int i=1;i<=k;i++) ans=1ll*ans*ans%p;
    printf("%d\n",ans);
    return 0;
}