闲话
稻老师更新了！！！又是毒性十足的一曲！
稲葉曇『フロートプレイ』Vo. 歌愛ユキ
鬼面老师有几个肝啊（
【乐正绫AI】《世末歌者》——“我仍然在无人问津的阴雨霉湿之地”【原创PV付】
手动 at Keven_He（
我猜他今天大概是不会发博客了（
数学 \(1\)
感谢大自然的馈赠（合十）
Young SimPle Mate /jy
\(\text{y}\color{red}{\text{spm}}\)
\(\text{Young}\)
妙妙 DP。这玩意数学？我期待了一晚上的题就给整个这玩意？
设 \(f(n, m)\) 为最终所有可能情况的贡献和，最后除以 \(2^{nm}\) 就是答案了。
生成树的话考虑枚举一条边，我们可以根据第 \(m\) 位的 \(01\) 性将点分为 \(S,T\) 两个集合。其内部肯定形成生成树，然后找到一条最小的边链接二者即可。我们设 \(g(s, t, m)\) 表示当 \(|S| = s, |T| = t\)，边权 \(\in [0, 2^m)\) 时的最小边贡献之和，则可以通过枚举一侧点集的大小得到转移
\[f(n, m) = \sum_{i=0}^n \binom{n}{i} \left(2^{(n - i)(m - 1)} f(i, m - 1) + 2^{i(m - 1)} f(n - i, m - 1) + g(i, n - i, m - 1) + 2^{(n + 1)(m - 1)}\right) \]问题就来到了如何求得 \(g(s, t, m)\)。我们可以将边的贡献转化为贡献次数来求解 \(g\)。假设 \(p(s, t, m, k)\) 表示当 \(|S| = s, |T| = t\)，边权 \(\in [0, 2^m)\) 时的最小边 \(\ge k\) 的情况数，我们就有
\[g(s, t, m) = \sum_{i=0}^{2^m - 1} p(s, t, m, i) \]对于 \(p\)，我们可以通过与 \(f\) 类似的策略构造，通过将第 \(m\) 位分类讨论，得到 \(S_0, S_1, T_0, T_1\)，最后枚举 \(S, T\) 一侧点集的大小即可。也就是
\[p(s, t, m, k) = 2p(s, t, m-1, 0) + \sum_{i=0}^s \sum_{j=0}^t \binom {s}{i} \binom{t}{j} p(i, j, m - 1, k) p(s - i, t - j, m - 1, k) \]这里如果 \(k\) 最高位就是第 \(m - 1\) 位的话可以直接递归到 \(2p(s, t, m - 1, k - 2^{m-1})\)。
能否通过计数工业得到更优的复杂度？以及上面的都是贺题解，我根本没理解。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#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 eb emplace_back
#define pb pop_back
const int N = 1e6 + 10, mod = 258280327;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, m, bnd, pw2[N];
int qp(int a, int b) {
int ret = 1;
while (b) {
if (b & 1) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
} return ret;
}
int fac[N], inv[N];
int C(int n, int m) { return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod; }
int __p[52][52][9][1<<8|3];
int p(int s, int t, int m, int k) {
if (!s or !t or !m or !k) return pw2[(s + t) * m];
if (~__p[s][t][m][k]) return __p[s][t][m][k];
if ((k >> m - 1) & 1) return __p[s][t][m][k] = 2ll * p(s, t, m - 1, k ^ (1 << m - 1)) % mod;
int ret = 0;
rep(i,0,s) rep(j,0,t) if ((i and j) or (s - i and t - j))
ret = (ret + 1ll * C(s, i) * C(t, j) % mod * p(i, j, m - 1, k) % mod * p(s - i, t - j, m - 1, k)) % mod;
ret = (ret + 2ll * p(s, t, m - 1, 0)) % mod;
return __p[s][t][m][k] = ret;
}
int __g[52][52][9];
int g(int s, int t, int m) {
if (!s or !t or !m) return 0;
if (~__g[s][t][m]) return __g[s][t][m];
int ret = 0;
rep(k,1,(1<<m)-1) ret = (ret + p(s, t, m, k)) % mod;
return __g[s][t][m] = ret;
}
int __f[52][9];
int f(int n, int m) {
if (!m or n <= 1) return 0;
if (~__f[n][m]) return __f[n][m];
int ret = 0, tmp;
rep(i,0,n) {
tmp = 0;
if (i > 0) tmp = (tmp + 1ll * pw2[(n - i) * (m - 1)] * f(i, m - 1)) % mod;
if (n - i) tmp = (tmp + 1ll * pw2[i * (m - 1)] * f(n - i, m - 1)) % mod;
if (i > 0 and n - i > 0)
tmp = (tmp + pw2[(n + 1) * (m - 1)] + g(i, n - i, m - 1)) % mod;
ret = (ret + 1ll * tmp * C(n, i)) % mod;
} return __f[n][m] = ret ;
}
signed main() {
cin >> n >> m;
memset(__f, -1, sizeof __f);
memset(__g, -1, sizeof __g);
memset(__p, -1, sizeof __p);
pw2[0] = fac[0] = fac[1] = inv[0] = inv[1] = 1;
rep(i,1,(n + 1) * m) pw2[i] = 2ll * pw2[i - 1] % mod;
rep(i,2,n) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
rep(i,2,n) fac[i] = 1ll * fac[i - 1] * i % mod,
inv[i] = 1ll * inv[i - 1] * inv[i] % mod;
cout << 1ll * f(n, m) * qp(pw2[n * m], mod - 2) % mod << '\n';
timer;
}
\(\text{SimPle}\)
挺简单的一道计数。虽然最开始一直题意被读成了”存在 \(k\)”然后被卡了半小时（（
我们考虑一个数字如果有循环节那就肯定不行，而没有循环节的数字只能取字典序最小的位置，因此我们只需要统计没有循环节的数字的数量，除以 \(n\) 即可。抽象一下也就是 \(n\) 长度序列，值域 \([0, 9]\)，没有循环。
我们考虑一手容斥（最近咋一直都是容斥）。枚举一个循环段数 \(d|n\)，假设容斥系数为 \(f(d)\)。对于同一个长度为 \(n/d\) 的循环节，我们这里让他可以随意选择数字，可能性就是 \(10^{n / d}\) 的，这样拼起来就得到原序列的计数 \(\sum_{d|n} f(d) 10^{n / d}\)。
其实如果硬猜结论的话能直接冲一个 \(f(n) = \mu (n)\)，然后你发现这个结论是对的。
具体证明的话可以考虑递归子问题。也就是说，我们上面让他可以随便选数，因此还需要考虑子序列是否是一个循环的序列。从质数处开始归纳，能得到 \(f(n)\) 和 \(\mu(n)\) 是同构的。
不难写出答案
\[\begin{aligned} &\sum_{i=1}^n i \sum_{d|i} \mu(d)\times 10^{i / d} \\ = \ &\sum_{d=1} \mu(d)d \sum_{i=1}^{n/d} i\times 10^{i} \\ = \ &\sum_{d=1} \mu(d)d f(n / d) \end{aligned}\]其中 \(f(n) = \sum_{i=1}^n i\times 10^i\)。这个是好求的啊，我们直接构造 \(f\) 的 gf \(F\)，容易写出 \(F = \dfrac{x}{1-x} \left(\dfrac {1}{1 - 10x}\right)'\)。提取系数得到 \(f(n) = \dfrac{10}{81} (1 - 10^n + 9n 10^n)\)
光速幂以及构造杜教筛可以在 \(O(n^{2/3})\) 的复杂度内解决。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#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 eb emplace_back
#define pb pop_back
const int N = 1e6 + 10, mod = 258280327, L = 1e6;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
ll n;
struct light {
int p, sq, u[N], d[N];
ll m;
light(int p = 10, ll m = 1e10 + 5) : p(p), m(m) {
sq = sqrt(m);
u[0] = d[0] = 1;
rep(i,1,sq) d[i] = 1ll * d[i - 1] * p % mod;
rep(i,1,sq) u[i] = 1ll * u[i - 1] * d[sq] % mod;
}
int qp(ll x) {
return 1ll * u[x / sq] * d[x % sq] % mod;
}
} Lt;
int calc(ll x) { return 226393867ll * (1 + (9ll * x - 1) % mod * Lt.qp(x) % mod) % mod; }
int prime[N], cnt, mu[N];
bool vis[N];
void sieve(int bnd = L) {
mu[1] = 1;
rep(i,2,L) {
if (!vis[i]) mu[i] = mod - 1, prime[++ cnt] = i;
rep(j,1,cnt) {
if (i * prime[j] > L) break;
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
mu[i * prime[j]] = mod - mu[i];
}
}
rep(i,2,L) mu[i] = (1ll * mu[i] * i + mu[i - 1]) % mod;
}
int S(ll x) { x %= mod; return 1ll * x * (x + 1) / 2 % mod; }
unordered_map<ll, int> mp;
int muu(ll x) {
if (x <= L) return mu[x];
if (mp.count(x)) return mp[x];
int ret = 1;
for (ll l = 2, r; l <= x; l = r + 1) {
r = x / (x / l);
ret = (ret - 1ll * (S(r) - S(l - 1) + mod) * muu(x / l) % mod + mod) % mod;
} return mp[x] = ret;
}
signed main() {
cin >> n; sieve();
// cout << 226393867ll * 81 % mod << '\n';
int ret = 0;
for (ll l = 1, r = n; l <= n; l = r + 1) {
// cout << l << ' ' << r << endl;
r = n / (n / l);
ret = (ret + 1ll * (muu(r) - muu(l - 1) + mod) * calc(n / l)) % mod;
// cout << muu(r) - muu(l - 1) << ' ' << calc(n / l) << '\n';
} cout << ret << '\n';
// rep(i,1,5) cout << i << ' ' << calc(i) << '\n';
timer;
}
\(\text{Mate}\)
最开始脑子抽了，不会组合数取模了。然后场上就屈辱 40pts 暴力跑路了。
首先考虑一下式子是啥。挺简单的。首先 \(x, y\) 取一下绝对值。
我们分配 \(i\) 步给上下走的情况，然后可以上下/左右分开讨论，彼此同构。
上下的话假设分配 \(k\) 步向上走，则我们需要保证 \(k - (i - k) = x\)，也就是 \(k = \dfrac{i + x}{2}\)，这也要求 \(2|k\)。左右相同。于是我们就得到了答案
通过 CF896D 的手法，我们可以做到 \(O(n \log \text{mod})\) 的复杂度求解。
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#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 eb emplace_back
#define pb pop_back
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int infll = 0x3f3f3f3f3f3f3f3fll;
int n, mod, x, y, p[20], cnt, phi, ans;
int qp(int a, int b = phi - 1) {
int ret = 1;
while (b) {
if (b & 1) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
} return ret;
}
struct light {
int p, sq, u[1005], d[1005], m;
void init(int _p, int _m) {
p = _p, m = _m;
sq = sqrt(m);
u[0] = d[0] = 1;
rep(i,1,sq) d[i] = 1ll * d[i - 1] * p % mod;
rep(i,1,sq) u[i] = 1ll * u[i - 1] * d[sq] % mod;
}
int qp(int x) {
return 1ll * u[x / sq] * d[x % sq] % mod;
}
} Lt[20];
struct Int {
int x, c[15];
Int() { }
Int(const int& v) {
x = v; memset(c, 0, sizeof c);
rep(i,1,cnt) while (x % p[i] == 0)
++ c[i], x /= p[i];
}
Int& operator= (const int& v) {
x = v; memset(c, 0, sizeof c);
rep(i,1,cnt) while (x % p[i] == 0)
++ c[i], x /= p[i];
return *this;
}
int value() {
int ret = x;
rep(i,1,cnt) ret = 1ll * ret * Lt[i].qp(c[i]) % mod;
return ret;
}
Int operator* (const Int& b) const {
Int ret; ret.x = 1ll * x * b.x % mod;
rep(i,1,cnt) ret.c[i] = c[i] + b.c[i];
return ret;
}
Int operator/ (const Int& b) const {
Int ret; ret.x = 1ll * x * qp(b.x) % mod;
rep(i,1,cnt) ret.c[i] = c[i] - b.c[i];
return ret;
}
} fac[N];
signed main() {
file(mate);
cin >> n >> mod >> x >> y;
x = abs(x), y = abs(y);
if ((n + y + x) & 1) puts("0"), exit(0);
int tmp = mod; phi = mod;
for (int i = 2; i * i <= tmp; ++ i) if (tmp % i == 0) {
phi = phi / i * (i - 1); p[++ cnt] = i;
while (tmp % i == 0) tmp /= i;
} if (tmp > 1) phi = phi / tmp * (tmp - 1), p[++ cnt] = tmp;
rep(i,1,cnt) Lt[i].init(p[i], 1000000);
fac[0] = 1;
rep(i,1,n) fac[i] = fac[i - 1] * Int(i);
for (int i = 0, j, k, l; i <= n; ++ i) {
if (i + (j = i + x) + y > n) break;
if (n - (i + j) - y & 1) continue;
k = (n - (i + j) - y) >> 1, l = k + y;
ans = (ans + (fac[n] / (fac[i] * fac[j] * fac[k] * fac[l])).value()) % mod;
} cout << ans << '\n';
}