OI题解 - Count Subsequences(Codechef)


什么时候信息竞赛也要期末考试了……
第一场的难度顺序好像不大对劲,把 T1T3 AC 了然后 T2 爆零 qwq


# 题面

> Codechef传送门

如果一个整数序列的各元素之和可以被给定整数 $K$ 整除,则称这个序列是好的。给定整数序列 $A_1,A_2,…,A_N$。Hasan想计算该序列有多少子序列是好的。不过这样的话问题就太简单了,因此Hasan决定再加一个限制。

任意非空下标序列 $i_1< i_2< \cdots < i_L$对应子序列$A_{i_1}, A_{i_2},…, A_{i_L}$。如果满足 $i_L-i_1\ge W$,则称这个子序列非常好。请帮Hasan统计非常好的子序列方案数。由于答案可能非常大,请输出方案数对$10^9+7$ 取模的结果。

(多组数据,每个数据点包含 $T$ 组数据)

数据规模:
- $1\le T\le1000$;
- $1\le N\le 10^5$,$0\le W\le N-1$;
- $0\le A_i\le K-1$,$2\le K\le50$;
- 每个数据点中的所有 $N$ 之和不超过 $3\times 10^5$;


# 解析

如果没有 $W$ 的限制,这道题是一道非常简单的 DP,类似于背包。大概也不需要说了。

考虑在 $W$ 的限制下怎样求答案。首先我们固定所选子序列的左端点(最左边元素)位置为 $L$,那么就必须要在 $[L+W,N]$ 这段区间内选择至少一个元素。最后把所有位置作为 $L=1\text~N$ 对应答案求和就可以了,不难发现因为每一次固定的左端点不同,所以这样求和得到的方案数不重不漏。

假设现在确定了 $L$,怎样计算方案数?
设计 DP 状态 f[i][j] 表示已经在 $A_{L+1}\text~A_i$ 这些元素中选取了一些元素,且元素之和模 $K$ 余 $j$ 的方案数。那么下面的转移应该很好理解:

啊哈?
然后方案数就是“在 $A_{L+1}\text~A_N$ 中选取的元素之和被 $K$ 整除的方案数”-“在 $A_{L+1}\text~A_{L+W-1}$ 中选取的元素之和被 $K$ 整除的方案数”(这样减了就可以保证一定在 $A_{L+W}\text~A_N$ 中选取了至少一个元素了)。

但是不可能枚举 $L$ 然后每个都分别计算。

于是题解中所说的分治是这样的:定义“询问区间”为 $[L,L+W]$。从初始区间 $[1,N]$ 开始,求解每个被包含在当前区间中的询问区间 的答案;设当前区间为 $[left,right]$ 定义 $mid$ 为区间中点,递归求解 $[left,mid]$、$[mid+1,right]$。

求解每个被包含在当前区间中的询问区间 的答案的过程如下:

定义 DP 状态 fl[i][j] 表示在 $A_i\text~A_{mid}$ 中选出一些元素,这些元素之和模 $K$ 余 $j$ 的方案数;fr[i][j] 表示在 $A_{mid+1}\text~A_i$ 中选出一些元素,……(同上)的方案数。转移就没必要说了。先把这些 DP 值处理出来。

(感觉不是很方便叙述,不如我举个栗子)

  1. 询问区间跨过区间中点:

    jpg1

    那么询问区间的答案就是“必须选L,L+1~mid随便选的方案数”乘“mid+1~L+W-1随便选,L+W~right至少选一个的方案数”。用 DP 值表示就是 (fl[L][j]-fl[L+1][j])*(fr[right][j_]-fr[L+W-1][j_]) (其中 j_j 之和为 K 或 0)。

  2. 询问区间完全在左区间:

    jpg2

    这样无法直接算出完整的答案,但是可以把答案拆成两步计算:
    ①必须选L,在 $[mid+1,right]$ 中至少选一个,$[L+1,mid]$ 随便选的方案数;
    ②必须选L,不在 $[mid+1,right]$ 中选,但是在 $[L+W,mid]$ 中至少选一个,$[L+1,L+W-1]$ 随便选的方案数;

    可以发现这两个方案加起来恰好能不重不漏地得到所有选择的方案。

    对于 ①,可以用当前的 DP 值计算出:(fl[L][j]-fl[L+1][j])*(fr[right][j_]-fr[mid][j_])

    对于 ②,可以递归求解:在左区间 $[L,mid]$ 中求解,一定是能够计算完的。

算法思想就是这样。

复杂度分析其实很简单:因为这样取中点递归,最多会递归 $\log N$ 层;每一层计算 fl[i][j]fr[i][j] 都需要枚举 i=1~Nj=0~K-1,均摊 $O(NK)$;枚举询问区间在每一层中也是 $O(N)$ 的。

因此复杂度是 $O(NK\log N)$。


# 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5,MOD=1e9+7;
#define fix(x) (((x)%mod+mod)%mod)

int n,len,mod,cas;
long long ans;
int num[N+3],flef[N+3][50],frig[N+3][50];

void Solve(int lef,int rig){
if(rig-lef<=len-1) return;
if(rig==lef){
if(num[lef]==0) ans=(ans+1)%MOD;
return;
}
int mid=(lef+rig)>>1;
Solve(lef,mid);Solve(mid+1,rig);
for(int j=0;j<mod;j++) flef[mid+1][j]=frig[mid][j]=0;
frig[mid][0]=1;flef[mid+1][0]
for(int i=mid+1;i<=rig;i++)
for(int j=0;j<mod;j++)
frig[i][j]=(frig[i-1][j]+frig[i-1][fix(j-num[i])])%MOD;
for(int i=mid;i>=lef;i--)
for(int j=0;j<mod;j++)
flef[i][j]=(flef[i+1][j]+flef[i+1][fix(j-num[i])])%MOD;
for(int i=lef;i+len<=rig && i<=mid;i++)
for(int j=0;j<mod;j++){
int J=fix(mod-j);
long long vlef=(flef[i][j]-flef[i+1][j]+MOD)%MOD,
vrig=(frig[rig][J]-frig[max(i+len-1,mid)][J]+MOD)%MOD;
ans=(ans+vlef*vrig%MOD)%MOD;
}
}
int main(){
scanf("%d",&cas);
while(cas--){
scanf("%d%d%d",&n,&mod,&len);
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
ans=0;
Solve(1,n);
printf("%lld\n",ans);
}
return 0;
}

The End

Thanks for reading!

啊,文化课要期末考试了!

0%