题解：CF1957E Carousel of Combinations

· · 题解

CF1957E 题解

题目大意

要求直接计算

\sum\limits_{i=1}^n \sum\limits_{j=1}^i \left( C(i,j) \bmod j \right)

其中 C(i,j) 表示从 i 个数当中选 j 个的不同圆排列数。
拥有 T 组测试样例 T \leq 10^5，n \leq 10^6。

前置知识提示

  1. 威尔逊定理
  2. 卢卡斯定理

分析C函数

因为这里的 C(i,j) 是指圆排列数，先选择 j 个数字，方案为 \binom{i}{j}。我们尝试将选择的数中的第一个固定，剩下 j-1 个数字的排列方式数为 (j-1)!。

所以圆排列数的计算公式为：

C(i,j) = \binom{i}{j} \times (j-1)!

入手

  1. 尝试快速预处理出所有的 a[i] =\sum\limits_{j=1}^i \left( C(i,j) \bmod j \right) 然后对于每组输入数据直接输出前缀和 \sum\limits_{i=1}^n a[i] 即可
  2. 展开组合数得
\begin{aligned} C(i,j) &= \binom{i}{j} \times (j-1)! \\ &= \frac{i!}{j!(i-j)!} \times (j-1)! \\ &= \frac{i!}{j(i-j)!} \end{aligned}

因为 i>j 所以可以从 i! 找到至少一个 j 与分母的 j 抵消

\frac{i!}{(i-j)!} = i \times (i-1) \times \cdots \times (i-j+1)

当 j 是合数时可以证明这其中的质因数可以组成另一个 j。
然后因为结果要模 j 所以我们会得到 0。

重要 corner

当 j=4 时，我们上述的可以得到的两个 j，也就是一个 j 与两个 2 其中的一个 2 与那个 j 重合，导致结果无法被 4 整除，因此 4 也能造成有效贡献。

至此，我们后面只要考虑 j 为质数的情况了，4 的情况直接加上去。

公式推导

C(i,j) \equiv \binom{i}{j} \times (j-1)! \pmod{j}

根据卢卡斯定理

C(i,j) \equiv \binom{i \bmod j}{j \bmod j} \times \frac{\lfloor \frac{i}{j} \rfloor}{\lfloor \frac{j}{j} \rfloor} \times (j-1)! \pmod{j} C(i,j) \equiv \lfloor \frac{i}{j} \rfloor \times (j-1)! \pmod{j}

根据威尔逊定理

C(i,j) \equiv -\lfloor \frac{i}{j} \rfloor \pmod{j}

把题目要我们求的结果只考虑质数并用 C(i,j) 替换

\sum\limits_{i=1}^n \sum\limits_{\substack{j为质数 \\ j \leq i}} \left( C(i,j) \bmod j \right) = \sum\limits_{i=1}^n \sum\limits_{\substack{j为质数 \\ j \leq i}} \left( -\left\lfloor \frac{i}{j} \right\rfloor \bmod j \right)

因为括号里有一个 \bmod j 所以考虑交换两个求和顺序

\sum\limits_{i=1}^n \sum\limits_{\substack{j为质数 \\ j \leq i}} \left( -\left\lfloor \frac{i}{j} \right\rfloor \bmod j \right) = \sum\limits_{j为质数}\sum\limits_{i=j}^n \left( -\left\lfloor \frac{i}{j} \right\rfloor \bmod j \right)

所以我们枚举每一个质数 j，并快速求出其对每一个 a[i] 的贡献。

递推求解

当我们枚举到 j 的时候，因为 \left\lfloor \frac{i}{j} \right\rfloor 是每连续 j 个数字都是一样的，所以我们从 i 开始，对每 j 个合法的数字加上 -\left\lfloor \frac{i}{j} \right\rfloor 的贡献，区间增加，静态查询，直接差分就行了。

j=4$ 时，$(j-1) \equiv 3! \equiv 2\pmod{4}$ ，展开计算 $C(x,4)=\frac{i(i-1)(i-2)(i-3)}{4} \bmod 4$ 发现如果 $2\mid \lfloor \frac{i}{8} \rfloor $ 结果就是 $2$ 否则是 $0

复杂度

\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} +\ldots+ \frac{n}{4} \approx O(nloglogn)

代码

基本与公式相同，码量很少

const int N=1e6;
ll a[MXN];//差分数组，静态做区间修改

void add(int l,int r,int add){//区间修改
    r=Min(r,N);
    (a[l]+=add)%=M;
    (a[r+1]-=add)%=M;
}

void solve(int p){
    for(int i=p;i<=N;i+=p){
        add(i,i+p-1,(i/p*(p-1))%p);
        //-1 ≡ p-1 (mod p)
    }
}
void solve4(){
    for(int i=4;i<=N;i+=4){
        add(i,i+4-1,(i/4*2)%4);
    }
}

signed main() {
    std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);

    euler();
    for(int i=1;i<=tot;i++)solve(prime[i]);
    solve4();

    for(int i=1;i<=N;i++)(a[i]+=a[i-1])%=M;//差分->原数组
    for(int i=1;i<=N;i++)(a[i]+=a[i-1])%=M;//原数组->前缀和

    int T;
    std::cin>>T;
    while(T--){
        int x;
        std::cin>>x;
        std::cout<<a[x]<<"\n";
    }
}

致谢

非常感谢 C20220403 大佬在今天春游时为我提供了此题的部分灵感。

更改