[CF 900F]Unusual Sequence
求有多少正整数序列,满足所有数的最大公约数为\(x\),所有数的和为\(y\)。
\(1\leq x, y\leq 10^9\)。
[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 3622]已经没有什么好害怕的了
已经……没有什么好害怕的了
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; }