AGC052C Nondivisible Prefix Sums(计数dp)题解

发布于 2021-03-20  1448 次阅读


本文同步发表在我的洛谷博客,Latex炸了可以去那边。

题目大意:

求符合以下条件的排列 $a_1 ... a_n$ (称之为“好”排列):

  1. 长度为 $n$ 且所有元素的取值范围为 $[1,P-1]$
  2. 满足这个排列的所有前缀和都不能被 $P$ 整除。

答案对998244353取模。

$1\le n \le 5000 ,2 \le P \le 10^8 $ 且 $P$ 为质数。

解题思路:

考虑一个排列是“好”排列的条件:

首先我们可以得出一个前提条件: $ P \nmid \sum_{i=1}^n a_i$ 。显然,如果一个数列本身的和就是 $P$ 的倍数,那么最后一个位置一定无法满足条件。

然后我们来寻找其他条件。

我们先来考虑何时一个排列不是“好”排列。

手动构造一个排列,可以看到,当你发现当前这个数填上去会不符合条件时你会换一个数。

那么一个显然(?)的想法是一个数重复出现了太多次,导致在这个数之后已经 没有其他的数可以用于替换这个数了 ,那么只能宣布:构造失败。

诶那我们假设这个数是 $1$ 。对于那些众数(出现最多的数)为 $x$ ,且 $x \ne 1$ 的情况,我们可以把整个数列乘上在模 $P$ 意义下的 $x^{-1}$ ,即 $x$ 的逆元即可。这样如果原来的一个前缀和 $sum$ 在模 $P$ 意义下 $=0$ ,那么 $x^{-1} \ne 0$ ,但是 $sum \times x^{-1} = 0$ ,不改变其不合法的本质。同样, $sum \ne 0$ 时,由于 $x^{-1} \ne 0$ ,有 $sum \times x^{-1} \ne 0$ 。综上,整个序列乘上 $x^{-1}$ 时,合法的仍然合法,不合法的仍然不合法,所以假设众数是 $1$ 是可行的。

让我们进入这道题真正精妙的地方吧。我们考虑如何避免上面无法拿别的数替代 $1$ 的尴尬情况:我们尽量在前面消耗 $1$ 。如何消耗呢?自然是见缝插针。

  1. 首先数列的前 $P-1$ 项可以全部插入 $1$ 。
  2. 然后再在后面跟上一个不为 $1$ 的数以使前缀和不为 $P$ 。
  3. 假设这个数是 $x$ ,那么此时整个数列的和为 $P-1+x$ ,我们需要在它到达 $2\times P$ 前尽量插入 $1$ ,那么我们可以插入 $2 \times P - 1 - (P-1+x)$ 也就是 $P-x$ 个 $1$ 。
  4. 重复上面的步骤 2 和步骤 3 ,在下面再插入后面的数。

我们假设一共有 $k$ 个非 $1$ 的数,分别为 $b_1...b_k$ ,$cnt1$ 个 $1$。

那么 一共可以消耗 $P-1+\sum (P-b_i)=(k+1)P-1-\sum b_i$ 个 $1$

所以容易发现当 $cnt1 \le (k+1)P-1-\sum b_i$ 的时候是有解,也就是充分性。

那么必要性呢?

当 $cnt1 > (k+1)P-1-\sum b_i$ ,也即 $cnt1 \ge (k+1)P-1-\sum b_i+1=(k+1)P-\sum b_i$ 时,所有数的总和 $Sum=cnt1+\sum b_i \ge (k+1)P$ (把上面 $cnt1$ 的式子代入即可)。

而前面说到 $P\nmid Sum$ ,所以有 $Sum \ge (k+1)P+1$ 。而我们发现 对于每一段要到达 $P$ 的倍数的时候我们都需要一个非 $1$ 的数来使前缀和跳过 $P$ 这个位置 。所以对于总数 $ \ge $ $(k+1)P$ 的排列,我们至少需要 $(k+1)$ 个非 $1$ 的数。而事实上我们只有 $k$ 个非 $1$ 的数,所以此时不可能有满足要求的排列,必要性得证。

诶但是我们发现当数列的众数不止有 $1$ 一个时我们可能会计重(自己可以找几个反例)。那么我们考虑正难则反, 用总数 $(P-1)^n$ 减去不符合要求的排列 。那么此时有 $cnt1 > (k+1)P-\sum b_i$ ,则此时 $1$ 为严格众数,不会出现计重的情况。

接下来就是 $dp$ 了。我们设 $dp[cnt][sum]$ 表示用了 $cnt$ 个非 $1$ 的数,$ \sum_{i=1}^k (P-b_i)=sum$ 的数列的数量,那么可以枚举下一个填入什么,是 $O(n^2)$ 的 $dp$ 。

不过在开头我们需要处理总和为 $P$ 的倍数的情况。当 $n$ 为奇数时这个数字为 $ \frac {(P−1)^n−(P−1)} {P} $ , $n$ 为偶数时这个数字为 $\frac {(P-1)^n+(P-1)} {P}$ 。

为什么呢?这里给出 @lengendgod 的证明:我们假设 $g_i$ 为长度为 $i$ 的总和非 $P$ 的倍数的序列个数。则有 $g_i=g_{i-1} \times (P-2) + ((P-1)^{i-1}-g_{i-1}) \times (P-1)$ 。解释:长度为 $i$ 的排列可以由长度为 $i-1$ 的合法排列末尾接上一个 接上以后使它不为 $P$ 的倍数的数(有 $P-2$ 种,因为有且只有一个数会让总和变成 $P$ 的倍数) 或者 由不合法的数目( 不合法数目=总数( $(P-1)^{i-1}$ )$-$ 合法数目($g_{i-1}$) )加上任意一个数(都不会使总和变成 $P$ 的倍数)。

可以化简出是 $g_i$ 类似于 $(P-1)-(P-1)^2+(P-1)^3...$ 的正负交错的式子 ,正负号由 $n$ 的奇偶性决定,把它化简出来就是上面的式子。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005;
const int Mod=998244353;

int n,m,k;
int sum,inv,ans,f[N][N],C[N][N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline int Power(int base,int power){
    int result=1;
    while (power>0){
        if (power&1)
            result=result*base%Mod;
        power>>=1;
        base=(base*base)%Mod;
    }
    return result;
}

signed main(){
    //freopen("AGC052C.in","r",stdin);
    //freopen("AGC052C.out","w",stdout);
    n=read(),m=read();
    k=min(n,m-2);
    f[0][0]=C[0][0]=1;
    for (int i=1;i<=n;++i){
        sum=0,C[i][0]=1;
        for (int j=1;j<=n;++j){
            if (j<=i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
            sum=(sum+f[i-1][j-1])%Mod;
            if (j>k) sum=(sum-f[i-1][j-k-1]+Mod)%Mod;
            f[i][j]=sum;
        }
    }

    ans=Power(m-1,n),inv=Power(m,Mod-2);        //先统计总和为P的倍数的情况
    if (n%2) ans=(ans-(ans-m+1+Mod)%Mod*inv%Mod+Mod)%Mod;
    else ans=(ans-(ans+m-1)%Mod*inv%Mod+Mod)%Mod;

    for (int i=0;i<=n;++i)
        for (int j=0;(j<=n) && (n-i>=j+m);++j){
            if ((n-i)%m==j%m) continue;     //统计不合法的情况数量
            ans=(ans-f[i][j]*(m-1)%Mod*C[n][i]%Mod+Mod)%Mod;
        }
    printf("%lld\n",ans);
    return 0;
}

我们无法选择过去,但我们可以改变未来。