P5591

发表于 分类于
小猪佩奇学数学

小猪佩奇学数学

先把这个转化为整除形式，然后单位根反演暴力推。

$$
\begin{aligned}
& \sum _ { i = 0 } ^ { n } \binom { n } { i } p ^ i \left \lfloor \dfrac { i } { k } \right \rfloor
\\
= & \sum _ { i = 0 } ^ { n } \binom { n } { i } p ^ i \dfrac { i - i \bmod k } { k }
\\
= & \dfrac { 1 } { k } \sum _ { i = 0 } ^ { n } i \binom { n } { i } p ^ i - \dfrac { 1 } { k } \sum _ { i = 0 } ^ { n } \binom { n } {i} p ^ i \sum _ { j = 0 } ^ { k - 1 } j [ i \equiv j \pmod { k } ]
\\
= & \dfrac { n } { k } \sum _ { i = 1 } ^ { n } \binom { n - 1 } { i - 1 } p ^ i - \dfrac { 1 } { k ^ 2 } \sum _ { i = 0 } ^ { n } \binom { n } {i} p ^ i \sum _ { j = 0 } ^ { k - 1 } j \sum _ { x = 0 } ^ { k - 1 } \omega _ { k } ^ { ( i - j ) x}
\\
= & \dfrac { n p } { k } \sum _ { i = 0 } ^ { n - 1 } \binom { n - 1 } { i } p ^ i 1 ^ { n - 1 - i } - \dfrac { 1 } { k ^ 2 } \sum _ { j = 0 } ^ { k - 1 } j \sum _ { i = 0 } ^ { n } \binom { n } {i} p ^ i \sum _ { x = 0 } ^ { k - 1 } \omega _ { k } ^ { - x j } \omega _ { k } ^ { x i }
\\
= & \dfrac { n p } { k } (p + 1 ) ^ { n - 1 } - \dfrac { 1 } { k ^ 2 } \sum _ { j = 0 } ^ { k - 1 } j \sum _ { x = 0 } ^ { k - 1 } \omega _ { k } ^ { - x j } \sum _ { i = 0 } ^ { n } \binom { n } {i} p ^ i \omega _ { k } ^ { x i }
\\
= & \dfrac { n p } { k } (p + 1 ) ^ { n - 1 } - \dfrac { 1 } { k ^ 2 } \sum _ { j = 0 } ^ { k - 1 } j \sum _ { x = 0 } ^ { k - 1 } \omega _ { k } ^ { - x j } \sum _ { i = 0 } ^ { n } \binom { n } {i} ( p \omega _ { k } ^ { x }) ^ i 1 ^ { n - i }
\\
= & \dfrac { n p } { k } (p + 1 ) ^ { n - 1 } - \dfrac { 1 } { k ^ 2 } \sum _ { j = 0 } ^ { k - 1 } j \sum _ { x = 0 } ^ { k - 1 } \omega _ { k } ^ { - x j } (p \omega _ { k } ^ { x } + 1 ) ^ n
\\
= & \dfrac { n p } { k } (p + 1 ) ^ { n - 1 } - \dfrac { 1 } { k ^ 2 } \sum _ { x = 0 } ^ { k - 1 } (p \omega _ { k } ^ { x } + 1 ) ^ n \sum _ { j = 0 } ^ { k - 1 } j \omega _ { k } ^ { - x j }
\\
= & \dfrac { n p } { k } (p + 1 ) ^ { n - 1 } - \dfrac { 1 } { k ^ 2 } \sum _ { x = 0 } ^ { k - 1 } (p \omega _ { k } ^ { x } + 1 ) ^ n \sum _ { j = 0 } ^ { k - 1 } j ( \omega _ { k } ^ { - x } ) ^ j
\end{aligned}
$$

可以 $ O ( k ^ 2 )$ 算了。

我们考虑快速计算 $ \sum _ { j = 0 } ^ { k - 1 } j ( \omega _ { k } ^ { - x }) ^ j $，看起来大概是个 Whk 数列题。

我们设 $ F ( x , y ) = \sum _ { i = 0 } ^ { y } i x ^ i $，同时再设 $ G ( x , y ) = \sum _ { i = 0 } ^ { y } x ^ i$，然后想办法找到封闭形式解决这个问题。

下面的推导默认 $ x \ne 1 $。

$ G ( x , y ) $ 的封闭形式很简单：

$$ x G ( x , k ) + 1 = G ( x , k ) + x ^ { k + 1 } $$

可以导出：

$$ G ( x , y ) = \dfrac { x ^ { k + 1 } - 1 } { x - 1 } $$

你当然可以看成简单的等比数列求和，不过我比较无聊，主要想把这个东西用到下面。

$$ x F ( x , k - 1 ) + G ( x , k ) - 1 = F ( x , k ) = F ( x , k - 1 ) + k x ^ k $$

可以导出：

$$ F ( x , k - 1 ) = \dfrac { k x ^ { k } + 1 - ( x ^ { k + 1 } - 1) / ( x - 1 ) } { x - 1 } $$

如果 $ x = 1 $ 的话，这个东西就跟简单了：

$$ F ( x , y ) = \sum _ { i = 0 } ^ { y } i = \dfrac { y ( y + 1 ) } { 2 }$$

而最后我们要求的就是 $ F ( \omega _ { k } ^ { - x } , k - 1 )$。

现在复杂度就是 $ O ( k \log n ) $ 的了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll mo=998244353,G=3;

inline ll Pow(ll b,ll p) {
  ll r=1;while(p) {if(p&1) r=r*b%mo;b=b*b%mo;p>>=1;}return r;
}

const ll invG=Pow(G,mo-2);

ll n,p,k,ans;

inline ll F(ll x) {
  if(x==1) {return (k*(k-1)%mo)*Pow(2,mo-2)%mo;}
  ll tmpinv=Pow(x-1,mo-2);
  ll tmp=k*Pow(x,k)%mo;
  tmp=(tmp+1)%mo;
  tmp=(tmp-((Pow(x,k+1)-1+mo)%mo)*tmpinv%mo+mo)%mo;
  tmp=tmp*tmpinv%mo;
  return tmp;
}

int main() {

  n=read();p=read();k=read();

  ans=n*p%mo;ans=ans*Pow(k,mo-2)%mo;ans=ans*Pow((p+1)%mo,n-1)%mo;

  ll tmp=0,buft=1,bufm=1,tG=Pow(G,(mo-1)/k),mG=Pow(invG,(mo-1)/k);
  for(ll i=0;i<k;i++) {
    ll tmpp=Pow((p*buft+1)%mo,n);
    tmpp=tmpp*F(bufm)%mo;tmp=(tmp+tmpp)%mo;
    buft=buft*tG%mo;bufm=bufm*mG%mo;
  }
  tmp=tmp*Pow(k*k%mo,mo-2)%mo;
  ans=(ans-tmp+mo)%mo;

  write(ans);

  return 0;
}