子序列

君のNOIP。 · 2020-09-19 15:19:35 · 题解

------------ ### 数据点 $1\sim 4$： $O(2^nn)$ 暴力枚举子序列即可。 ------------ ### 数据点 $12$：$k=0

合法的子序列均只有一个元素，答案显然为 \sum \limits _{i=1} ^n a_i^2。

数据点 5\sim 11： O(n^2) 暴力递推。

先不考虑不合法的子序列，即 k=n-1 的情况，将 \sum \limits _{i=1} ^ x s_i 和 \prod \limits _{i=1} ^ x s_i 分开看。

设 f_n 为考虑前 n 个元素的答案。

显然 f_n 表示的答案中由 2^n -1 个非空子集组成，设第 i 个子集的值为 w_i \times b_i

显然 f_n 的形式为 \sum \limits _{i=1} ^ {2^n-1} w_i \times b_i 。

再设 g_n =\sum \limits _{i=1} ^ {2^n-1} b_i 。

那么 f_{n+1} 表示的答案由 3 个部分组成：

那么我们分别考虑这 3 个部分可以得到：

\\ & = a_{n+1}^2 + f_n + \sum \limits _{i=1} ^ {2^n-1} (w_i \times b_i \times a_{n+1} + b_i \times a_{n+1}^2 ) \\ & = a_{n+1}^2 + f_n + f_n \times a_{n+1} + g_n \times a_{n+1}^2 \\ & = a_{n+1}^2 \times (g_n + 1) + f_n \times ( a_{n+1} + 1 ) \end{aligned}

关于 g_n，根据乘法结合律，同理考虑 3 个部分易得：

\\ & = a_{n+1} \times (g_n+1) + g_n \end{aligned}

f_{n+1} = a_{n+1}^2 \times ( g_n + 1) + f_n \times ( 1 + a_{n+1} )

于是我们就可以 O(n) 同时递推两个式子，答案即为 f_n。

而现在我们需要考虑去掉不合法的序列。

改设 f_{i,j} 为 i \le p_1 \le p_x \le j 的所有子序列的值之和， g_{i,j} 同理。

发现由上式的原理可以由 f_{i,j} 推至 f_{i-1,j} 和 f_{i,j+1}， g_{i,j} 同理。

根据基本容斥原理，答案为 \sum \limits _{i=1} ^{n-k} f_{i,i+k} - \sum \limits _{i=2} ^{n-k} f_{i,i+k-1}。

数据点 15\sim 17： O(nlogn) 逆元。

根据前文中推出的式子，同理：

f_{i,j} = f_{i+1,j} \times (a_i + 1 ) + a_i ^ 2 \times g_{i+1,j}

移项得：

f_{i+1,j} = ( f_{i,j} - a_i ^ 2 \times g_{i+1,j} ) / ( a_i + 1 )

同理 g_{i,j} 可推得 g_{i+1,j}。

由于 mod = 10^9+7，是质数，我们只需用逆元即可运用类似双指针的方法推得答案。

数据点 18\sim 22： O(nlogn) 合并区间 \&倍增。

我们是否能由 f_{i,l} 和 f_{l+1,j} 合并得 f_{i,j} 呢？

方法与由 f_{i,j} 推至 f_{i,j+1} 是一样的，同理可推得：

f_{i,j} = f_{i,l} \times (g_{l+1,j} + 1 ) + f_{l+1,j} \times (g_{i,l} + 1 )

g_{i,j} = g_{i,l} + g_{l+1,j} + g_{i,l} \times g_{l+1,j}

接下来只要利用倍增的思想，预处理出 f_{i,i+2^j-1},g_{i,i+2^j-1} ,再倍增求出 f_{i,i+k} 和 f_{i+1,i+k} 即可。

时空复杂度都是 O(nlogn)。

数据点 23\sim 25：

正解 O(n)，但由于这是乐多赛制缺少试错的机会，且作为信心赛题目，良心出题人放了很多略加优化的 O(nlogn) 乱搞做法通过。

乱搞一：

