自动搬运

查看原文

来自洛谷，原作者为

	Rainy_chen 仿生 Rainy 会上电子班吗？

搬运于2025-08-24 22:12:22，当前版本为作者最后更新于2019-10-22 07:11:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题面

给出$n$种颜色的球，每种颜色的球没有区别，定义$f(l,r)$为颜色为$l$到$r$的所有球的不同排列数，求$\sum_{l=1}^n\sum_{r=1}^n(f(l,r)\mod p)$。

$n\le5\times10^5,0\le a_i\le10^{18},p\in\{2,3,5,7\}$

吐槽

考场上想出了题解的第一步，果然我已经从「完全没有计数基础」进化到了「有一定组合数学基础」了吗233。

然后感谢XR团队提供的优质题目/亲亲。

题解

我们考虑$f(l,r)$该怎么计算，实际上应该是一个$\binom{\sum_{i=l}^ra_i}{a_l}\times f(l+1,r)$，理解方式大概就是在长度为$\sum_{i=l^r}a_i$的序列中选出$a_i$个位置设置成颜色$l$，然后剩下的位置的方案数恰好就是$f(l+1,r)$。从同样的角度理解你还可以发现$f(l,r)=\binom{\sum_{i=l}^ra_i}{a_r}\times f(l,r-1)$。
当然，对于$f(l,l)$，其值为1。

我们令$S(l,r)$表示$\sum_{i=l}^ra_i$，之后我们展开$f(l,r)$，应该可以得到

$$f(l,r) = \prod_{i=l}^r\binom{S(i,r)}{a_i}= \prod_{i=l}^r\binom{S(i,r)}{S(i+1,r)} $$

以上是题解的第一步

之后我们考虑Lucas定理，Lucas定理一般表示为$\binom nm\mod p=\binom{n/p}{m/p}\binom{n\mod p}{m\mod p}\mod p$，其中，$a/b$表示$\left\lfloor\frac ab\right\rfloor$。

实际上如果我们将$n,m$看做两个$p$进制数$\overline{n_a..n_2n_1n_0},\overline{m_b..m_2m_1m_0}$的话，$\binom nm\mod p$就是$\prod_{i=0}^{max(a,b)}\binom{n_i}{m_i}\mod p$。

有一个并不显然的结论，若$\binom {n+m}m\mod p$为$0$，那么这代表着在$p$进制下计算$n+m$时有一位发生了进位。

一个比较感性的理解方式是若$\binom{n+m}m\mod p=0$，那么$n+m$的$p$进制上必然有一位是小于$m$的$p$进制上的这一位的，而发生这个情况的唯一可能性是这一位加了一个数产生了进位。

或许你还会考虑到这一位可能被其他位置的进位所影响，所以我们这里找的是产生进位的最低位，如果存在进位则必然存在这一位，并且无论如何这一位都不会被其他位影响。

然后我们发现$f(l,r)\mod p=0$的条件就是$\sum_{i=l}^ra_i$在$p$进制下运算时出现了进位。
更优秀的性质是如果$f(l,r)\mod p=0$，那么$f(l-1,r)=f(l,r+1)=0$,因为这两者都可以从$f(l,r)$通过乘法计算而来。这意味着是否进位是满足单调性的。

于是我们得出了解法1，对每个点$r$求出最小的$l$使得$f(l,r)$不产生进位，之后暴力计算$\sum_{i=l}^rf(i,r)$。

第一部分的测试点中期望的不产生进位的区间个数是$\theta(n)$个左右，具体证明可以参考XR题解，这里不再赘述。

对于第二部分的测试点，$a_i$不再随机，这意味着可能会被人为构造出大量的$0$来使解法1的区间个数以及区间长度大量增长，这时复杂度完全取决于出题人是否良心。

于是你可以考虑消除$0$对于答案的影响，容易发现若$a_l=0$则$f(l,r)=\binom{S(l,r)}{0}f(l+1,r)=f(l+1,r)$，于是将所有0缩起来，只记录0出现的数量，之后在新的不包含0的序列上再沿用解法1即可。

