P5591 小猪佩奇学数学(单位根反演)

  • 时间:
  • 浏览:
  • 来源:互联网

P5591 小猪佩奇学数学

∑ i = 0 n ( i n ) × p i × ⌊ i k ⌋ ⌊ i k ⌋ = i − i % k k 1 k ∑ i = 0 n ( i n ) × p i × ( i − i % k ) 1 k ∑ i = 0 n ( i n ) × p i × i − 1 k ∑ i = 0 n ( i n ) × p i ( i m o d    k ) \sum_{i = 0} ^{n} (_i ^ n) \times p ^ i \times \lfloor \frac{i}{k} \rfloor\\ \lfloor \frac{i}{k} \rfloor = \frac{i - i \% k}{k}\\ \frac{1}{k} \sum_{i = 0} ^{n} (_i ^ n) \times p ^ i \times (i - i \% k)\\ \frac{1}{k} \sum_{i = 0} ^{n} (_i ^ n) \times p ^ i \times i - \frac{1}{k} \sum_{i = 0} ^{n} (_i ^ n) \times p ^ i (i \mod k)\\ i=0n(in)×pi×kiki=kii%kk1i=0n(in)×pi×(ii%k)k1i=0n(in)×pi×ik1i=0n(in)×pi(imodk)
考虑前项化简:
1 k ∑ i = 0 n ( i n ) × p i × i ∑ i = 0 n ( i n ) × i = ∑ i = 0 n n ! i ! ( n − i ) ! i = ∑ i = 1 n n ! ( i − 1 ) ! ( n − i ) ! n ∑ i = 1 n ( n − 1 ) ! ( i − 1 ) ! ( n − i ) ! = n ∑ i = 1 n ( i − 1 n − 1 ) 原 式 n p k ∑ i = 1 n ( i − 1 n − 1 ) p i − 1 = n p k ( p + 1 ) n − 1 \frac{1}{k} \sum_{i = 0} ^{n} (_i ^ n) \times p ^ i \times i\\ \sum_{i = 0} ^{n} (_i ^ n) \times i = \sum_{i = 0} ^{n} \frac{n!}{i!(n - i)!} i = \sum_{i = 1} ^{n} \frac{n!}{(i - 1)!(n - i)!}\\ n\sum_{i = 1} ^{n} \frac{(n - 1)!}{(i - 1)!(n - i)!} = n \sum_{i = 1} ^{n} (_{i - 1} ^{n - 1})\\ 原式\frac{np}{k} \sum_{i = 1} ^{n} (_{i - 1} ^{n - 1}) p ^{i - 1} = \frac{np}{k} (p + 1) ^{n - 1}\\ k1i=0n(in)×pi×ii=0n(in)×i=i=0ni!(ni)!n!i=i=1n(i1)!(ni)!n!ni=1n(i1)!(ni)!(n1)!=ni=1n(i1n1)knpi=1n(i1n1)pi1=knp(p+1)n1
考虑后项化简:
1 k ∑ d = 0 k − 1 d ∑ i = 0 n ( i n ) p i [ k ∣ i − d ] 对 [ k ∣ i − d ] 进 行 单 位 根 反 演 1 k ∑ d = 0 k − 1 d ∑ i = 0 n ( i n ) × p i × 1 k ∑ j = 0 k − 1 w k j ( i − d ) 1 k 2 ∑ d = 0 k − 1 d ∑ j = 0 k − 1 w k − j d ∑ i = 0 n ( i n ) p i w k i j 1 k 2 ∑ d = 0 k − 1 d ∑ j = 0 k − 1 w k − j d ( p w k j + 1 ) n 1 k 2 ∑ j = 0 k − 1 ( p × w k j + 1 ) n ∑ d = 0 k − 1 d × w k − j d \frac{1}{k} \sum_{d = 0} ^{k - 1} d \sum_{i = 0} ^{n} (_i ^ n) p ^ i[k \mid i - d]\\ 对[k \mid i - d]进行单位根反演\\ \frac{1}{k} \sum_{d = 0} ^{k - 1} d \sum_{i = 0} ^{n} (_i ^ n) \times p ^ i \times \frac{1}{k} \sum_{j = 0} ^{k - 1} w_k ^{j(i- d)}\\ \frac{1}{k ^ 2}\sum_{d = 0} ^{k - 1} d \sum_{j = 0} ^{k - 1} w_{k} ^{-jd} \sum_{i = 0} ^{n} (_i ^ n) p ^ i w_{k} ^{ij}\\ \frac{1}{k ^ 2} \sum_{d = 0} ^{k - 1} d \sum_{j = 0} ^{k - 1} w_{k} ^{-jd} (pw_k ^{j} + 1) ^{n}\\ \frac{1}{k ^ 2} \sum_{j = 0} ^{k - 1} (p \times w_k ^ j + 1) ^n \sum_{d = 0} ^{k - 1} d \times w_{k} ^{-jd}\\ k1d=0k1di=0n(in)pi[kid][kid]k1d=0k1di=0n(in)×pi×k1j=0k1wkj(id)k21d=0k1dj=0k1wkjdi=0n(in)piwkijk21d=0k1dj=0k1wkjd(pwkj+1)nk21j=0k1(p×wkj+1)nd=0k1d×wkjd
∑ d = 0 k − 1 d × w k − j d \sum\limits_{d = 0} ^{k - 1} d \times w_k ^{-jd} d=0k1d×wkjd形如 ∑ i = 0 n − 1 i r i \sum\limits_{i = 0} ^{n - 1} i r ^ i i=0n1iri,考虑形如 ∑ i = 0 n − 1 ( i + 1 ) r i + 1 \sum\limits_{i = 0} ^{n - 1} (i + 1) r ^ {i + 1} i=0n1(i+1)ri+1这样的式子化简:
∑ i = 0 n − 1 ( i + 1 ) r i + 1 = r ∑ i = 0 n − 1 i r i + ∑ i = 0 n − 1 r i + 1 = r ∑ i = 0 n − 1 i r i + r ( r n − 1 ) r − 1 有 ∑ i = 0 n − 1 i r i = ∑ i = 0 n − 1 ( i + 1 ) r i + 1 − 0 r 0 − n r n 所 以 ∑ i = 0 n − 1 i r i = r ∑ i = 0 n − 1 i r i + r ( r n − 1 ) r − 1 − n r n 整 理 可 得 ∑ i = 0 n − 1 i r i = n r n − r ( r n − 1 ) r − 1 r − 1 = n r n ( r − 1 ) − r ( r n − 1 ) ( r − 1 ) 2 = n r n r − 1 − r ( r n − 1 ) ( r − 1 ) 2 \sum_{i = 0} ^{n - 1} (i + 1) r ^{i + 1} = r\sum_{i = 0} ^{n - 1} i r ^i + \sum_{i = 0} ^{n - 1} r ^{i + 1} = r \sum_{i = 0} ^{n - 1} i r ^ i + \frac{r(r ^ n - 1)}{r - 1}\\ 有\sum_{i = 0} ^{n - 1} i r ^ i = \sum_{i = 0} ^{n - 1} (i + 1) r ^{i + 1} - 0 r ^ 0 - n r ^ n\\ 所以\sum_{i = 0} ^{n - 1} i r ^ i = r \sum_{i = 0} ^{n - 1} i r ^ i + \frac{r(r ^ n - 1)}{r - 1} - n r ^ n\\ 整理可得\sum_{i = 0} ^{n - 1} i r ^ i = \frac{n r ^ n - \frac{r(r ^ n - 1)}{r - 1}}{r - 1} = \frac{n r ^ n(r - 1) - r (r ^ n - 1)}{(r - 1) ^ 2} = \frac{nr ^ n}{ r - 1} - \frac{r(r ^ n - 1)}{(r - 1) ^ 2}\\ i=0n1(i+1)ri+1=ri=0n1iri+i=0n1ri+1=ri=0n1iri+r1r(rn1)i=0n1iri=i=0n1(i+1)ri+10r0nrni=0n1iri=ri=0n1iri+r1r(rn1)nrni=0n1iri=r1nrnr1r(rn1)=(r1)2nrn(r1)r(rn1)=r1nrn(r1)2r(rn1)
特殊情况 r = 1 r = 1 r=1 ∑ i = 0 n − 1 i r i = n ( n − 1 ) 2 \sum\limits_{i = 0} ^{n - 1} i r ^ i = \frac{n(n - 1)}{2} i=0n1iri=2n(n1),对后项再进行化简:
∑ d = 0 k − 1 d × w k − j d 考 虑 j ≠ 0 时 , 也 就 是 w k j 不 为 1 ∑ d = 0 k − 1 d × w k − j d = k w k − j k w k − j − 1 − w k − j ( w k − j k − 1 ) ( w k − j − 1 ) 2 = k w k − j − 1 后 项 整 体 有 : 1 k 2 ∑ j = 0 k − 1 ( p × w k j + 1 ) n k w k − j − 1 \sum_{d = 0} ^{k - 1} d \times w _k ^{-jd}\\ 考虑j \neq 0时,也就是w_{k} ^{j}不为1\\ \sum_{d = 0} ^{k - 1} d \times w_k ^{-jd} = \frac{k w_k ^ {-jk}}{w_k ^{-j} - 1} - \frac{w_k ^{-j}(w_k ^{-jk} - 1)}{(w_k ^{-j} - 1) ^ 2} = \frac{k}{w_k ^{-j} - 1}\\ 后项整体有:\frac{1}{k ^ 2} \sum_{j = 0} ^{k - 1} (p \times w_k ^ j + 1) ^ n \frac{k}{w_k ^{-j} - 1}\\ d=0k1d×wkjdj=0wkj1d=0k1d×wkjd=wkj1kwkjk(wkj1)2wkj(wkjk1)=wkj1k:k21j=0k1(p×wkj+1)nwkj1k
最后答案为:
n p k ( p + 1 ) n − 1 − ( k ( k − 1 ) 2 ( p + 1 ) n k 2 + ∑ j = 1 k − 1 ( p × w k j + 1 ) n k ( w k − j − 1 ) ) n p k ( p + 1 ) n − 1 − ( ( k − 1 ) ( p + 1 ) n 2 k + ∑ j = 1 k − 1 ( p × w k j + 1 ) n k ( w k − j − 1 ) ) \frac{np}{k}(p + 1) ^ {n - 1} - \left(\frac{k(k - 1)}{2}\frac{(p + 1) ^ n}{k ^ 2} + \sum\limits_{j = 1} ^{k - 1} \frac{(p \times w_k ^ j + 1) ^ n}{k(w_{k} ^{-j} - 1)}\right)\\ \frac{np}{k}(p + 1) ^ {n - 1} - \left(\frac{(k - 1)(p + 1) ^ n}{2k} + \sum\limits_{j = 1} ^{k - 1} \frac{(p \times w_k ^ j + 1) ^ n}{k(w_{k} ^{-j} - 1)}\right)\\ knp(p+1)n1(2k(k1)k2(p+1)n+j=1k1k(wkj1)(p×wkj+1)n)knp(p+1)n1(2k(k1)(p+1)n+j=1k1k(wkj1)(p×wkj+1)n)

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353, N = 2e6 + 10;

int w[N], n, p, k;

int quick_pow(int a, int n) {
  int ans = 1;
  while (n) {
    if (n & 1) {
      ans = 1ll * ans * a % mod;
    }
    a = 1ll * a * a % mod;
    n >>= 1;
  }
  return ans;
}

int inv(int x) {
  return quick_pow(x, mod - 2);
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  scanf("%d %d %d", &n, &p, &k);
  int wn = quick_pow(3, (mod - 1) / k);
  int ans = 1ll * n * p % mod * quick_pow(p + 1, n - 1) % mod * inv(k) % mod;
  int res = 1ll * (k - 1) * quick_pow(p + 1, n) % mod * inv(2 * k) % mod;
  w[0] = 1;
  for (int i = 1; i < k; i++) {
    w[i] = 1ll * w[i - 1] * wn % mod;
  }
  for (int i = 1; i < k; i++) {
    res = (res + 1ll * quick_pow(1ll * p * w[i] % mod + 1, n) * inv(1ll * k * (w[k - i] - 1) % mod) % mod) % mod;
  }
  ans = (ans - res + mod) % mod;
  printf("%d\n", ans);
  return 0;
}

本文链接http://www.dzjqx.cn/news/show-617587.html