UOJ450

发表于 分类于
【集训队作业2018】复读机

【集训队作业2018】复读机

如果不看数据范围的话，这是一个经典问题。

令 $\hat{F} ( x ) = \sum _ {i=0} ^ {\infty} [ d \mid i ] x ^ {i} / i!$，我们要求的答案就是：

$$ Ans = n! \left[ \dfrac { x ^ n } { n ! } \right] \hat{F} ( x ) ^ k $$

但是 $\hat{F} ( x ) $ 的封闭形式不太好找，这个答案根本没法算。

考虑变换 $ \hat {F} ( x )$，使用单位根反演。

$$
\begin{aligned}
\hat{F} ( x ) = & \sum _ { i = 0 } ^ {\infty} \dfrac { x ^ i } { i ! } [ d \mid i ]
\\
= & \dfrac {1} {d} \sum _ { i = 0 } ^ {\infty} \dfrac { x ^ i } { i ! } \sum _ { j = 0 } ^ { d - 1 } \omega _ {d} ^ {ij}
\\
= & \dfrac {1} {d} \sum _ { j = 0 } ^ { d - 1 } \sum _ { i = 0 } ^ {\infty} \dfrac {(x \omega _ {d} ^ {j}) ^ i } { i ! }
\\
= & \dfrac {1} {d} \sum _ { j = 0 } ^ { d - 1 } e ^ { x \omega _ {d} ^ {j} }
\end{aligned}
$$

注意到这个特殊的数据范围，分类讨论 $d$：

  1. 若 $d=1$，则有：

    $$\hat{F} ( x ) = e ^ x$$

    那么答案就是：

    $$Ans = n! \left[ \dfrac{x^n}{n!} \right] e ^ {kx} = k ^ n $$

  2. 若 $d=2$，则有：

    $$\hat{F}(x)= \dfrac {e ^ x + e ^ { - x }} { 2 }$$

    代入答案的时候使用二项式定理展开：

    $$
    \begin{aligned}
    Ans = & n! \left[ \dfrac { x ^ n } { n ! } \right] \left( \dfrac {e ^ x + e ^ { - x }} { 2 } \right) ^ k
    \\
    = & \dfrac { n! } { 2 ^ k } \left[ \dfrac { x ^ n } { n ! } \right] \sum _ { i = 0 } ^ { k } \binom { k } { i } e ^ {ix} e ^ {- ( k - i ) x}
    \\
    = & \dfrac { n! } { 2 ^ k } \left[ \dfrac { x ^ n } { n ! } \right] \sum _ { i = 0 } ^ { k } \binom { k } { i } e ^ { ( 2 i - k ) x}
    \\
    = & \dfrac { 1 } { 2 ^ k } \sum _ { i = 0 } ^ { k } \binom { k } { i } ( 2 i - k ) ^ n
    \end{aligned}
    $$

    爆算的时间复杂度是 $ O ( k \log n ) $ 的，直接莽。

  3. 若 $ d = 3$，则：

    $$ \hat { F } ( x ) = \dfrac { e ^ x + e ^ { \omega _ 3 ^ 1 x} + e ^ {\omega _ 3 ^ 2 x}} { 3 }$$

    两次二项式定理把这玩意暴力展开：

    $$
    \begin{aligned}
    Ans = & n! \left[ \dfrac { x ^ n } { n ! } \right] \left( \dfrac { e ^ x + e ^ { \omega _ 3 ^ 1 x} + e ^ {\omega _ 3 ^ 2 x}} { 3 } \right) ^ k
    \\
    = & \dfrac {n!} {3 ^ k} \left[ \dfrac { x ^ n } { n ! } \right] \sum _ { i = 0 } ^ { k } \binom { k } { i } e ^ {\omega _ {3} ^ {2 } x i } \sum _ { j= 0 } ^ { k - i } \binom { k-i } { j } e ^ { x j } e ^ { \omega _ {3} ^ {1} x ( k - i - j )}
    \\
    = & \dfrac {n!} {3 ^ k} \left[ \dfrac { x ^ n } { n ! } \right] \sum _ { i = 0 } ^ { k } \binom { k } { i } \sum _ { j= 0 } ^ { k - i } \binom { k-i } { j } e ^ {(\omega _ {3} ^ {2} i + j + \omega _ {3} ^ {1} ( k - i - j ))}
    \\
    = & \dfrac { 1 } {3 ^ k} \sum _ { i = 0 } ^ { k } \binom { k } { i } \sum _ { j= 0 } ^ { k - i } \binom { k-i } { j } \left ( \omega _ {3} ^ {2} i + j + \omega _ {3} ^ {1} ( k - i - j ) \right) ^ {n}
    \end{aligned}
    $$

    看起来应该是 $O(k ^ 2 \log n)$ 可算，不过要求一下单位根。

    可以直接再写一个求三次单位根的程序，也可以凭借你的聪明才智发现它的原根是 7，然后用 Python 算一下 $7 ^ { \varphi (19491001)/3}$ 即可。

    这里我就直接给出 $\omega _ {3} ^ 1 = 663067$。

然后做完了。

代码：

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
59
60
61
62
63
64
65
66
67
68
#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 N=1e6,mo=19491001;

ll n,k,d,w1,w2;
ll fac[N+5],invfac[N+5];

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;
}

inline ll C(ll n,ll m) {return (fac[n]*invfac[m]%mo)*invfac[n-m]%mo;}

inline void Init_2(ll n) {
  fac[0]=1;for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%mo;
  invfac[0]=1;invfac[n]=Pow(fac[n],mo-2);
  for(ll i=n-1;i>=1;i--) invfac[i]=invfac[i+1]*(i+1)%mo;
}

inline ll F(ll i,ll j) {
  return Pow(((w2*i%mo+j)%mo+w1*(k-i-j)%mo)%mo,n);
}

int main() {

  n=read();k=read();d=read();

  if(d==1) {write(Pow(k,n));}
  if(d==2) {
    Init_2(k);
    ll ans=0;
    for(ll i=0;i<=k;i++) {ans=(ans+C(k,i)*Pow((2*i-k+mo)%mo,n)%mo)%mo;}
    ans=ans*Pow(Pow(2,k),mo-2)%mo;
    write(ans);
  }
  if(d==3) {
    Init_2(k);
    ll tmp=0;w1=663067;w2=w1*w1;
    for(ll i=0;i<=k;i++) {
      ll tmpp=0;
      for(ll j=0;j<=k-i;j++) {
        tmpp=(tmpp+C(k-i,j)*F(i,j)%mo)%mo;
      }
      tmp=(tmp+tmpp*C(k,i)%mo)%mo;
    }
    tmp=tmp*Pow(Pow(3,k),mo-2)%mo;
    write(tmp);
  }

  return 0;
}