题目链接

LuoguP2000

题目概括

给你$n$个东西,再给一些排列的限制,问有多少种排列的方案数。
数据范围 $10^{100000} n\leq 10^{100001}$

思路要点

逐个条件构造生成函数后全部卷积起来,第$n$位就是答案。
用$NTT$加速高精度乘法。
时间复杂度 $O(m\log_2 m),m=log_{10}n$

代码

#include <bits/stdc++.h>

using namespace std;

template <class T>
void chkmax(T& x, T y) {
  x = x > y ? x : y;
}

template <class T>
void chkmin(T& x, T y) {
  x = x < y ? x : y;
}

template <class T>
void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}

template <class T>
void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}

template <class T>
void writeln(T x) {
  write(x), puts("");
}

typedef vector<int> poly;

const int N = 100005;
const int MOD = 998244353;
const int g = 3;

int expand(int x) {
  int r = 1; 
  while (r < x) r <<= 1;
  return r;
}

template <class T> T add(T x, T y) {
  return (x += y) >= MOD ? x -= MOD : x; 
}

template <class T> T sub(T x, T y) {
  return (x -= y) < 0 ? x += MOD : x; 
}

template <class T> T mul(T x, T y) {
  return (long long)x * y % MOD;
}

template <class T> T power(T x, T y) {
  T res = 1; 
  for (; y; y >>= 1, x = mul(x, x)) 
    if (y & 1) res = mul(res, x);
  return res;
}

namespace FFT {
  void NTT(poly& a, bool type) {
    int n = a.size(), k = 0;
    while ((1 << k) < n) k++;
    vector<int> rev(n); 
    for (int i = 0; i < n; i++) {
      rev[i] = rev[i >> 1] >> 1 | (i & 1) << (k - 1);
      if (i < rev[i]) swap(a[i], a[rev[i]]);
    }
    for (int mid = 1; mid < n; mid <<= 1) {
      int wn = power(g, (MOD - 1) / (mid << 1));
      if (type) wn = power(wn, MOD - 2);
      for (int i = 0; i < n; i += (mid << 1)) 
        for (int j = 0, w = 1; j < mid; j++, w = mul(w, wn)) {
          int x = a[i + j], y = mul(w, a[i + j + mid]);
          a[i + j] = add(x, y), a[i + j + mid] = sub(x, y);
        }
    }
  }
  
  void DFT(poly& a) {
    NTT(a, 0);
  }
  
  void IDFT(poly& a) {
    NTT(a, 1);
    int invn = power((int)a.size(), MOD - 2);
    for (int i = 0; i < (int)a.size(); i++) a[i] = mul(a[i], invn); 
  }
}

namespace Poly {
  poly operator * (poly a, poly b) {
    int n = a.size(), m = b.size(), k = expand(n + m - 1);
    a.resize(k), b.resize(k);
    FFT::DFT(a), FFT::DFT(b);
    for (int i = 0; i < k; i++) a[i] = mul(a[i], b[i]);
    FFT::IDFT(a);
    a.resize(n + m - 1);
    return a;
  }
}

using namespace Poly;

poly fix(poly a) {
  int n = a.size(); a.resize(n + 1); a[n] = 0;
  for (int i = 0; i < n; i++) {
    a[i + 1] += a[i] / 10;
    a[i] %= 10;
  }
  int m = a.size(); 
  while (a[m - 1] == 0) m--;
  a.resize(m);
  return a;
}

void print(poly a) {
  for (int i = a.size() - 1; i >= 0; i--) write(a[i]); puts("");
}

char s[N];
int n;
 
int main() {
  scanf("%s", s);
  n = strlen(s);
  poly a(n), ans(1); 
  ans[0] = 1;
  for (int i = 0; i < n; i++) a[n - i - 1] = s[i] - '0';
  a[0] += 1, a = fix(a), ans = fix(ans * a); 
  a[0] += 1, a = fix(a), ans = fix(ans * a);
  a[0] += 1, a = fix(a), ans = fix(ans * a);
  a[0] += 1, a = fix(a), ans = fix(ans * a); 
  for (int i = (int)ans.size() - 1; i > 0; i--) 
    ans[i - 1] += ans[i] % 24 * 10, ans[i] /= 24;
  ans[0] /= 24;
  ans = fix(ans);
  print(ans);
  return 0;
}
最后修改:2020 年 03 月 03 日 08 : 56 AM
如果觉得我的文章对你有用,请随意赞赏