题目传送门
题目大意： 求 ∑ l = 1 n ∑ r = l n f ( l , r ) \sum_{l=1}^n \sum_{r=l}^n f(l,r) ∑l=1n∑r=lnf(l,r)。其中 f ( l , r ) f(l,r) f(l,r) 表示将所有颜色为 l l l ~ r r r 的球进行排列的方案数。
做法真是太神了%%%
显然有： f ( l , r ) = ( ∑ k = l r a k ) ! a l ! a l + 1 ! . . . a r ! f(l,r)=\frac {(\sum_{k=l}^r a_k)!} {a_l!a_{l+1}!...a_r!} f(l,r)=al!al+1!...ar!(∑k=lrak)!，就是个多重集组合数问题。
然后这个柿子可以转化成： ( ∑ k = l + 1 r a k ) ! a l + 1 ! a l + 2 ! . . . a r ! × ( ( ∑ k = l r a k ) ! a l ) \frac {(\sum_{k=l+1}^r a_k)!} {a_{l+1}!a_{l+2}!...a_r!} \times {(\sum_{k=l}^r a_k)!\choose a_l} al+1!al+2!...ar!(∑k=l+1rak)!×(al(∑k=lrak)!)
证明很简单，将组合数拆开然后和左边的柿子合并一下就变成上面的柿子了。
记 S ( l , r ) = ∑ i = l r a i S(l,r)=\sum_{i=l}^r a_i S(l,r)=∑i=lrai，然后不断拆上面的柿子，就变成了： ( S ( r , r ) ! a r ) ( S ( r − 1 , r ) ! a r − 1 ) . . . ( S ( l , r ) ! a l ) {S(r,r)!\choose a_r}{S(r-1,r)!\choose a_{r-1}}...{S(l,r)!\choose a_l} (arS(r,r)!)(ar−1S(r−1,r)!)...(alS(l,r)!)
变成这种形式之后，我们就可以发现一个优秀的性质： f ( l − 1 , r ) = f ( l , r ) × ( S ( l − 1 , r ) a l − 1 ) f(l-1,r)=f(l,r) \times {S(l-1,r) \choose a_{l-1}} f(l−1,r)=f(l,r)×(al−1S(l−1,r))
有了这个柿子之后，在 r r r 固定的时候，从大到小枚举 l l l 就可以 O ( n ) O(n) O(n) 算出所有 f ( l , r ) ( l ∈ [ 1 , r ] ) f(l,r)~(l\in[1,r]) f(l,r) (l∈[1,r])，然后那个组合数我们可以用卢卡斯定理搞一搞，那么就有了一个 O ( n 2 l o g p ( S ( 1 , n ) ) ) O(n^2log_{p}(S(1,n))) O(n2logp(S(1,n))) 的做法，里面的 l o g p ( S ( 1 , n ) ) log_p(S(1,n)) logp(S(1,n)) 是卢卡斯的时间复杂度。
根据卢卡斯定理，一个组合数 ( x y ) ( m o d p ) {x\choose y} \pmod p (yx)(modp)，假如我们用 x 1 x 2 . . . x k ‾ \overline{x_1x_2...x_k} x1x2...xk 来表示 x x x 的 p p p 进制数，用 y 1 y 2 . . . y k ‾ \overline{y_1y_2...y_k} y1y2...yk 来表示 y y y 的 p p p 进制数，那么这个组合数可以表示成（证明参考卢卡斯定理）： ( x y ) = ( x 1 y 1 ) ( x 2 y 2 ) . . . ( x k y k ) {x\choose y}={x_1\choose y_1}{x_2\choose y_2}...{x_k\choose y_k} (yx)=(y1x1)(y2x2)...(ykxk)
那么对于一个组合数 ( n + m m ) {n+m\choose m} (mn+m)，我们设 n 1 n 2 . . . n k ‾ \overline{n_1n_2...n_k} n1n2...nk 为 n n n 的 p p p 进制数， m 1 m 2 . . . m k ‾ \overline{m_1m_2...m_k} m1m2...mk 为 m m m 的 p p p 进制数，那么这个组合数可以表示为： ( n + m m ) = ( n 1 + m 1 m 1 ) ( n 2 + m 2 m 2 ) . . . ( n k + m k m k ) {n+m\choose m}={n_1+m_1\choose m_1}{n_2+m_2\choose m_2}...{n_k+m_k\choose m_k} (mn+m)=(m1n1+m1)(m2n2+m2)...(mknk+mk)
我们知道，对于组合数 ( x y ) {x\choose y} (yx)，当 y > x y>x y>x 时，这个组合数的值为 0 0 0。
那么看上面这个柿子，假如有一位 n i + m i n_i+m_i ni+mi 大于等于 p p p，那么这一位是要往前进 1 1 1 的，假如进位了，我们考虑所有位里面发生进位的最低位，那么这一位的组合数就是 ( n i + m i − p m i ) {n_i+m_i-p \choose m_i} (mini+mi−p)，发现此时一定有 m i > n i + m i − p m_i>n_i+m_i-p mi>ni+mi−p，因为 n i − p < 0 n_i-p<0 ni−p<0。
假如这一串组合数中有一个为 0 0 0，那么整一串相乘的值就是 0 0 0 了。
那么可以得到一个结论：假如 n , m n,m n,m 的 p p p 进制数相加发生了进位，那么 ( n + m m ) {n+m\choose m} (mn+m) 一定为 0 0 0。
那么我们看回上面的那个柿子： f ( l − 1 , r ) = f ( l , r ) × ( S ( l − 1 , r ) a l − 1 ) f(l-1,r)=f(l,r) \times {S(l-1,r) \choose a_{l-1}} f(l−1,r)=f(l,r)×(al−1S(l−1,r))
假如 S ( l − 1 , r ) S(l-1,r) S(l−1,r) 在 p p p 进制下发生了进位，那么 f ( l − 1 , r ) f(l-1,r) f(l−1,r) 的值就是 0 0 0，进一步可以得到， f ( i , r ) ( i ∈ [ 1 , l − 1 ] ) f(i,r)~(i\in[1,l-1]) f(i,r) (i∈[1,l−1]) 的值都会为 0 0 0。
那么此时我们已经可以将暴力优化得很优秀了：在统计 S ( l , r ) S(l,r) S(l,r) 的时候，注意有没有发生进位，如果有，就停下来， l l l 不用继续向下枚举了。
时间复杂度依然玄学，TLE常伴吾身。
我们发现，这个序列里面的 0 0 0 是没什么用的，假如 0 0 0 在 l , r l,r l,r 区间内，他不会产生任何贡献，即不会对这段区间的答案产生影响。
那么不妨考虑将这些 0 0 0 都缩起来，然后对于此时一段区间 [ l , r ] [l,r] [l,r]，它的贡献是 f ( l , r ) × ( d [ l ] + 1 ) × ( d [ r + 1 ] + 1 ) f(l,r)\times (d[l]+1) \times (d[r+1]+1) f(l,r)×(d[l]+1)×(d[r+1]+1)。其中 d [ i ] d[i] d[i] 表示当前序列中的 i − 1 i-1 i−1 和 i i i 在原序列里两个位置之间有多少个 0 0 0。
举个栗子：比如说原序列是 1 , 0 , 0 , 2 , 3 1,0,0,2,3 1,0,0,2,3，那么把 0 0 0 缩起来之后，得到的新序列就是 1 , 2 , 3 1,2,3 1,2,3，此时 d d d 数组为： { 0 , 2 , 0 , 0 } \{0,2,0,0\} {0,2,0,0}。
上面那个柿子的正确性很显然，因为 0 0 0 不产生贡献，所以在原序列中，把两边的 0 0 0 包含进这个区间里面是不会影响答案的，答案依然是 f ( l , r ) f(l,r) f(l,r)，所以需要考虑左端点在左边的 0 0 0 里面和右端点在右边的 0 0 0 里面的方案。
再举个栗子：比如说原序列是 0 , 1 , 0 0,1,0 0,1,0，那么新序列就是 1 1 1， d d d 数组为 { 1 , 1 } \{1,1\} {1,1}，那么新序列中区间 [ 1 , 1 ] [1,1] [1,1] 产生的贡献就是 f ( 1 , 1 ) × ( d [ 1 ] + 1 ) × ( d [ 2 ] + 1 ) = 4 f(1,1) \times (d[1]+1) \times (d[2]+1)=4 f(1,1)×(d[1]+1)×(d[2]+1)=4，因为这相当于同时考虑了原序列中区间 [ 2 , 2 ] , [ 1 , 2 ] , [ 2 , 3 ] , [ 1 , 3 ] [2,2]~,~[1,2]~,~[2,3]~,~[1,3] [2,2] , [1,2] , [2,3] , [1,3] 的贡献。
那么我们此时将所有 0 0 0 缩了起来，有什么用呢？接下来又是一个优秀的结论：当 r r r 固定时， l l l 至多只需要枚举 ( p − 1 ) × l o g p ( a r ) (p-1)\times log_p(a_r) (p−1)×logp(ar) 个。因为在这之后， S ( l , r ) S(l,r) S(l,r) 一定会发生进位。
证明很简单：因为此时区间 [ l , r ] [l,r] [l,r] 内不存在 0 0 0，那么每一个数在 p p p 进制下至少会让某一位 + 1 +1 +1，我们一共有 l o g p ( a r ) log_p(a_r) logp(ar) 位，每一位至多为 p − 1 p-1 p−1，所以至多只能承受 ( p − 1 ) × l o g p ( a r ) (p-1)\times log_p(a_r) (p−1)×logp(ar) 次 + 1 +1 +1。再加，肯定就发生进位了。
所以在将 0 0 0 缩起来后，我们就可以大胆放心地枚举了，那么此时的时间复杂度为 O ( n ( p − 1 ) l o g p 2 ( a m a x ) ) O(n(p-1)log_p^2(a_{max})) O(n(p−1)logp2(amax))，其中多出来的那个 l o g p ( a r ) log_p(a_r) logp(ar) 是用卢卡斯定理计算组合数的时间复杂度。
但是，这样还过不了……
我们发现，上面那个结论中， l l l 至多枚举 ( p − 1 ) × l o g p ( a r ) (p-1)\times log_p(a_r) (p−1)×logp(ar) 个，这是极限情况，在这种比较极限的情况中， a l a_l al 不会有很多大于 0 0 0 的位，那么不妨将这些大于 0 0 0 的位记下来，然后每次只枚举这些位，那么时间复杂度就是 O ( n ( p − 1 ) l o g p ( a m a x ) ) O(n(p-1)log_p(a_{max})) O(n(p−1)logp(amax)) 了，然后再预处理一下组合数什么的，就可以跑的飞快。
还有一个细节，将 0 0 0 缩起来之后，我们不能忘记统计这些 0 0 0 的贡献，对于一段长为 n n n 的 0 0 0，他们产生的贡献为 n ( n + 1 ) 2 \frac {n(n+1)} 2 2n(n+1)。
代码如下：
#include <cstdio> #include <cstring> #define ll long long #define maxn 500010 int n,m=0,p;//d[i]表示[i-1,i]中间有多少个0 ll d[maxn]; int lian[maxn][61],f[maxn][61],tot[maxn]; //lian[i][j]表示第i个数拆分后第j个大于0的位是那一位，f[i][j]则表示这一位的值是多少 void work(int i,ll x) { for(int j=0;j<=60;j++) { if(x%p)lian[i][++tot[i]]=j,f[i][tot[i]]=x%p;//记录下这个数的拆分 x/=(ll)p;if(x==0)break; } } int sum[60]; ll ans=0,s; int fac[10]; int C(int x,int y){return fac[x]/fac[y]/fac[x-y];} //由于组合数很小，所以大力计算 bool add(int x,int y) { ll tt=1;//tt用来求此时的C(S(l,r),a[l])，也就是上面f的转移方程中最右边的那个东西 for(int i=1;i<=tot[x];i++)//枚举不为0的位 { sum[lian[x][i]]+=f[x][i]; if(sum[lian[x][i]]>=p)return true;//假如发生了进位 tt=tt*(ll)C(sum[lian[x][i]],f[x][i])%p; //根据卢卡斯定理，将每一位的组合数相乘得到总的组合数 } s=s*tt%p; return false; } signed main() { scanf("%d %d",&n,&p); for(int i=1;i<=n;i++) { ll x; scanf("%lld",&x); if(x==0)d[m+1]++;//记录0 else work(m,x);//否则记录下这个数 } fac[0]=1;for(int i=1;i<=7;i++)fac[i]=fac[i-1]*i; for(int r=1;r<=m;r++) { for(int i=0;i<=60;i++) sum[i]=0;//sum用来记录此时的S(l,r)的p进制数 s=1;//s用来求当前的f(l,r) for(int l=r;l>=1;l--)//枚举l if(add(l,r))break;//假如此时发生了进位，则停止 else ans+=s*(ll)(d[r+1]+1)*(ll)(d[l]+1);//否则记录下这个区间的贡献 } for(int i=1;i<=m+1;i++) ans+=(ll)d[i]*(d[i]+1)/2ll;//最后求出0段的贡献 printf("%lld",ans); }