danihao123's Blog

又学了个新套路呢qwq

题面要求的其实是：

\[\sum_{i = 0}^n [k|i]\binom{n}{i} F_i\]

不考虑那个\([k|i]\)，式子是非常像一个二项式展开的……

考虑构造矩阵的二项式展开，可以发现（其中\(A\)是斐波那契数列的二项式展开）：

\[(I + A)^n = \sum_{i = 0}^n \binom{n}{i} A^i\]

然后\(k=1\)的情况我们就会做辣！接下来的问题是，如何取出一个生成函数中次数为\(k\)倍数的项求和？

然后我们发现单位根有个非常优良的性质：

\[\frac{1}{k} \sum_{i=1}^{k} \xi_k^{ni} = [k|n]\]

这里的\(n\)是一个常数，但是其实可以对应到原式里的某一项的次数。至于证明……满足\(k|n\)的情况左边显然是一堆1取平均值，其他情况可以通过等比数列求和证明左边为0。

于是可以构造多项式\((I+xA)^n\)，把所有\(k\)次单位根做为\(x\)（求这个的话，可以利用原根）带入，对结果取平均值即可。

代码：

/**************************************************************
    Problem: 3328
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9080 ms
    Memory:832 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
typedef long long ll;
typedef ll Mat[2][2];
ll p; int k;
ll pow_mod(ll a, ll b) {
  ll ans = 1LL, res = a % p;
  while(b) {
    if(1LL & b) ans = (ans * res) % p;
    res = (res * res) % p;
    b /= 2LL;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, p - 2LL);
}
 
void factor(int x, std::vector<int> &V) {
  int bd = sqrt(x + 0.5);
  for(int i = 2; i <= bd; i ++) {
    if(x % i == 0) {
      V.push_back(i);
      while(x % i == 0) x /= i;
    }
  }
  if(x > 1) V.push_back(x);
}
int get_phi() {
  if(p == 2LL) return 1LL;
  std::vector<int> V;
  factor(p - 1LL, V);
  for(int i = 2; i <= (p - 1); i ++) {
    bool flag = true;
    for(int j = 0; j < V.size(); j ++) {
      int up = (p - 1) / V[j];
      if(pow_mod(i, up) == 1LL) {
        flag = false; break;
      }
    }
#ifdef LOCAL
    if(flag) printf("xi : %d\n", i);
#endif
    if(flag) return i;
  }
}
 
void mat_mul(const Mat &A, const Mat &B, int n, int m, int t, Mat &C) {
  Mat D; memset(D, 0, sizeof(D));
  for(int i = 0; i < n; i ++) {
    for(int j = 0; j < t; j ++) {
      for(int k = 0; k < m; k ++) {
        D[i][j] = (D[i][j] + (A[i][k] * B[k][j]) % p) % p;
      }
    }
  }
  memcpy(C, D, sizeof(D));
}
void mat_pow(const Mat &A, int n, ll b, Mat &ret) {
  Mat C, res;
  memset(C, 0, sizeof(C));
  for(int i = 0; i < n; i ++) C[i][i] = 1LL;
  memset(res, 0, sizeof(res));
  memcpy(res, A, sizeof(res));
  while(b) {
    if(1LL & b) mat_mul(C, res, n, n, n, C);
    mat_mul(res, res, n, n, n, res);
    b /= 2LL;
  }
  memcpy(ret, C, sizeof(C));
}
 
int main() {
  int T; scanf("%d", &T);
  while(T --) {
    ll n;
    scanf("%lld%d%lld", &n, &k, &p);
    ll xi = pow_mod(get_phi(), (p - 1) / k);
    ll w = 1LL;
    ll ans = 0;
    for(int i = 0; i < k; i ++) {
      Mat X;
      memset(X, 0, sizeof(X));
      X[0][0] = X[1][0] = X[0][1] = w;
      X[0][0] = (X[0][0] + 1LL) % p;
      X[1][1] = (X[1][1] + 1LL) % p;
      mat_pow(X, 2, n, X);
#ifdef LOCAL
      puts("X : ");
      for(int i = 0; i < 2; i ++) {
        for(int j = 0; j < 2; j ++) {
          printf("%lld ", X[i][j]);
        }
        puts("");
      }
#endif
      ans = (ans + X[0][0]) % p;
      w = (w * xi) % p;
    }
    ans = (ans * inv(k)) % p;
    printf("%lld\n", ans);
  }
  return 0;
}

终于调过去了……（然而不就是道NTT+生成函数水题吗至于调半天）

首先积非常的恶心，考虑转成和。这个事需要求指标的……求指标的话枚举原根的若干次幂即可（恰好$m$是素数一定有原根……），判断原根用比较大力的手段即可（我搞了一个$O(n\sqrt{n}logn)$的……求轻喷）。

然后这题还算比较简单吧……用生成函数表示原来的集合，然后$n$次幂就可以了。

注意那事个循环卷积……所以要开两倍然后每次乘完了再把右半部分搞过去。

代码：

/**************************************************************
    Problem: 3992
    User: danihao123
    Language: C++
    Result: Accepted
    Time:6652 ms
    Memory:1864 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
#include <cmath>
typedef long long ll;
const int maxn = 32005;
const ll ha = 1004535809LL;
const ll bs = 3LL;
ll n, m, gl; int sz;
ll pow_mod(ll a, ll b, ll p) {
  if(!b) return 1LL;
  ll ans = pow_mod(a, b >> 1, p);
  ans = (ans * ans) % p;
  if(b & 1LL) ans = (ans * a) % p;
  return ans;
}
ll inv(ll x, ll p) {
  return pow_mod(x, p - 2LL, p);
}
void break_up(ll x, std::vector<ll> &V) {
  int bd = sqrt(x + 0.5);
  for(ll i = 2; i <= bd; i ++) {
    if(x % i == 0) {
      V.push_back(i);
      while(x % i == 0) x /= i;
    }
    if(x == 1LL) break;
  }
  if(x > 1LL) V.push_back(x);
}
ll get_phi() {
  if(m == 2LL) return 1LL;
  ll mi = m - 1LL;
  std::vector<ll> V;
  break_up(mi, V);
  for(ll i = 2; i <= mi; i ++) {
    bool ok = true;
    for(int j = 0; j < V.size(); j ++) {
      ll b = mi / V[j];
      if(pow_mod(i, b, m) == 1LL) {
        ok = false;
#ifdef LOCAL
        printf("%lld not passed!\n", i);
#endif
        break;
      }
    }
    if(ok) {
      return i;
    }
  }
}
 
int bi, len;
int flip(int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans += (1 << (bi - i - 1));
    }
  }
  return ans;
}
void ntt(ll *A, bool flag = false) {
  for(int i = 0; i < len; i ++) {
    int v = flip(i);
    if(v < i) std::swap(A[i], A[v]);
  }
  for(int L = 1; L < len; L <<= 1) {
    ll xi_n = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)), ha);
    if(flag) xi_n = inv(xi_n, ha);
    for(int i = 0; i < len; i += (L << 1)) {
      ll w = 1;
      for(int j = i; j < i + L; j ++) {
        ll p1 = A[j], p2 = A[j + L];
        A[j] = (p1 + (p2 * w) % ha) % ha;
        A[j + L] = (p1 - (p2 * w) % ha + ha) % ha;
        w = (w * xi_n) % ha;
      }
    }
  }
}
void poly_mul(ll *A, ll *B) {
  static ll C[maxn]; memset(C, 0, sizeof(C));
#ifdef LOCAL
  printf("A :");
  for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
  puts("");
  printf("B :");
  for(int i = 0; i < len; i ++) printf(" %lld", B[i]);
  puts("");
#endif
  ntt(A); ntt(B);
  for(int i = 0; i < len; i ++) C[i] = (A[i] * B[i]) % ha;
  ntt(C, true);
  ll inv_n = inv(len, ha);
  for(int i = 0; i < len; i ++) {
    C[i] = (C[i] * inv_n) % ha;
  }
#ifdef LOCAL
  printf("C (not processed) :");
  for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
  puts("");
#endif
  for(int i = 0; i < len; i ++) {
    int v = i % (m - 1LL);
    if(v != i) {
      C[v] = (C[v] + C[i]) % ha;
      C[i] = 0LL;
    }
  }
#ifdef LOCAL
  printf("C :");
  for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
  puts("");
#endif
  std::copy(C, C + len, A);
}
void poly_pow(ll *A, ll b) {
  static ll B[maxn];
  static ll res[maxn];
  std::copy(A, A + len, res);
  std::fill(A, A + len, 0); A[0] = 1LL;
#ifdef LOCAL
  printf("A :");
  for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
  puts("");
  printf("res : ");
  for(int i = 0; i < len; i ++) printf("%lld ", res[i]);
  puts("");
#endif
  while(b) {
    if(1LL & b) {
      std::copy(res, res + len, B);
      poly_mul(A, B);
      std::fill(B, B + len, 0);
    }
    std::copy(res, res + len, B);
    poly_mul(res, B);
    std::fill(B, B + len, 0);
    b >>= 1LL;
  }
}
 
int main() {
  static bool vis[maxn];
  static ll A[maxn];
  scanf("%lld%lld%lld%d", &n, &m, &gl, &sz);
  ll phi = get_phi();
  for(int i = 1; i <= sz; i ++) {
    int v; scanf("%d", &v);
    if(v == 0) continue;
    vis[v] = true;
  }
  int logx = 0;
  bi = 0; len = 1;
  while(len <= (2 * m - 2)) {
    bi ++; len <<= 1;
  }
  for(int i = 0; i < (m - 1); i ++) {
    int v = pow_mod(phi, i, m);
    if(vis[v]) {
      A[i] ++;
#ifdef LOCAL
      printf("log(%d) : %d\n", v, i);
#endif
    }
    if(v == gl) {
      logx = i;
    }
  }
  poly_pow(A, n);
  printf("%lld\n", A[logx]);
  return 0;
}