闲话
发现洲阁筛可以取到所有 \(\left\lfloor\frac nx\right\rfloor\) 的值。于是打算去学学。
不知道今天下午还能不能切题 但是先发了再说（
如果有想写的会及时更新的（但一直都是这么做的
杂题
有 \(2n\) 张卡牌与 \(n\) 个盒子。卡牌被编号为 \(1\) 至 \(2n\)，盒子被编号为 \(1\) 至 \(n\)。每个盒子里放着两张卡牌：第 \(i\) 个盒子里放着编号为 \(a_i\) 和 \(b_i\) 的卡牌。
找到满足下述条件的排列盒子的方案数：
- 考虑通过以下的方式取得长为 \(2n\) 的卡牌序列：从左到右考虑每个盒子，从其中拿出两张卡牌，以任意方式放置于当前序列尾。条件即为所得到的序列 \(P_1,P_2,\cdots,P_{2n}\) 有 \(n-1\) 个峰。
一个长为 \(n\) 的序列 \(p = \{p_1, p_2,\cdots,p_n\}\) 的其中一个峰为整数 \(1 <i<n\)，满足 \(p_{i-1} < p_i\) 且 \(p_i < p_{i + 1}\)。
答案对 \(10^9 + 7\) 取模。
\(n\le 2\times 10^5,\ 1\le A_i,B_i\le 2n\)。
这越级做题就很寄
我们记盒子 \(i\) 为 \((a_i, b_i)\)。不妨令 \(a_i < b_i\)。
由于我们需要让峰取到 \(n -1\) 个，观察可得合法方案一定形如以下两种可能中的一种：
- \((a,b), \cdots , (a,b),(a,b),\cdots, (a,b)\)
- \((a,b), \cdots , (a,b),(b,a),\cdots, (b,a)\)
其中 \(1.\) 情况无法取到最后一个 \(b\)，\(2.\) 情况无法取到两个挨着的 \(b\)。任意其余的构造方案都只能得到小于 \(b\) 个的峰。
首先考虑 \(1.\) 情况的计数。我们按 \(b\) 降序的顺序将每个盒子插入当前序列，在过程中计数。我们记 \(c_i = \sum_{j=1}^n[a_j <b_i]\)。容易发现每个盒子能插入的位置要么是结尾，要么是满足 \(a_k < b_i\) 的盒子 \(k\) 前面。因此这种情况有答案 \(\prod_{i=1}^n (c_i + 1)\)。
然后考虑 \(2.\) 情况的计数。我们考虑固定第一个 \((b,a)\) 出现的位置。假设在该位置出现的两个值为 \((p_{i},p_{i+1})\)，则在前半段形如 \((a,b)\) 的元素无法插入结尾，而大于 \(p_{i+1}\) 的元素既可以插入在后半段的开头，也可以插入在结尾。剩余部分由与上面类似的讨论，有这种情况的答案 \(\prod_{j=1}^{p_i-1}c_j \times \prod_{j=p_i+1}^{p_{i+1}-1}(c_j+1)\times \prod_{j = p_{i+1}+1}^n(c_j+2)\)。
利用树状数组可以做到 \(O(n\log n)\)。使用桶扫描计数并统计前后缀和可以做到 \(O(n)\).
code
#include <bits/stdc++.h>
using namespace std; using pii = pair<int,int>; using vi = vector<int>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> T rand(T l, T r) { return uniform_int_distribution<T>(l, r)(rnd); }
template <typename T> void get(T & x) {
x = 0; char ch = getchar(); bool f = false; while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x);
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
template <typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
template <typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define ufile(x)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define Aster(i, s) for (int i = head[s], v; i; i = e[i].next)
#define all(s) s.begin(), s.end()
#define eb emplace_back
#define pb pop_back
#define em emplace
const int N = 4e5 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
// int mod;
// const int mod = 10007;
// const int mod = 469762049, g = 3;
// const int mod = 998244353; // const int g = 3;
// const int mod = 1004535809, g = 3;
const int mod = 1e9 + 7;
// const int mod = 1e9 + 9;
// const int mod = 1e9 + 3579, bse = 131;
/* add / sub */ template <typename T1, typename T2> T1 add(T1 a, T2 b) { return (a += b) >= mod ? a - mod : a; } template <typename T1, typename ...Args> T1 add(T1 a, Args ... b) { return add(a, add(b...)); } template <typename T1, typename T2> T1 sub(T1 a, T2 b) { return (a -= b) < 0 ? a + mod : a; } template <typename T1, typename ...Args> T1 sub(T1 a, Args ... b) { return add(a, add(b...)); } template <typename T1, typename T2> void addi(T1 & a, T2 b) { (a += b) >= mod ? (a -= mod) : true; } template <typename T1, typename ...Args> void addi(T1 & a, Args ...b) { addi(a, add(b...)); } template <typename T1, typename T2> void subi(T1 & a, T2 b) { (a -= b) < 0 ? (a += mod) : true; } template <typename T1, typename ...Args> void subi(T1 & a, Args ...b) { subi(a, add(b...)); }
/* Fastmod / mul */ struct FastMod { int m; ll b; void init(int _m) { m = _m; if (m == 0) m = 1; b = ((lll)1<<64) / m; } FastMod(int _m) { init(_m); } int operator() (ll a) {ll q = ((lll)a * b) >> 64; a -= q * m; if (a >= m) a -= m; return a; } } Mod(mod); int mul(int a, int b) { return Mod(1ll * a * b); } template <typename T1, typename T2> int mul(T1 a, T2 b) { return Mod((long long)(1ll * a * b)); } template <typename T, typename ...Args> int mul(T a, Args ...b) { return mul(a, mul(b...)); } template <typename T1, typename T2> void muli(T1 & a, T2 b) { a = Mod(1ll * a * b); } template <typename T1, typename ...Args> void muli(T1 & a, Args ...b) { muli(a, mul(b ...)); } // /* trivial multiple function(idk whether its useful*/ int mul(int a, int b) { return 1ll * a * b % mod; } template <typename T1, typename T2> int mul(T1 a, T2 b) { return (long long)(1ll * a * b) % mod; } template <typename T, typename ...Args> int mul(T a, Args ...b) { return mul(a, mul(b...)); }
/* qp init C */ template <typename T1, typename T2> T1 qp(T1 a, T2 b) { T1 ret = 1; for (; b > 0; a = mul(a, a), b >>= 1) if (b & 1) ret = mul(ret, a); return ret; } int fac[N], inv[N], ifac[N]; template<typename T1> void init_fac(T1 bnd, int mask = 0b111) { if ((mask >> 2) & 1) { static int __var_fac_bnd; if (__var_fac_bnd == 0) fac[0] = fac[1] = __var_fac_bnd = 1; rep(i, __var_fac_bnd + 1, bnd) fac[i] = mul(fac[i - 1], i); __var_fac_bnd = bnd; } if ((mask >> 1) & 1) { static int __var_inv_bnd; if (__var_inv_bnd == 0) inv[0] = inv[1] = __var_inv_bnd = 1; rep(i, __var_inv_bnd + 1, bnd) inv[i] = mul(mod - mod / i, inv[mod % i]); __var_inv_bnd = bnd; } if ((mask >> 0) & 1) { static int __var_ifac_bnd, __var_inv_bnd; if (__var_ifac_bnd == 0) ifac[0] = ifac[1] = __var_ifac_bnd = 1; if (__var_inv_bnd < bnd) init_fac(bnd, 0b010); rep(i, __var_ifac_bnd + 1, bnd) ifac[i] = mul(ifac[i - 1], inv[i]); __var_ifac_bnd = bnd; } } template<typename T1, typename T2> int C(T1 n, T2 m) { if (n < m or m == 0) return 1; init_fac(max(n, m)); return mul(fac[n], ifac[m], ifac[n - m]); }
/* inv 2/3/6 / phi */ constexpr int __var_pow(int a, int b) { int ret = 1; for (; b > 0; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ret = 1ll * ret * a % mod; return ret; } constexpr int __var_phi(int x) { if (x <= 2) return 1; int ret = x; for (int i = 2; 1ll * i * i <= x; ++i) if (x % i == 0) { ret = ret / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) ret = ret / x * (x - 1); return ret; } const int __phi_mod = __var_phi(mod); const int inv2 = __var_pow(2, __phi_mod - 1), inv3 = __var_pow(3, __phi_mod - 1), inv6 = __var_pow(6, __phi_mod - 1); constexpr int __var_check() { assert( 1ll * 2 * inv2 % mod == 1 ); assert( 1ll * 3 * inv3 % mod == 1 ); assert( 1ll * 6 * inv6 % mod == 1 ); return (unsigned int)(-1); } const int __var_dummy = __var_check();
int n, ans = 1, cnt[N], f[N], g[N], h[N];
pii a[N];
struct BIT {
int Index[N];
void add(int p, int v) { for (; p <= (n << 1); p += p & -p) addi(Index[p], v); }
int qry(int p) { int ret = 0; for (; p; p ^= p & -p) addi(ret, Index[p]); return ret; }
};
signed main() {
cin >> n; init_fac(n << 1 | 3, 0b010);
rep(i, 1, n) cin >> a[i].first >> a[i].second, (a[i].first > a[i].second) && (swap(a[i].first, a[i].second), true);
sort(a + 1, a + 1 + n, [](pii a, pii b) { return a.second < b.second; });
static BIT B; pre(i,n,1) cnt[i] = B.qry(a[i].second), B.add(a[i].first, 1);
f[0] = g[0] = h[n + 1] = 1; f[0] = inv[cnt[1] + 1];
rep(i,1,n) f[i] = mul(f[i - 1], cnt[i], inv[cnt[i + 1] + 1]);
rep(i,1,n) g[i] = mul(g[i - 1], cnt[i] + 1);
pre(i,n,1) h[i] = mul(h[i + 1], cnt[i] + 2);
rep(i,1,n) ans = mul(ans, cnt[i] + 1);
static BIT T; rep(i,1,n) ans = add(ans, mul(T.qry(a[i].first), g[i - 1], h[i + 1])), T.add(a[i].second, f[i - 1]);
cout << ans << '\n';
}
\[\begin{aligned} & \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n [\left(j\mid i\right) \land\left( (j + k)\mid i\right)] \\ = \ & \sum_{i=1}^n\sum_{j=1}^n\sum_{k=j+1}^{2n} [\left(j\mid i\right) \land\left(k\mid i\right)] \\ = \ & \sum_{i=1}^n\sum_{j=1}^i\sum_{k=j+1}^{i} [\left(j\mid i\right) \land\left(k\mid i\right)] \end{aligned}\]给定 \(n\)。求
\[\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n [\left(j\mid i\right) \land\left( (j + k)\mid i\right)] \]\(n\le 10^{10}\)。
可以看到后面两个 \(\text{\sum}\) 其实就是选了两个 \(i\) 的因子。因此考虑组合意义，我们有
\[\begin{aligned} & \sum_{i=1}^n\sum_{j=1}^i\sum_{k=j+1}^{i} [\left(j\mid i\right) \land\left(k\mid i\right)] \\ = \ & \sum_{i=1}^n\binom{d(i)}2 \\ = \ & \frac 12 \left( \sum_{i=1}^nd^2(i) - \sum_{i=1}^nd(i)\right) \end{aligned}\]后面的部分可以 \(O(\sqrt n)\)。前面的部分可以 Min_25 筛，设完全积性函数为 \(\text I\)， \(d^2(p^k) = (k+1)^2\)。
于是总时间复杂度 \(O(\sqrt n + \frac{n^{\frac 34}}{\log n})\)。
code
#include <bits/stdc++.h>
#define int long long
using namespace std; using pii = pair<int,int>; using vi = vector<int>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> T rand(T l, T r) { return uniform_int_distribution<T>(l, r)(rnd); }
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
template <typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
template <typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
#define fsqrt(x) (__builtin_sqrtf(x))
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define ufile(x)
#define rep(i,s,t) for (int i(s), i##_((t) + 1); i < i##_; ++ i)
#define pre(i,s,t) for (int i(s), i##_((t) - 1); i > i##_; -- i)
#define mbl(s,t) for (int l(s),r(t/(t/s)),i##_((t)+1);l<i##_;l=r+1,r=(t)/(((t)/l)+((t)/l==0)))
#define Aster(i, s) for (int i = head[s], v; i; i = e[i].next)
#define all(s) s.begin(), s.end()
#define eb emplace_back
#define pb pop_back
#define em emplace
const int N = 4e5 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
// int mod;
// const int mod = 10007;
// const int mod = 469762049, g = 3;
const int mod = 998244353; // const int g = 3;
// const int mod = 1004535809, g = 3;
// const int mod = 1e9 + 7;
// const int mod = 1e9 + 9;
// const int mod = 1e9 + 3579, bse = 131;
/* add / sub */ template <typename T1, typename T2> T1 add(T1 a, T2 b) { return (a += b) >= mod ? a - mod : a; } template <typename T1, typename ...Args> T1 add(T1 a, Args ... b) { return add(a, add(b...)); } template <typename T1, typename T2> T1 sub(T1 a, T2 b) { return (a -= b) < 0 ? a + mod : a; } template <typename T1, typename ...Args> T1 sub(T1 a, Args ... b) { return add(a, add(b...)); } template <typename T1, typename T2> void addi(T1 & a, T2 b) { (a += b) >= mod ? (a -= mod) : true; } template <typename T1, typename ...Args> void addi(T1 & a, Args ...b) { addi(a, add(b...)); } template <typename T1, typename T2> void subi(T1 & a, T2 b) { (a -= b) < 0 ? (a += mod) : true; } template <typename T1, typename ...Args> void subi(T1 & a, Args ...b) { subi(a, add(b...)); }
/* Fastmod / mul */ struct FastMod { int m; ll b; void init(int _m) { m = _m; if (m == 0) m = 1; b = ((lll)1<<64) / m; } FastMod(int _m) { init(_m); } int operator() (ll a) {ll q = ((lll)a * b) >> 64; a -= q * m; if (a >= m) a -= m; return a; } } Mod(mod); int mul(int a, int b) { return Mod(1ll * a * b); } template <typename T1, typename T2> int mul(T1 a, T2 b) { return Mod((long long)(1ll * a * b)); } template <typename T, typename ...Args> int mul(T a, Args ...b) { return mul(a, mul(b...)); } template <typename T1, typename T2> void muli(T1 & a, T2 b) { a = Mod(1ll * a * b); } template <typename T1, typename ...Args> void muli(T1 & a, Args ...b) { muli(a, mul(b ...)); } // /* trivial multiple function(idk whether its useful*/ int mul(int a, int b) { return 1ll * a * b % mod; } template <typename T1, typename T2> int mul(T1 a, T2 b) { return (long long)(1ll * a * b) % mod; } template <typename T, typename ...Args> int mul(T a, Args ...b) { return mul(a, mul(b...)); }
/* qp init C */ template <typename T1, typename T2> T1 qp(T1 a, T2 b) { T1 ret = 1; for (; b > 0; a = mul(a, a), b >>= 1) if (b & 1) ret = mul(ret, a); return ret; } int fac[N], inv[N], ifac[N]; template<typename T1> void init_fac(T1 bnd, int mask = 0b111) { if ((mask >> 2) & 1) { static int __var_fac_bnd; if (__var_fac_bnd == 0) fac[0] = fac[1] = __var_fac_bnd = 1; rep(i, __var_fac_bnd + 1, bnd) fac[i] = mul(fac[i - 1], i); __var_fac_bnd = bnd; } if ((mask >> 1) & 1) { static int __var_inv_bnd; if (__var_inv_bnd == 0) inv[0] = inv[1] = __var_inv_bnd = 1; rep(i, __var_inv_bnd + 1, bnd) inv[i] = mul(mod - mod / i, inv[mod % i]); __var_inv_bnd = bnd; } if ((mask >> 0) & 1) { static int __var_ifac_bnd, __var_inv_bnd; if (__var_ifac_bnd == 0) ifac[0] = ifac[1] = __var_ifac_bnd = 1; if (__var_inv_bnd < bnd) init_fac(bnd, 0b010); rep(i, __var_ifac_bnd + 1, bnd) ifac[i] = mul(ifac[i - 1], inv[i]); __var_ifac_bnd = bnd; } } template<typename T1, typename T2> int C(T1 n, T2 m) { if (n < m or m == 0) return 1; init_fac(max(n, m)); return mul(fac[n], ifac[m], ifac[n - m]); }
/* inv 2/3/6 / phi */ constexpr int __var_pow(int a, int b) { int ret = 1; for (; b > 0; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ret = 1ll * ret * a % mod; return ret; } constexpr int __var_phi(int x) { if (x <= 2) return 1; int ret = x; for (int i = 2; 1ll * i * i <= x; ++i) if (x % i == 0) { ret = ret / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) ret = ret / x * (x - 1); return ret; } const int __phi_mod = __var_phi(mod); const int inv2 = __var_pow(2, __phi_mod - 1), inv3 = __var_pow(3, __phi_mod - 1), inv6 = __var_pow(6, __phi_mod - 1); constexpr int __var_check() { assert( 1ll * 2 * inv2 % mod == 1 ); assert( 1ll * 3 * inv3 % mod == 1 ); assert( 1ll * 6 * inv6 % mod == 1 ); return 1; } array<int,__var_check()> __var_dummy;
ll n, v[N];
int sq, ans, id1[N], id2[N], m, g[N];
int prime[N], cnt; bool vis[N];
int get(ll p) { return p < sq ? id1[p] : id2[n / p]; }
void sieve(int b) {
rep(i,2,b) {
if (!vis[i]) prime[++cnt] = i;
rep(j,1,cnt) {
if (i * prime[j] > b) break;
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
int S(ll x, int y) {
if (prime[y] >= x) return 0;
int ret = sub(g[get(x)], g[get(prime[y])]);
rep(i,y+1,cnt) {
if (1ll * prime[i] * prime[i] > x) break;
for (ll w = prime[i], c = 1; w <= x; w *= prime[i], ++ c) {
ret = add(ret, mul(S(x / w, i) + (c > 1), c + 1, c + 1));
}
} return ret;
}
signed main() {
cin >> n; sq = fsqrt(n);
sieve(sq);
mbl(1, n) {
ans = sub(ans, mul(Mod(r - l + 1), Mod(n / l)));
v[++ m] = n / l;
if (v[m] < sq) id1[v[m]] = m;
else id2[n / v[m]] = m;
g[m] = mul(4, Mod(v[m] - 1));
}
rep(i,1,cnt) rep(j,1,m){
if (1ll * prime[i] * prime[i] > v[j]) break;
g[j] = sub(g[j], sub(g[get(v[j] / prime[i])], g[get(prime[i - 1])]));
}
cout << mul(inv2, add(ans, S(n, 0), 1));
}