整除分块 + 莫比乌斯函数,点分树 + 可持久化可并堆,多项式(拉格朗日插值)+ dp
# A. 《如何优雅地送分》
考场上只会 30pts /kk
题目要求 , 为 的不同的质因子个数。
然后就是喜闻乐见的推式子:
. 可以使用整除分块快速计算,总复杂度
#include <bits/stdc++.h> | |
#define int long long | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0; | |
char ch = getchar(); | |
while(!isdigit(ch)) ch = getchar(); | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x; | |
} | |
template <typename T> inline void write(T x){ | |
if(x < 0) putchar('-'), x = -x; | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 1e6 + 10; | |
const int mod = 1e9 + 7; | |
int n, ans; | |
int mu[N], p[N], tot; | |
bool vis[N]; | |
inline void euler(int n){ | |
mu[1] = 1; | |
for(int i = 2; i <= n; ++i){ | |
if(!vis[i]) mu[i] = -1, p[++tot] = i; | |
for(int j = 1; j <= tot && i * p[j] <= n; ++j){ | |
vis[i * p[j]] = 1; | |
if(i % p[j] != 0) mu[i * p[j]] = -mu[i]; | |
else {mu[i * p[j]] = 0; break;} | |
} | |
} | |
} | |
inline int calc(int n){ | |
int res = 0; | |
for(int l = 1, r; l <= n; l = r + 1){ | |
r = n / (n / l); | |
res = (res + (r - l + 1) * (n / l) % mod) % mod; | |
} | |
return res; | |
} | |
signed main(){ | |
n = read(); | |
euler(sqrt(n)); | |
for(int i = 1; i * i <= n; ++i) ans = (ans + mu[i] * calc(n / i / i) % mod + mod) % mod; | |
write(ans), puts(""); | |
return 0; | |
} | |
// X.K. |
# B. 《阴阳》
阴阳题。
可持久化点分树,然而思路太过神仙,std 也太过神仙,咕咕咕。
暴力 维护可得 60pts 的好成绩。
# C. 《你猜是不是找规律》
正解:打表找规律
好吧确实是要打个表找找规律的,可以找出 的递推式,设 表示长度为 的排列,恰好交换 次能使之有序的排列数:
感性理解一下, 是关于 的 次多项式,然后拉插一下即可(
这里讲一下 神仙的神仙做法。
从一个乱序排列变成有序排列里面有许多置换环。
如果一个置换环的长度为 ,那么我们需要 次交换来使这个环上的数都到它应该在的位置。
此时我们有 个环,那么总点数为 ,从 里面任意选 个数,就是 。
然后我们要把这 个数变成有序的,需要再乘上 。
需要注意的一点:我们找的置换环长度必须严格大于 1,所以转移略有不同,具体来说,把 这一项改为 。
也就是从前 个数中招至少 2 个数放到第 个环里,有 种选择。
#include <bits/stdc++.h> | |
#define ll long long | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0; | |
char ch = getchar(); | |
while(!isdigit(ch)) ch = getchar(); | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x; | |
} | |
template <typename T> inline void write(T x){ | |
if(x < 0) putchar('-'), x = -x; | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 3e3 + 10; | |
const int mod = 1e9 + 7; | |
int n, k; | |
inline int qpow(int a, int b){ | |
int res = 1; | |
while(b){ | |
if(b & 1) res = 1ll * res * a % mod; | |
a = 1ll * a * a % mod, b >>= 1; | |
} | |
return res; | |
} | |
int s[N << 1][N], f[N << 1], ifac[N << 1]; | |
signed main(){ | |
n = read(), k = read(); | |
s[0][0] = 1; | |
for(int i = 2; i <= 2 * k; ++i) | |
for(int j = 1; j <= k; ++j) | |
s[i][j] = (1ll * (i - 1) * s[i - 1][j] % mod + 1ll * (i - 1) * s[i - 2][j - 1] % mod) % mod; | |
f[1] = n, ifac[0] = ifac[1] = 1; | |
for(int i = 2; i <= 2 * k; ++i) | |
f[i] = 1ll * f[i - 1] * (n - i + 1) % mod, ifac[i] = 1ll * ifac[i - 1] * qpow(i, mod - 2) % mod; | |
int res = 1; | |
for(int i = 1; i <= k; ++i) | |
for(int j = 1; j <= k; ++j) | |
res = (res + 1ll * f[i + j] * ifac[i + j] % mod * s[i + j][i] % mod) % mod; | |
write(res), puts(""); | |
return 0; | |
} | |
// X.K. | |
// s[1][0] = 1; | |
// for(int i = 1; i <= n; ++i) s[i][0] = 1; | |
// for(int i = 2; i <= n; ++i) | |
// for(int j = 1; j < i; ++j) | |
// s[i][j] = ((i - 1) * s[i - 1][j - 1] % mod + s[i - 1][j]) % mod; | |
// int ans = 0; | |
// for(int i = 0; i <= k; ++i) ans = (ans + s[n][i]) % mod; | |
// write(ans), puts(""); | |
// return 0; |