2024.03.01 ~ 2024.03.08
2024.03.13
Codeforces - 1278F
做完了之后翻了翻题解，发现做法都比较复杂，其实有更简单的做法如下。
考虑一个关于第二类斯特林数的等式：
\[x^k=\sum_{i=0}^{k}S_2(k, i)\cdot {x\choose i}\cdot i! \]因为除开系数之后全是和式，因此可以直接变成期望：
\[\begin{aligned} E[x^k]&=E[\sum_{i=0}^{k}S_2(k, i)\cdot {x\choose i}\cdot i!] \\ &=\sum_{i=0}^kS_2(k,i)\cdot E[{x\choose i}]\cdot i! \end{aligned} \]考虑：
\[E[{x\choose i}]=\sum_{p_1<p_2<\cdots<p_i}\prod_jP[A_{p_j}] \]其中 \(A_j\) 表示第 \(j\) 次洗牌时满足题目要求的事件，显然 \(P[A_j]=\frac{1}{m}\)。
上述式子考虑组合意义可以轻松地变成：
\[E[{x\choose i}]={n\choose i}\frac{1}{m^i} \]因此有：
\[\begin{aligned} E[x^k]&=\sum_{i=0}^kS_2(k,i)\cdot E[{x\choose i}]\cdot i! \\ &= \sum_{i=0}^k S_2(k,i)\cdot {n\choose i}\cdot \frac{i!}{m^i} \end{aligned} \]然后可以 \(O(k)\) 求值。第二类斯特林数递推求值是 \(O(k^2)\) 的。
总时间复杂度 \(O(k^2)\)。
2024.03.18
Codeforces - 578F Mirror Box
很好的题目，爱来自矩阵数定理。
结论是满足限制当且仅当网格上 \(x+y\) 为奇数的点构成生成树或偶数点构成生成树。
Submission #252017022 - Codeforces
Luogu - P4022 [CTSC2012] 熟悉的文章
很套路的题目，爱来自 SAM。
对每个标准作文，中间夹上特殊字符放在一个 SAM 中。
对于每个待检查作文，在每个串的每个位置上计算以这个串结尾时往前最长能在标准作文库中匹配多少长度。
然后二分，单调队列 DP 即可。
// Not afraid to dark.
#include <bits/stdc++.h>
using namespace std;
clock_t start_time, end_time;
#define GET_START start_time = clock ();
#define GET_END end_time = clock (); fprintf (stderr, "TIME COSSEMED : %0.3lf\n", 1.0 * (end_time - start_time) / CLOCKS_PER_SEC);
#define int long long
namespace io {
// io : read , write
}
const int N = 1e6, mod = 1e9 + 7;
int n, m, k, f[N + 5], g[N + 5], ans;
__inline__ __attribute__ ((always_inline)) int power (int a, int p){
int res = 1;
while (p > 0){
if (p & 1)
res = res * a % mod;
a = a * a % mod;
p >>= 1;
}
return res;
}
signed main (){
GET_START
io::read (n), io::read (m), io::read (k);
if (k == 1)
io::write (power (m, n)), puts ("");
else {
f[0] = 1;
for (int i = 1;i <= n;++ i){
f[i] = (g[i - 1] - g[max (0ll, i - k)] + mod) * (m - 1) % mod;
if (i < k)
f[i] = (f[i] + m) % mod;
g[i] = (g[i - 1] + f[i]) % mod;
}
int iv = power (m, mod - 2);
for (int i = 1, pw = power (m, n - k);i <= n - k + 1;++ i, pw = pw * iv % mod)
ans = (ans + f[i - 1] * (m - 1 + (i == 1)) % mod * pw % mod) % mod;
io::write (ans), puts ("");
}
GET_END
return 0;
}
2024.03.25
hackearth - Perfect Permutations
巧妙的题目，爱来自 欧拉五边形数定理。
// Not afraid to dark.
#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace io {
// io : read , write
}
const int K = 1e5, mod = 1e9 + 7;
int n, k;
int inv[K + 5], inj[K + 5], jc[K + 5];
int ans;
__inline__ __attribute__ ((always_inline)) int pentagonal (int x, int delta){
return x * (3 * x + delta) / 2;
}
__inline__ __attribute__ ((always_inline)) int C (int x){
return jc[x] * inj[x] % mod;
}
__inline__ __attribute__ ((always_inline)) char Calc (int x, int delta){
int frm = k - pentagonal (x, delta), res;
if (frm < 0)
return 0;
res = C (frm);
if (x & 1)
res = mod - res;
ans = (ans + res) % mod;
return 1;
}
signed main (){
for (int T = io::read ();T --;){
io::read (n), io::read (k);
inj[0] = inj[1] = inv[1] = jc[0] = 1;
jc[1] = n;
for (int i = 2;i <= k;++ i){
inv[i] = inv[i - mod % i] * (mod / i + 1) % mod;
inj[i] = inj[i - 1] * inv[i] % mod;
jc[i] = jc[i - 1] * (n - 1 + i) % mod;
}
ans = C (k);
for (int i = 1, frm;i <= k;++ i)
if (! (Calc (i, 1) | Calc (i, - 1)))
break;
io::write (ans), puts ("");
}
return 0;
}