danihao123's Blog

求有多少正整数序列，满足所有数的最大公约数为\(x\)，所有数的和为\(y\)。

\(1\leq x, y\leq 10^9\)。

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

已经……没有什么好害怕的了

OI给了我足够的欢乐了，OI让我看到了新的世界，让我有了人生中最好的几位朋友，我没有什么可以遗憾的了……就算可能要面临最残酷的结局吧……

有点跑题了呢……还是说这个题吧

显然可以看出来这个题要求你的从大到小的匹配（姑且称之为好的匹配）恰好要有\(\frac{n + k}{2}\)个，剩下的全都不是好的匹配。

首先把糖果（记为\(A\)）和药片（记为\(B\)）分别排序，对于每一个\(A\)中元素就很容易得到\(B\)中有多少比它小的。考虑设计状态\(f[i][j]\)表示对（排序后的）\(A\)的前\(i\)项，已经确定了的好的匹配有至少\(j\)个。这个DP转移显然。

然后发现\(f[n][j]\times (n - j)!\)就是对于所有元素的完美匹配中，有至少\(j\)个是好的匹配的方案数。这正是广义容斥原理的用武之地。考虑记\(t_j = f[n][j]\times (n - j)!\)，那么答案就是（令\(\frac{n + k}{2} = l\)）：

\[\sum_{i = l}^n (-1)^{n - i}\binom{i}{l} t_i\]

代码：

/**************************************************************
    Problem: 3622
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1844 ms
    Memory:63680 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const ll ha = 1000000009LL;
const int maxn = 2005;
ll C[maxn][maxn], F[maxn];
inline void process() {
  int N = 2000;
  C[0][0] = 1LL;
  for(int i = 1; i <= N; i ++) {
    C[i][0] = C[i][i] = 1LL;
    for(int j = 1; j < i; j ++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % ha;
    }
  }
  F[0] = 1LL;
  for(int i = 1; i <= N; i ++) {
    F[i] = (F[i - 1] * (ll(i))) % ha;
  }
}
 
int A[maxn], B[maxn];
ll cp[maxn]; int n;
void gen_cp() {
  std::sort(A + 1, A + 1 + n); std::sort(B + 1, B + 1 + n);
  for(int i = 1; i <= n; i ++) {
    cp[i] = n - (B + n + 1 - std::upper_bound(B + 1, B + 1 + n, A[i]));
#ifdef LOCAL
    printf("cp[%d] : %lld\n", i, cp[i]);
#endif
  }
}
 
ll f[maxn][maxn];
ll dp(int dec) {
  process(); gen_cp();
  f[0][0] = 1LL;
  for(int i = 1; i <= n; i ++) {
    for(int j = 0; j <= n; j ++) {
      f[i][j] = f[i - 1][j];
      if(j > 0) {
        f[i][j] += (f[i - 1][j - 1] * std::max(0LL, cp[i] - ll(j - 1))) % ha;
        if(f[i][j] >= ha) f[i][j] -= ha;
      }
#ifdef LOCAL
      printf("f[%d][%d] : %lld\n", i, j, f[i][j]);
#endif
    }
  }
  for(int j = 0; j <= n; j ++) {
    f[n][j] = (f[n][j] * F[n - j]) % ha;
  }
  ll ans = 0;
  for(int j = dec; j <= n; j ++) {
    ll a = ((j - dec) % 2 == 0) ? 1LL : (ha - 1LL);
    ll delta = (C[j][dec] * f[n][j]) % ha;
    ans += (a * delta) % ha;
    if(ans >= ha) ans -= ha;
  }
  return ans;
}
 
int main() {
  int k; scanf("%d%d", &n, &k);
  if((n - k) & 1) {
    puts("0"); return 0;
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &A[i]);
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]);
  }
  printf("%lld\n", dp((n + k) / 2));
  return 0;
}