【题解】[XR-4] 混乱度组合数学+kummer 定理+lucas 定理 luoguP5598

题意：
小 X 有 $n$ 种颜色的球，其中第 $i$ 种颜色的球共有 $a_i$
个，同色的球无法区分。定义第 $l \sim r$ 种颜色的混乱度 $f(l, r)$ 为：将第 $l \sim r$ 种颜色的所有球排成一排，总共的方案数对 $p$ 取模后的值。小 X 想请你帮忙计算下列式子的值：
$\sum_{l=1}^n \sum_{r=l}^nf(l, r)$

题解：发现每次选球的贡献可以直接使用组合数计算。但是是 $O(n^3*log_2a[i])$ 的，拿不到任何分数。

考虑枚举一个 i 把 j 向右边扩，发现原式子是组合数相乘，所以可行。这样子是 $O(n^2*log_2a[i])$ ，也拿不到任何分数。

但是发现其实乘的组合数有很多是 0，于是可以在遇到第一个 0 以后跳出。可以通过子任务 1。

在子任务 2 和 3 中，可能出题人会构造出很多 0，导致组合数乘的有很多 1，使用上面的优化时间复杂度退化。把所有 0 缩成一个 0 即可解决这个问题，通过子任务 2

实际上，由于 kummer 定理，c(n+m,n) 含有 p 的幂次数量为 n+m 在 p 进制下的进位次数。于是每一次加到区间 (l,r) 时，其实就是在检查 a[l]+…+a[r] 在 p 进制下是否有进位。最多进位 $p\times$ 位数次，所以最多扩展 $p\times$ 位数次。这样时间复杂度有保证。

发现每次调用 lucas 定理太慢。实际上，每次调用 lucas 定理就是在它的 p 进制分拆下做组合数，于是可以在每次向右边扩展时顺便维护一下和在 p 进制的每一位值，即可快速判断是否要跳出以及快速计算组合数。可以获得 100 分。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 500010
#define int long long
int n,c[15][15],nt[N],l[N],r[N],w[N*60],v[N*60],s[70],p;
int a[N],t;
signed main(){
    cin>>n>>p;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=0;i<15;i++){
        c[i][0]=1;
        for(int j=1;j<15;j++){
            if(i<j)continue;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
        }
    }
    nt[n]=n+1;
    for(int i=n-1;i;i--){
        if(a[i+1])nt[i]=i+1;
        else nt[i]=nt[i+1];
    }
    int j=0;
    for(int i=1;i<=n;i++){
        l[i]=j+1;
        r[i]=j;
        int x=a[i],c=-1;
        while(x){
            int nw=x%p;
            x/=p;
            c++;
            if(nw){
                w[++r[i]]=c;
                v[r[i]]=nw;
            }
        }
        j=r[i];
    }
    for(int i=1;i<=n;i++){
        int g=1;
        memset(s,0,sizeof(s));
        if(a[i]){
            for(int j=l[i];j<=r[i];j++)
                s[w[j]]=v[j];
        }
        t+=g;
        int j=i+1;
        while(j<=n){
            if(!a[j]){
                t+=g*(nt[j]-j);
                j=nt[j];
                continue;
            }
            for(int k=l[j];k<=r[j];k++){
                s[w[k]]+=v[k];
                if(s[w[k]]>=p){
                    g=0;
                    break;
                }
                g=(g*c[s[w[k]]][v[k]])%p;
            }
            if(!g)break;
            t+=g;
            j++;
        }
    }
    cout<<t;
}

【题解】[XR-4] 混乱度组合数学+kummer 定理+lucas 定理 luoguP5598

于2019年10月30日2019年10月30日由rilisoft发布

rilisoft

3 条评论

boshi · 2019年10月30日 4:54 下午

rilisoft · 2019年11月5日 8:05 上午

boshi · 2019年11月5日 8:56 上午

发表回复取消回复

【题解】[XR-4] 混乱度 组合数学+kummer 定理+lucas 定理 luoguP5598

于2019年10月30日2019年10月30日由rilisoft发布

rilisoft

3 条评论

boshi · 2019年10月30日 4:54 下午

rilisoft · 2019年11月5日 8:05 上午

boshi · 2019年11月5日 8:56 上午

发表回复 取消回复

【题解】[XR-4] 混乱度组合数学+kummer 定理+lucas 定理 luoguP5598

发表回复取消回复