[51Nod 1355]斐波那契的最小公倍数

MIN-MAX容斥第一题……

众所周知斐波那契数有个非常好的性质:

\[\gcd(\{f_i | i\in T\}) = f_{\gcd\{T\}}\]

但很不幸的事情是,lcm没有类似的性质。那我们就考虑怎么把lcm改成gcd。

根据MIN-MAX容斥,可以得到这个式子(可以理解为对指数的容斥。这里设\(S\)为全集):

\[\prod_{T\subseteq S, T\neq\emptyset} f_{\gcd\{T\}}^{(-1)^{|T| + 1}}\]

gcd套在上面非常烦人,考虑用狄利克雷卷积去化解它。考虑有个函数\(g\)满足\(f_n = \prod_{d|n} g(d)\),然后xjb化简一下之后柿子变成:

\[\prod_{d} g(d)^{\sum_{T\subseteq S, T\neq\emptyset, \forall x\in T, d | x}(-1)^{|T| + 1}}\]

再去考虑那个指数。当且仅当\(d\in S\)时,\(g(d)\)才会对答案做贡献。并且无论\(S\)中\(d\)的约数有多少个(只要大于),最后指数肯定都是1。因为其实大于零的情况那个指数也是一个所有最小值都是1的MIN-MAX容斥……这样求出来最大值肯定是1了,那个指数自然就是1。

于是乎柿子变成了:

\[\prod_{\exists x\in S, d | x} g(d)\]

然后搞出来\(S\)中所有数的约数很容易。当务之急就是求\(g\)了(这里其实就是莫比乌斯反演了)。不过球莫比乌斯函数反而让问题复杂化了……移下项可以发现:

\[g(n) = f_n\cdot (\prod_{d | n, d\neq n} g(d))^{-1}\]