仍然倍增，但空间会炸，于是我们类似分块，以 10 为块大小，再倍增记录每块的信息即可。空间上足够了，但是由于常数巨大，经测试，#23 很难卡过去。

乱搞二：

据说有方法可以实现膜数非质数逆元，不太了解这里就不讲了，但时间复杂度仍然要 O(nlogn)。

乱搞三：

区间合并，区间查询，显然可以线段树，时间复杂度 O(logn)，空间复杂度 O(n)。

注意由于要同时合并 f_{i,j},g_{i,j}，求和的时候要是分两个函数求解，则会产生重复递归（和 T1 不加 map 记忆化搜索是一个道理），时间复杂度会退化成 O(n^2)。

我的方法是直接用 pair<> 作函数类型，如果有其它方法欢迎评论提出。

但由于线段树巨大的常数还是有一定风险的，事实上出题人写的线段树这 3 个点一个都过不去。

正解：分块。

大家都知道分块一般是 n^{1.5} 的，但这里不太一样。

因为我们要求的区间长度只有 k 和 k+1。

所以我们可以以 k 为块的大小，设 i 所在块左边界为 l_i，右边界为 r_i。

则我们只需预处理出 f_{l_i,i},f_{i,r_i}，则计算答案的时候每次也只要合并两个区间 f_{i,r_i},f_{l_j,j} 即可。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define G() Cr = getchar()
#define LL long long
LL Xr, Fr; char Cr;
inline LL rd() {
    Xr = 0, Fr = 1, G();
    while(Cr < '0' || Cr > '9') {if(Cr == '-') Fr = -1; G();}
    while(Cr >= '0' && Cr <= '9') Xr = (Xr<<1) + (Xr<<3) + (Cr&15), G();
    return Xr * Fr;
}
#define MAX_N 1000005
LL n, k, mod;
LL va[MAX_N], f[MAX_N][3], b[MAX_N][3], l[MAX_N], r[MAX_N], ans, s; // 0 -> from left ; 1 -> from right

LL work( LL L, LL R ) {
    if( L == R ) return va[L] * va[L] % mod;
    if( l[L] == l[R] ) return f[R][0];
    LL x, y, A, B;
    x = f[L][1], y = f[R][0];
    A = b[L][1], B = b[R][0];
    return ( x + y + A * y % mod + B * x % mod ) % mod;
}

int main() {
    n = rd(), k = rd(), mod = rd();
    for( int i = 1; i <= n; i++ ) va[i] = rd();
    if(!k) {
        for( int i = 1; i <= n; i++ ) ans = ( ans + va[i] * va[i] ) % mod;
        cout << ans;
        return 0;
    }
    for( int i = 1; i <= n; i++ ) l[i] = ( i - 1 ) / k * k + 1, r[i] = ( ( i - 1 ) / k + 1 ) * k;
    for( int i = 1; i <= n; i++ ) {
        if( i == l[i] ) b[i][0] = va[i], f[i][0] = va[i] * va[i] % mod;
        else {
            f[i][0] = (va[i] * va[i] % mod * ( 1 + b[i-1][0] ) % mod + f[i-1][0] * ( 1 + va[i] ) % mod ) % mod;
            b[i][0] = ( b[i-1][0] * ( 1 + va[i] ) + va[i] ) % mod;
        }
    }
    for( int i = n; i >= 1; i-- ) {
        if( i == r[i] ) b[i][1] = va[i], f[i][1] = va[i] * va[i] % mod;
        else {
            f[i][1] = (va[i] * va[i] % mod * ( 1 + b[i+1][1] ) % mod + f[i+1][1] * ( 1 + va[i] ) % mod ) % mod;
            b[i][1] = ( b[i+1][1] * ( 1 + va[i] ) + va[i] ) % mod;
        }
    }
    for( int i = k + 1; i < n; i++ )
        ans = ( ans + work(i-k,i) - work(i-k+1,i) + mod ) % mod;
    ans = ( ans + work(n-k,n) ) % mod;
    cout << ans;
}