至于说在不包含0的序列上用解法1的时间复杂度，容易发现区间长度不会超过$(p-1)\lceil log_pa_i\rceil$，主要每一个数至少在一位上至少为1，然后最多可以有$(p-1)\lceil log_pa_i\rceil$个1，只要再出现一个数就会产生进位。

于是最坏复杂度是$O(nplog_p^2a_i)$。

正解与第二部分的算法是十分相似的，在第二部分中计算组合数时使用了lucas定理，而lucas定理的本质是将数转化为$p$进制数后逐位计算。

所以我们可以在进行解法2之前先将每一个$a_i$拆分成$p$进制数。 然后进行解法2的扫描时，把$p$进制的每一位的值储存下来，对于扫到的数$a_i$，将其拆分后的$p$进制数在其几个非$0$位上将储存的值更新掉。

$p$很小，所以完全可以$p^2$预处理出所有$\binom ij\mod p(i,j<p)$的结果。 那么每一次更新时只需要$O(1)$的复杂度，而很显然最多只会更新$(p-1)\lceil log_pa_i\rceil$次（参考解法2复杂度分析），那么此时就有了一个复杂度为$O(nplog_pa_i)$的优秀算法了。

代码细节好难考虑。。。

#include<bits/stdc++.h>

using namespace std;

typedef long long int_t;

char getch(){
    static char buf[100000],*s,*t;
    return (s == t) && (t = (s = buf) + fread(buf,1,100000,stdin)), s == t ? EOF : *s++;
}

#ifdef local
#define getch getchar
#endif

int_t read(){
    int_t x = 0,w = 1;char ch = 0;
    for(;!isdigit(ch);ch = getch()) if(ch == '-') w = -1;
    for(;isdigit(ch);ch = getch()) x = x * 10 + ch - '0';
    return x * w;
}

struct shu{
    int_t w;
    vector<pair<int_t,int_t>> cf;
    void chaifen(int_t w,int_t p) { 
        this -> w = w;
        int_t tmp = 0;
        while(w) {
            if(w % p) cf.push_back(make_pair(tmp,w % p));
            ++tmp; w/=p;
        }
    }
}shus[500010];

int_t ans = 0;
int_t C[10][10],pre[500010];
// 预处理出的组合数以及每一个数开始的最靠左的连续的0位置

void init(int_t n,int_t p){
    for(int_t i=0;i<p;i++)
        for(int_t j=C[i][0]=1;j<=i;j++)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % p;
    pre[1] = 1;
    for(int_t i=2;i<=n;i++) if(!shus[i].w) pre[i] = shus[i-1].w ? i : pre[i-1];
}

int_t fpow(int_t a,int_t b,int_t p){
    int_t res = 1;
    for(;b;b>>=1,a=a*a%p) if(b & 1) res = res * a % p;
    return res;
}

int_t inv(int_t x,int_t p){
    return fpow(x,p-2,p);
}

int_t a[70]; // 按位拆分后的S(i,r)

void work(int_t r,int_t p){
    int_t tmp = 1,ttmp = 1;
    memset(a,0,sizeof a);
    for(auto x : shus[r].cf) a[x.first] = x.second;
    while(r){
        ans += tmp;
        // 这里tmp是f(r-1,R), R为传入的参数r的复制
        --r;
        if(r < 1) break;
        if(shus[r].w == 0){
            ans += (r - pre[r] + 1) * tmp;
            r = pre[r] - 1;
        }
        ttmp = 1;
        for(auto x : shus[r].cf){
            int_t pos = x.first,w = x.second;
            if(a[pos] + w >= p) {ttmp = 0; break;}
            ttmp = ttmp * C[a[pos] + w][a[pos]];
            a[pos] += w; 
        }
        // 这里ttmp是计算的组合数
        if(!ttmp) break;
        tmp = tmp * ttmp % p;
    }
}

int main(){
    int_t n = read(),p = read();
    for(int_t i=1;i<=n;i++) 
        shus[i].chaifen(read(),p);
    init(n,p);
    for(int_t i=1;i<=n;i++) work(i,p);
    cout<<ans;
}