由于存在一道题叫做白兔之舞就导致这道题看上去非常的板......
约定，\([x]\)表示\(x\)向下取整
\[\sum_{i=0}^n\dbinom{n}{i}*p^i*[\dfrac{i}{k}]\]
然后会想到可以将\([\dfrac{i}{k}]\)拆开变成：
\[\dfrac{i-i\%k}{k}\]
于是原问题变成：
\[\sum_{i=0}^n\dbinom{n}{i}*p^i*\dfrac{i-i\%k}{k}\]
看到了\(i\%k\)，然后还有组合数，然后\(k\)还是\(2\)的整数次幂，这个时候当然是单位根反演上场了...
\[\sum_{t=0}^{k-1}\sum_{i=0}^n[i\%k==t]\dbinom{n}{i}*\dfrac{i-t}{k}*p^i\]
然后就是喜闻乐见的化式子了
\[\sum_{t=0}^{k-1}\sum_{i=0}^n[(i-t)\%k==0]\dbinom{n}{i}*\dfrac{i-t}{k}p^i\]
\[\sum_{t=0}^{k-1}\sum_{i=0}^n\dfrac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{(i-t)j} *\dbinom{n}{i}*\dfrac{i-t}{k}p^i\]
\[\dfrac{1}{k^2}\sum_{t=0}^{k-1}\sum_{i=0}^n\sum_{j=0}^{k-1}\omega_{k}^{(i-t)j} *\dbinom{n}{i}*(i-t)p^i\]
\[\dfrac{1}{k^2}\sum_{t=0}^{k-1}\sum_{i=0}^n\sum_{j=0}^{k-1}\omega_{k}^{ij}*\omega_{k}^{-tj} *\dbinom{n}{i}*(i-t)p^i\]
然后肯定要交换求和顺序变成：
\[\dfrac{1}{k^2}\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=0}^{n}\omega_{k}^{ij} *\dbinom{n}{i}*(i-t)p^i\]
然后这里是可以将其拆开的...
\[\dfrac{1}{k^2}\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=0}^{n}\omega_{k}^{ij} *\dbinom{n}{i}*i*p^i-\dfrac{1}{k^2}\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=0}^{n}\omega_{k}^{ij} *\dbinom{n}{i}*tp^i\]
我们先忽略\(\dfrac{1}{k^2}\)
\[\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=0}^{n}\omega_{k}^{ij} *\dbinom{n}{i}*i*p^i-\sum_{t=0}^{k-1}t*\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=0}^{n}\omega_{k}^{ij} *\dbinom{n}{i}p^i\]
\[\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=0}^{n}(\omega_{k}^{j}p)^i *\dbinom{n}{i}*i-\sum_{t=0}^{k-1}t*\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=0}^{n}(\omega_{k}^{j}p)^i *\dbinom{n}{i}\]
第二个式子很好处理，我们直接用二项式定理即可化开变成：
\[\sum_{t=0}^{k-1}t*\sum_{j=0}^{k-1}\omega_{k}^{-tj}(\omega_{k}^{j}p+1)^n\]
然后对于某一个\(j\)，\((\omega_{k}^{j}p+1)^n\)为定值，设其为\(a_j\)
第一个式子可以将组合数拆开
\[\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=0}^{n}(\omega_{k}^{j}p)^i *\dbinom{n}{i}*i\]
\[\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=0}^{n}(\omega_{k}^{j}p)^i *\dfrac{n!}{i!*(n-i)!}*i\]
然后这个时候可以将\(i=0\)的那一项给忽略掉
\[\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=1}^{n}(\omega_{k}^{j}p)^i *\dfrac{n!}{(i-1)!(n-i)!}\]
\[\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=1}^{n}(\omega_{k}^{j}p)^i *\dfrac{n*(n-1)!}{(i-1)!((n-1)-(i-1))!}\]
\[n*\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=1}^{n}(\omega_{k}^{j}p)^{i-1+1}*\dfrac{(n-1)!}{(i-1)!((n-1)-(i-1))!}\]
\[n*\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=1}^{n}(\omega_{k}^{j}p)^{i-1}*\omega_{k}^jp*\dfrac{(n-1)!}{(i-1)!((n-1)-(i-1))!}\]
\[n*\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}*\omega_{k}^jp\sum_{i-1=0}^{n-1}(\omega_{k}^{j}p)^{i-1}*\dfrac{(n-1)!}{(i-1)!((n-1)-(i-1))!}\]
\[n*\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}*\omega_{k}^jp\sum_{i-1=0}^{n-1}(\omega_{k}^{j}p)^{i-1}* \dbinom{i-1}{n-1}\]
\[n*\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}*\omega_{k}^jp\sum_{i=0}^{n-1}(\omega_{k}^{j}p)^{i}* \dbinom{i}{n-1}\]
\[n*\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}*\omega_{k}^jp*(\omega_{k}^{j}p+1)^{n-1}\]
后面那一坨对于某一个\(j\)也是固定的，我们可以设\(b_j=\omega_{k}^jp*(\omega_{k}^jp+1)^{n-1}\)
那么就有原式即：
\[n*\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-tj}*b_j-\sum_{t=0}^{k-1}t*\sum_{j=0}^{k-1}\omega_{k}^{-tj}a_j\]
然后我们就得到了一个\(O(k^2)\)的做法了...
然后我们用一下白兔之舞的神仙操作\(tj=\dfrac{(t+j)(t+j-1)}{2}-\dfrac{j(j-1)}{2}-\dfrac{t(t-1)}{2}\)
证明也很简单，分子是：
\[(t+j)^2-t-j-j^2+j-t^2+t\]
\[2tj\]
所以原式就可以化成：
\[n*\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-(\binom{2}{t+k}-\binom{2}{t}-\binom{2}{j})}*b_j-\sum_{t=0}^{k-1}t*\sum_{j=0}^{k-1}\omega_{k}^{-(\binom{2}{t+k}-\binom{2}{t}-\binom{2}{j})}a_j\]
\[n*\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-\binom{2}{t+k}+\binom{2}{t}+\binom{2}{j}}*b_j-\sum_{t=0}^{k-1}t*\sum_{j=0}^{k-1}\omega_{k}^{-\binom{2}{t+k}+\binom{2}{t}+\binom{2}{j}}a_j\]
\[n*\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-\binom{2}{t+k}} \omega_{k}^{\binom{2}{t}}\omega_k^{\binom{2}{j}}*b_j-\sum_{t=0}^{k-1}\sum_{j=0}^{k-1}\omega_{k}^{-\binom{2}{t+k}} t*\omega_{k}^{\binom{2}{t}}\omega_k^{\binom{2}{j}}a_j\]
然后如果我们将\(t+k\)看作一个整体那么就会发现这是一个卷积的形式
然后就只需要将\(\omega_{k}^{\binom{j}{t}}\)和\(\omega_k^{\binom{2}{j}}*b_j\)以及\(t*\omega_{k}^{\binom{j}{t}}\)和\(\omega_k^{\binom{2}{j}}*a_j\)分别卷起来即可，暴力卷是需要\(\rm 6NTT\)的...
还担心会\(\rm T\)来着...然而事实上也不慢，开\(\rm O2\)最慢的点才\(1.3s\)..不过其实可以做\(\rm 3FFT\)的...因为卷起来可以将结果乘起来再加起来...同时把两个多项式的\(\rm DFT\)算出来需要\(3\)次变\(2\)次的技巧...所以速度应该会还可以
复杂度\(O(k\log k)\)
\(Code:\)
#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define LL long long
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int Gi = 332748118 ;
const int P = 998244353 ;
const int N = 4e6 + 5 ;
const int G = 3 ;
int n, p, m, limit, L, R[N] ;
LL A[N], B[N], F[N], F2[N], Dg[N], Inv ;
LL fpow( LL x, int k ) {
LL ans = 1, base = x % P ; k = k % ( P - 1 ) ;
while( k ) {
if( k & 1 ) ans = ( ans * base ) % P ;
base = ( base * base ) % P, k >>= 1 ;
}
return ans % P ;
}
void NTT( LL *a, int type ) {
for( re int i = 0; i < limit; ++ i ) if( i < R[i] ) swap( a[i], a[R[i]] ) ;
for( re int k = 1; k < limit; k <<= 1 ) {
LL dg = fpow( ( type == 1 ) ? G : Gi, ( P - 1 ) / ( k << 1 ) );
for( re int i = 0; i < limit; i += ( k << 1 ) )
for( re LL j = i, g = 1; j < i + k; ++ j, g = ( g * dg ) % P ) {
LL Nx = a[j], Ny = ( a[j + k] * g ) % P;
a[j] = ( Nx + Ny ) % P, a[j + k] = ( Nx - Ny + P ) % P ;
}
}
if( type != 1 ) rep( i, 0, limit - 1 ) a[i] = ( a[i] * Inv ) % P ;
}
void Init() {
limit = 1, L = 0 ;
while( limit < m + m ) limit <<= 1, ++ L ;
for( int i = 0; i < limit; ++ i ) R[i] = ( R[i >> 1] >> 1 ) | ( ( i & 1 ) << ( L - 1 ) ) ;
Inv = fpow( limit, P - 2 ) ;
}
LL C( int x ) {
return 1ll * x * ( x - 1 ) / 2 ;
}
signed main()
{
n = gi(), p = gi(), m = gi() ;
Dg[0] = 1, Dg[1] = fpow( G, ( P - 1 ) / m ) ;
rep( i, 2, m ) Dg[i] = ( Dg[i - 1] * Dg[1] ) % P ;
rep( i, 0, m - 1 ) A[i] = fpow( Dg[i] * p + 1, n ), B[i] = Dg[i] * p % P * fpow( Dg[i] * p + 1, n - 1 ) % P ;
LL Ans1 = 0, Ans2 = 0, Ans = 0 ;
rep( i, 0, m - 1 ) A[i] = Dg[C(i) % m] * A[i] % P, B[i] = Dg[C(i) % m] * B[i] % P,
F[i] = Dg[C(i) % m] % P, F2[i] = 1ll * i * Dg[C(i) % m] % P ;
Init(), NTT( A, 1 ), NTT( B, 1 ), NTT( F, 1 ), NTT( F2, 1 ) ;
rep( i, 0, limit - 1 ) A[i] = ( F2[i] * A[i] ) % P, B[i] = ( F[i] * B[i] ) % P ;
NTT( A, -1 ), NTT( B, -1 ) ;
rep( i, 0, limit ) A[i] = A[i] * Dg[m - C(i) % m] % P, B[i] = B[i] * Dg[m - C(i) % m] % P,
Ans2 = ( Ans2 + A[i] ) % P, Ans1 = ( Ans1 + B[i] ) % P ;
Ans1 = ( 1ll * Ans1 * ( n % P ) ) % P ;
Ans = ( Ans1 - Ans2 + P ) % P ;
Ans = ( Ans * fpow( m * m % P, P - 2 ) ) % P ;
printf("%lld\n", Ans ) ;
return 0 ;
}因为多项式实在是做少了所以调得非常自闭...，下次再写我开数组绝对不这么吝啬QAQ我错了
原文：https://www.cnblogs.com/Soulist/p/11673254.html