然后就很愉快的搞出来了(逃

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 1000005;
using ll = long long;
const ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1LL, res = a;
  while(b) {
    if(1LL & b) {
      ans = (ans * res) % ha;
    }
    res = (res * res) % ha;
    b /= 2LL;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

ll f[maxn], g[maxn];
void process_f() {
  int N = 1000000;
  f[0] = 0LL; f[1] = 1LL;
  for(int i = 2; i <= N; i ++) {
    f[i] = (f[i - 1] + f[i - 2]) % ha;
  }
  std::fill(g + 1, g + 1 + N, 1LL);
  for(int i = 1; i <= N; i ++) {
    g[i] = (f[i] * inv(g[i])) % ha;
    for(int j = i * 2; j <= N; j += i) {
      g[j] = (g[j] * g[i]) % ha;
    }
  }
#ifdef LOCAL
  puts("g has been processed!");
#endif
}

bool vis[maxn];
void process_vis() {
  int N = 1000000;
  for(int i = 1; i <= N; i ++) {
    for(int j = i * 2; j <= N; j += i) {
      vis[i] = (vis[i] || vis[j]);
    }
  }
}

int main() {
  process_f();
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    int a; scanf("%d", &a);
    vis[a] = true;
  }
  process_vis();
  ll ans = 1LL;
  for(int i = 1; i <= 1000000; i ++) {
    if(vis[i]) {
      ans = (ans * g[i]) % ha;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

[BZOJ 4816][SDOI2017]数字表格

当年在考场上一点反演都不会啊啊啊啊啊啊

这题虽然牵扯到了对积的反演,但其实也不是很难。先让我们大力推导一波(逃

考虑枚举柿子中的\(f[(i, j)]\)中的最大公约数(设为\(k\)),然后式子变成了(这里不妨偷个懒,钦定\(n\leq m\)):

\[\prod_{k = 1}^n f[k]^{\sum_{i = 1}^n \sum_{j = 1}^m\:[(i, j) = k]}\]

然后发现上面那个指数就是Problem b的式子,显然可化为\(\sum_{d = 1}^n \mu(d) \lfloor\frac{n}{kd}\rfloor \lfloor\frac{m}{kd}\rfloor\)。然后似乎化简没有余地了,但是根据直觉,我们可以钦定\(T = kd\),然后枚举\(T\)。

然后柿子变成了:

\[\prod_{T = 1}^n (\prod_{k\mid T} f[k]^{\mu(\tfrac{T}{k})})^{\lfloor\tfrac{n}{T}\rfloor \lfloor\tfrac{m}{T}\rfloor}\]

柿子中的\(\prod_{k\mid T} f[k]^{\mu(\tfrac{T}{k})}\)是一个类似狄利克雷卷积的东西(取完对数就是了),可以枚举约数预处理。并且这个东西很不错的一点就是上面的指数是莫比乌斯函数,可以取到的值只有那三种,不需要快速幂。

然后剩下的部分就和通常的反演题一般无二了……

代码(卡线过的蒟蒻……求轻喷……但我在LOJ上跑的还挺快的):

/**************************************************************
    Problem: 4816
    User: danihao123
    Language: C++
    Result: Accepted
    Time:50840 ms
    Memory:33048 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cctype>
#include <cassert>
const int N = 1000000;
const int maxn = N + 5;
typedef long long ll;
const ll ha = 1000000007LL;
bool p_flag = false;
ll pow_mod(ll a, ll b) {
  if(!b) return 1LL;
  ll ans = pow_mod(a, b / 2LL);
  ans = (ans * ans) % ha;
  if(1LL & b) ans = (ans * a) % ha;
#ifdef LOCAL
  if(p_flag) printf("%lld^%lld : %lld\n", a, b, ans);
  if(b == ha - 2LL) p_flag = false;
#endif
  return ans;
}
ll inv(ll x) {
  // if(x == 1LL) p_flag = true;
  return pow_mod(x, ha - 2LL);
}
int miu[maxn];
void sieve() {
  static int prm[maxn]; int cnt = 0;
  static bool vis[maxn];
  miu[1] = 1;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      miu[i] = -1;
      prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt && prm[j] * i <= N; j ++) {
      int v = prm[j] * i;
      vis[v] = true;
      if(i % prm[j] == 0) {
        miu[v] = 0;
        break;
      } else {
        miu[v] = miu[i] * -1;
      }
    }
  }
}
ll f[maxn], inv_d[maxn], F[maxn];
void process() {
  sieve();
  f[1] = 1LL; inv_d[1] = 1LL;
  for(int i = 2; i <= N; i ++) {
    f[i] = (f[i - 1] + f[i - 2]) % ha;
    inv_d[i] = inv(f[i]);
    assert(f[i] != 0LL); assert(inv_d[i] != 0LL);
  }
  for(int i = 1; i <= N; i ++) F[i] = 1LL;
  for(int i = 1; i <= N; i ++) {
    for(int j = i; j <= N; j += i) {
      int res = j / i;
      if(miu[res] == 1) {
        F[j] = (F[j] * f[i]) % ha;
#ifdef LOCAL
        if(j <= 3) printf("f[%d](%lld) -> F[%d]\n", i, f[i], j);
#endif
        continue;
      }
      if(miu[res] == -1) {
        F[j] = (F[j] * inv_d[i]) % ha;
#ifdef LOCAL
        if(j <= 3) printf("inv_f[%d](%lld) -> F[%d]\n", i, inv_d[i], j);
#endif
      }
    }
  }
  F[0] = 1LL;
  bool flag = true;
  for(int i = 1; i <= N; i ++) {
    F[i] = (F[i] * F[i - 1]) % ha;
    if(flag && F[i] == 0LL) {
      printf("SF[%d] has been 0.\n", i);
      flag = false;
    }
  }
}
 
ll calc(ll n, ll m) {
  if(n > m) std::swap(n, m);
  ll ans = 1LL;
  for(ll i = 1; i <= n;) {
    ll nx = std::min(n / (n / i), m / (m / i));
#ifdef LOCAL
    // printf("nx of %lld : %lld\n", i, nx);
#endif
    ll mulv = pow_mod((F[nx] * inv(F[i - 1])) % ha, (n / i) * (m / i));
    ans = (ans * mulv) % ha;
    i = nx + 1LL;
  }
  return ans;
}
 
int main() {
  process();
  int T; scanf("%d", &T);
  while(T --) {
    int n, m; scanf("%d%d", &n, &m);
    printf("%lld\n", calc(n, m));
  }
  return 0;
}

[坑]狄利克雷卷积和反演

开个坑,记录一些和反演以及狄利克雷卷积的东西。

首先积性函数、狄利克雷卷积等基本概念不写了,就讲讲性质吧。

有几个一定要记住的东西:

\[\mu \ast 1 = e\]

\[\varphi \ast 1 = id\]

\[\mu \ast id = \varphi\]

这几个在推式子的过程中都有很大的作用,务必要记住。

所谓莫比乌斯反演,其实就是:

\[F = f \ast 1\Leftrightarrow f = F \ast \mu\]

(谜之音:其实很多所谓“反演题”都没用到这俩性质啊……)

关于莫比乌斯函数本身,还有一个好康的性质:

\[(\mu\ast 1)(k) = \sum_{i = 0}^k (-1)^i C_k^i\]

继续阅读