【2020牛客多校第八场 D】Disgusting Relationship 题解

题目大意

  一个置换可以看成是有 $a_1$ 个长度为 $1$ 的环 + $a_2$ 个长度为 $2$ 的环 + …… + $a_n$ 个长度为 $n$ 的环，满足 $\sum_{i=1}^n i\cdot a_i=n$ 。
  记 $f(a_1,a_2,\cdots,a_n)$ 表示各种环的数量分别为 $a_1,\cdots,a_n$、长度为 $n$ 的置换的数量，现给定 $n,p$（$p$ 是质数），问有多少种不同的数列 $a_1,\cdots,a_n$，满足 $p \not|\ f(a_1,a_2,\cdots,a_n)$ 。

  $n \leq 10^{18},\ \ 2 \leq p \leq 10^5$
  多测，$T \leq 10^5$，2s

题解

  明眼人一看就有

$$f(a_1,\cdots,a_n)=\frac{n!}{\prod_{i=1}^n i^{a_i} \cdot a_i!}$$

  所以 $p$ 不整除这个东西，意思是要让分母的 $p$ 因子数量 $\ge$ 分子的 $p$ 因子数量。
  乍一看这个 $n$ 这么大，整数拆分、dp 之类的啥都做不了，吓死个人。

  冷静分析.jpg
  首先，这整个分式最终必然得到一个整数（因为这是在计算方案数），这意味着分母的 $p$ 因子数量一定是 $\leq$ 分子的 $p$ 因子数量的。而我们的目标又是“分母的 $p$ 因子数量 $\ge$ 分子的 $p$ 因子数量”，因此可得：1、我们要让分母、分子的 $p$ 因子数量相等；2、这等价于让分母的 $p$ 因子数量最大化。

  有了这个目标，就能隐约感觉到，$a$ 数列不会长得太奇怪，肯定有限制的。
  接下来就来排除掉一些情况。

1. 会不会有环长 $r>p$ 却又不是 $p$ 的倍数呢？
     注意到这时候 $r^{a_r}$ 是没有贡献的，这太浪费了，我们把这 $a_r$ 个长度为 $r$ 的环，每个抽 $p$ 出来，组成 $a_r$ 个长度为 $p$ 的环，发现贡献至少多了 $a_r$。说明这种情况下分母的 $p$ 因子数量没有最大化。
2. 会不会有环长 $r=kp$（$k>1$）呢？
     同理啊，全部换成环长为 $p$ 会使贡献增大：单个 $r$ 的贡献从 $1+(k的p因子数量)$ 变成 $k$，正常情况下后者都会大于前者；而 $a_r!$ 部分的贡献从 $a_r!$ 变成 $\frac{(a_p+a_r)!}{a_p!}$，不会更劣。
     唯一使得单个 $r$ 贡献保持不变的是 $k=p=2$，但这会在 $a_r!$ 部分增大贡献。
     所以也不合法。

  所以这就说明 $a_i$ 非零的只有 $i \in [1,p]$ 了。

  我们可以先想像一种初始情况：$a_1=n$，这显然是一个合法解。然后看看怎么能把 $a_1$ 里的东西拿到 $a_2,\cdots,a_p$ 里去，而保持 $p$ 因子数量不变。

  先考虑 $n \bmod p=0$。
  当然可以想到 $a_1$ 举家迁移到 $a_p$，贡献从 $\sum_{j=1}^\infty \lfloor \frac{n}{p^j} \rfloor$ 变成 $\frac np + \sum_{j=2}^\infty \lfloor \frac{n}{p^j} \rfloor$，没有变化。如果只是抽 $a_1$ 的一部分放到 $a_p$ 里去呢？由于在 $p$ 的幂的位置，$a_1!$ 的 $p$ 因子数量都会有一次大的提升，所以构成 $p$ 的幂的连续段不能拆开考虑，否则 $p$ 因子数量一定会减少。比如 $a_1=14, p=2$，那么相当于把 $a_1$ 分成长度为 $8,4,2$ 的三个段，每个段要么留在 $a_1$ 要么搬到 $a_p$
  更一般地说，设 $n$ 的 $p$ 进制表示为 $b_1b_2\cdots b_m$，那么每个二进制位下的每个单位“1”可以选择留在 $a_1$ 或搬到 $a_p$，因此对答案的贡献为 $\prod_{i=1}^{m-1}(b_i+1)$。（为啥是 $m-1$？最低位一定是 $0$，如果不是 $0$ 的话是下面的情况）

  再考虑 $n \bmod p>0$。
  显然这个多出来的部分放哪都无所谓，都不会产生任何 $p$ 因子，因此这里对答案的贡献是 $n \mod p$ 的可重整数拆分。

  综上，答案为

$$ans=part(n \bmod p) \cdot \prod_{i=1}^{m-1}(b_i+1)$$

  其中 $b_1b_2\cdots b_m$ 是 $n$ 的 $p$ 进制表示，$part$ 表示可重整数拆分方案数。后者五边形数 $O(n \sqrt n)$ 或者 $O(n \log n)$ 预处理一下就完事了。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxp=1e5+5;
const LL mo=1e9+7;

LL n;
int p;

int w[maxp],w0;
LL f[maxp];
void Pre_part(int n)
{
    for(int i=1; w[w0]<n; i++)
    {
        w[++w0]=i*(3*i-1)>>1;
        w[++w0]=i*(3*i+1)>>1;
    }
    f[0]=1;
    fo(i,1,n)
        for(int j=1; w[j]<=i; j++) (f[i]+=((((j-1)>>1)&1) ?-1 :1)*f[i-w[j]])%=mo;
}

int T;
int main()
{
    Pre_part(1e5);

    scanf("%d",&T);
    fo(ti,1,T)
    {
        scanf("%lld %d",&n,&p);

        LL ans=f[n%p];
        for(n/=p; n; n/=p) (ans*=n%p+1)%=mo;

        printf("Case #%d: %lld\n",ti,(ans+mo)%mo);
    }
}