|
更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19638913 $\newcommand{\binom}[2]{{#1 \choose #2}}$ 大意 求$\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p$的值。其中 $n$, $x$, $p$ 为给定的整数，$f(k)$ 为给定的一个 $m$ 次多项式 $f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m$。$\binom{n}{k}$ 为组合数，其值为 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$。
思路 好题！ 我们先考虑这个式子的暴力处理方式，我们发现是外层枚举 $k$，内层枚举 $f(k)$ 的k $k$，这样是 $\mathcal{O}(nm)$ 的，但是我们发现 $1 \le n \le 10 ^ 9$，但是我们的 $m$ 是 $1 \le m \le 10 ^ 3$ 的，我们首先考虑的是把复杂度中的 $n$ 化为用 $m$ 的复杂度能解决的事情。 我们发现原始的式子中，只有 $f(k)$ 是需要我们额外处理的，所以我们先看这个东西，我们考虑化简，这个时候需要用到 $k$ 次下降幂的东西，众所周知 $x ^ k = x \times x \times \ldots $，那么我们的 $x ^ {\underline{k}} = x(x - 1)(x - k + 1)$，为什么我们需要知道这个东西呢？因为我们发现 $f(k)$ 中的 $k ^ j$ 无法很好的运算，我们考虑幂的转化，即利用**第二类斯特林数**将 $x ^ k \to x ^ {\underline{k}}$，如何做呢？我们有这样的恒等式：$k ^ i = \sum_{j = 0}^{i} {i \brace j} k ^ {\underline{j}}$。 那这个时候就有人要问了，主播主播什么是**第二类斯特林数**？我们考虑组合意义，是这样的： ${i \brace j}$ 表示将 $i$ 个互不相同的球放到 $j$ 个相同的盒子里（每个盒子都不为空）的方案数。那递推式就是：${i \brace j} = {i - 1 \brace j - 1} + j \times {i - 1 \brace j}$，那这个式子我们可以用组合的方式去理解一下，就是左边的 ${i - 1 \brace j - 1}$ 就是开一个新的盒子，而右边的 $j \times {i - 1 \brace j}$ 就是用旧的盒子。 好，回到正题，我们考虑将原始的 $f(k)$ 优化代换一下，用 $k ^ {\underline{j}}$ 替代 $k ^ j$，这样的话前面会产生一个新的系数，我们将这个系数记为 $b_j$，那么 $b_j = \sum_{i = 1}^{m} a_i \times {i \brace j}$。那么我们将这个 $b_j$ 带入原式，那么我们的式子就变成了这样~~一坨~~：$\sum_{k = 0} ^ {n} (\sum_{j = 0} ^ {m} b_j k ^ {\underline{j}}) x ^ k \binom{n}{k}$ 接下来，我们先交换 $k$ 与 $j$ 的枚举顺序：$\sum_{j = 0} ^ {m} b_j (\sum_{k = 0} ^ {n} k ^ {\underline{j}} x ^ k \binom{n}{k})$
接下来我我们利用**吸收公式**的 $k$ 次下降幂的形式：$k ^ {\underline{j} \binom{n}{k}} = n ^ {\un 该题解待审........................................................................(剩余 1831 个中英字符)
题目3418 [统一省选 2020]组合数问题
AAAAAAAAAAAAAAAAAAAA
2026-02-25 21:59:51
|
|
|
更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19638717
大意 给定两个点 $a$ 和 $b$，首先对于 $a$ 到 $b$ 路径上的所有点 $x$（包含 $a$ 和 $b$），你要将与 $x$ 相连的所有边变为轻边。然后再将 $a$ 到 $b$ 路径上包含的所有边变为重边。 给定两个点 $a$ 和 $b$，你需要计算当前 $a$ 到 $b$ 的路径上一共包含多少条重边。
思路 我们考虑一个小巧思。 我们将问题可以转化为将 $a \to b$ 这条路径的点染上独一无二的颜色，最终求 $a \to b$ 路径上的重边即为两端颜色相同的边的数量。 因为每次我们选的颜色都不一样，这样操作一定能够让我们通过只记录端点的颜色去统计这个值，我们通过直接维护区间的左右的端点的颜色和相邻重色的个数，我们如果区间的端点颜色重合就可以将这个答案继续累加。这个就是处理本题线段树的方式。 但是对于这个题目是在树上的操作，那就没什么说的了，直接树剖维护即可。但是如果你像我一样闲着没事的话可以用 LCT 维护，原因是这个更改 $a \to b$ 路径的过程可以用 LCT 的 split 操作非常简便的完成。至于 LCT 里面维护的内容，和线段树几乎一样，剩下就没什么了。
代码
#include<iostream>
#include<algorithm>
using namespace std;
#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa
const int MAXN = 1e5 + 5;
struct node{
int ch[2], fa;
int col, tag;
int lc, rc;
int cnt;
int sz;
bool rev;
node(){
ch[1] = ch[0] = fa = 0;
col = tag = lc = rc = cnt = sz = 0;
rev = false;
}
}t[MAXN];
bool isroot(int x){
return (lc(fa(x)) != x) && (rc(fa(x)) != x);
}
void pushup(int x) {
t[x].sz = t[lc(x)].sz + t[rc(x)].sz + 1;
t[x].cnt = t[lc(x)].cnt + t[rc(x)].cnt;
t[x].lc = lc(x) ? t[lc(x)].lc : t[x].col;
t[x].rc = rc(x) ? t[rc(x)].rc : t[x].col;
if(lc(x) && t[lc(x)].rc == t[x].col) t[x].cnt ++;
if(rc(x) && t[rc(x)].lc == t[x].col) t[x].cnt ++;
}
void update_rev(int x){
if(!x) return;
swap(lc(x), rc(x));
swap(t[x].lc, t[x].rc);
t[x].rev ^= 1;
}
void apply_col(int x, int c){
if(!x) return;
t[x].col = t[x].lc = t[x].rc = t[x].tag = c;
t[x].cnt = t[x].sz - 1;
}
void pushdown(int x){
题目3598 [NOI 2021]轻重边
2026-02-25 21:09:54
|
|
|
更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19638674
大意 三种牌分别有 $n , m, k$ 张，要求排列后满足相同的类型的牌不相邻的方案数。 $\newcommand{\binom}[2]{{#1 \choose #2}}$ 思路 这集很考察基本功，组合好题。 考虑插板法，我们首先先把这个东西转换成上面的大意之后，我们先考虑把前两个人的位置考虑好，再考虑第三个人放的位置。 先安排核桃和小 $B$ 的位置，我们先枚举 $i$ 块 H，方案数是 $\binom{n - 1}{i - 1}$，现在我们要把 $m$ 个 B 也分成若干块，插入到这 $i$ 块 H 的空隙里。 为了使得 H 块之间分开，B 块的个数 $j$ 只有三种情况： - $j = i - 1$ - $j = i$ - $j = i + 1$ 其分别对应的情况为：B 块全在 H 块中间，方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i - 2}$，B 和 H 一头一尾（两种情况），方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i - 1} \times 2$，H 全在 B 中间，方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i}$。然而此时的问题是，虽然 B 和 H 交错排列了，但是仍有一部分不合法的块内相邻的点，接下来我们需要做的就是将 R 插入到这个序列里面。 如果每一个 H 块内有 $x$ 个相邻的，那么就需要 $x - 1$ 个板来进行隔开，同样的对于 B 块内的也一样。所以说至少需要拿出来使得不合法变为合法的 R 需要 $(n - i) + (m - j)$ 个 R 来进行~~紧急避险~~，那么我们还能剩的 $k' = (k - n - m + i + j)$，那么我们剩下的这些 $k'$ 应该放到哪些地方呢？首先是 H 和 B 的中间是可以的，然后就是序列的开头和结尾是一定可以的，那么我们的剩余槽位是 $r = i + j$，若是 H 和 B 交错排列的话就是 $r = i + j + 1$，所以接下来的问题是把这剩下的 $k'$ 放到 $r$ 个剩余的槽位中（每个槽可以放 $0$ 个或多个），这个时候使用隔板法 $\binom{k' + r - 1}{r - 1}$，我们将其展开之后就是 $\binom{k - n - m + 2i + 2j}{i + j}$。 所以来说，对应的三种情况的总方案数就可以写出来了： - $i = j - 1：\binom{k - n - m + 4i - 2}{2i - 1}$ - $i = j：\binom{k - n - m + 4i}{2i}$ ........................................................................ 该题解待审........................................................................(剩余 1507 个中英字符)
题目3349 [HSOI 2020] UNO
AAAAA
2026-02-25 20:59:01
|
|
|
[统一省选 2020] 组合数问题 题解说明本题解整理自完整数学推导过程，重点在于如何从定义严格推出可计算的递推式， 并说明该递推如何对应到最终实现代码。 注意： 本题解包含较多组合恒等式与求和变形，请耐心阅读。 简要题意给定整数 $n,x,p$，以及一个 $m$ 次多项式 $$ f(k)=\sum_{i=0}^{m}a_i k^i $$要求计算： $$ \left(\sum_{k=0}^{n} f(k)\cdot x^k \cdot \binom{n}{k}\right)\bmod p $$先说结论定义： $$ F(a,b)=\sum_{k=0}^{a}k^b x^k\binom{a}{k} $$核心递推式$$ \boxed{ F(n,m)=n\left(F(n,m-1)-F(n-1,m-1)\right) } $$边界条件$$ F(k,0)=(x+1)^k $$最终答案$$ \boxed{ \text{ans}=\sum_{i=0}^{m}a_i F(n,i) } $$证明前置公式$$ k\binom{n}{k}=n\binom{n-1}{k-1} $$ $$ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} $$ $$ (x+1)^p=\sum_{i=0}^{p}\binom{p}{i}x^i $$推导一：直接展开（$O(m^2)$）$$ F(n,m)=\sum_{k=0}^{n}k^m x^k\binom{n}{k} $$ $$ \begin{aligned} F(n,m) &=\sum_{k=0}^{n}k^{m-1}x^k\cdot k\binom{n}{k} \\ &=\sum_{k=0}^{n}k^{m-1}x^k\cdot n\binom{n-1}{k-1} \\ &=n\sum_{k=1}^{n}k^{m-1}x^k\binom{n-1}{k-1} \end{aligned} $$ $$ F(n,m) =n\sum_{j=0}^{n-1}(j+1)^{m-1}x^{j+1}\binom{n-1}{j} $$ $$ F(n,m) =nx\sum_{j=0}^{n-1}(j+1)^{m-1}x^{j}\binom{n-1}{j} $$ $$ (j+1)^{m-1}=\sum_{i=0}^{m-1}\binom{m-1}{i}j^i $$ $$ F(n,m)=nx\sum_{i=0}^{m-1}\binom{m-1}{i}F(n-1,i) $$推导二：关键递推$$ \begin{aligned} F(n,m) &=\sum_{k=0}^{n}k^m x^k\binom{n}{k} \\ &=\sum_{k=0}^{n}k^m x^k\binom{n-1}{k} +\sum_{k=0}^{n}k^m x^k\binom{n-1}{k-1} \end{aligned} $$ $$ F(n,m)=F(n-1,m)+x\sum_{i=0}^{m}\binom{m}{i}F(n-1,i) $$ $$ F(n,m)=(1+x)F(n-1,m) +x\sum_{i=0}^{m-1}\binom{m}{i}F(n-1,i) $$ $$ x\sum_{i=0}^{m-1}\binom{m-1}{i}F(n-1,i) =F(n,m-1)-F(n-1,m-1) $$最终结论$$ \boxed{ F(n,m)=n\left(F(n,m-1)-F(n-1,m-1)\right) } $$证毕。 与代码的对应关系（简述）
题目3418 [统一省选 2020]组合数问题
AAAAAAAAAAAAAAAAAAAA
评论
2026-02-25 22:24:41
|
|
|
突然发现自己暑假写过这题。 显然可以考虑动态规划，但不难发现用时间做状态没前途，用站点做状态转移比较困难，而用车次做转移刚刚好。 设 $f_i$ 表示坐上列车 $i$ 的最小烦躁值，因为并没有保证 $x_i<y_i$，所以转移的顺序要按照 $p$ 来排，每次要转移的来源必须满足 $y_j=x_i,q_j\le p_i$。不难完成 $O(n^2)$ 的代码。 考虑优化，注意到转移很像斜率优化，所以使用李超线段树，每次计算完 $f_i$ 后，将 $(q_i,i)$ 放入二叉堆按 $q_i$ 排序。每次转移前，取出二叉堆中所有满足 $q_j\le p_i$ 的 $j$，然后将直线 $j$ 插入第 $y_j$ 个位置的李超树。 李超树动态开点空间复杂度 $O(n)$，时间复杂度 $O(n\log V)$。
题目3224 [NOI 2019]回家路线
AAAAAAAAAAAAAAAAAAAA
 1
评论
2026-02-25 13:29:09
|
|
|
更好的阅读体验https://www.cnblogs.com/To-Carpe-Diem/p/19635184
大意 给出 $b_{i, j} = a_{i - 1, j} + a_{i, j - 1} + a_{i - 1, j - 1} + a_{i, j}$，要求给出一组 $a$ 的可行解，保证 $0 \le a_{i, j} \le 10 ^ 6$。
思路 这集真的神了。 我们想一个问题，首先这个题我们很容易构造出一个 $a$，使其满足 $b$ 的性质，我们将 $a_{i, 1}$ 和 $a_{1, i}$ 都设为 $0$，那么我们有这样的转移式子：$a_{i, j} = b_{i - 1, j - 1} - a_{i - 1, j} - a_{i, j - 1} - a_{i - 1, j - 1}$，这样构造出来的 $a$ 是含有负数的，但是我们考虑进行调整。 这里有一个小巧思，我们考虑对于每一行和每一列进行增量的操作，加减交替，这样会得到以下这个样子的矩阵： $\begin{pmatrix}r_1 + c_1 & -r_1 + c_2 & r_1 + c_3 & \cdots \\r_2 - c_1 & -r_2 - c_2 & r_2 - c_3 & \cdots \\r_3 + c_1 & -r_3 + c_2 & r_3 + c_3 & \cdots \\\vdots & \vdots & \vdots & \ddots\end{pmatrix}$ 有什么用呢？？？我们发现 $(r_1 + c_1) + (-r_1 + c_2) + (r_2 - c_1) + (-r_2 - c_2) = 0$，那么这样我们就在不改变 $b$ 的情况下可以对 $a$ 进行调整，那么会变成类似于这样的差分约束系统：$0 \le a_{i, j} \pm r_i \pm c_i \le 10 ^ 6$，我们就直接对这样的建立差分约束系统，然后跑 SPFA 即可（注意判负环，如果有负环说明就没有答案）
代码
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 1005;
const int INF = 1000000;
int T;
int n, m;
int b[MAXN][MAXN];
int a[MAXN][MAXN];
vector<pair<int, int> > g[MAXN];
bool vis[MAXN << 1];
int dis[MAXN << 1], in[MAXN << 1];
queue<int> q;
void init(){
while(!q.empty()) q.pop();
for(int i = 1;i <= n + m;i ++){
dis[i] = 0;
vis[i] = 1;
in[i] = 0;
q.push(i);
}
}
void solve(){
cin >> n >> m;
for(int i = 1;i < n;i ++){
for(int j = 1;j < m;j ++){
cin >> b[i][j];
}
}
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
a[i][j] = 0;
for(int i = 2;i <= n;i ++){
for(int j = 2;j <= m;j ++){
a[i][j] = b[i - 1][j - 1] - a[i - 1][j] - a[i][j - 1] - a[i - 1][j - 1];
// cout << a[i][j] << ' ';
}
// cout << endl;
}
for(int i = 1;i <= n + m + 1;i ++) g[i].clear();
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
if((i + j) & 1){
g[i].push_back(make_pair(j + n, a[i][j]));
g[j + n].push_back(make_pair(i, INF - a[i][j]));
}
else{
g[j + n].push_back(make_pair(i, a[i][j]));
g[i].push_back(make_pair(j + n, INF - a[i][j]));
}
}
}
init();
while(!q.empty()){
int u = q.front(); q.pop(); vis[u] = 0;
for(auto x : g[u]){
int v = x.first, w = x.second;
if(dis[u] + w < dis[v]){
dis[v] = dis[u] + w;
if(!vis[v]){
in[v] ++;
if(in[v] > n + m + 1){
cout << "NO\n";
return;
}
vis[v] = 1;
q.push(v);
}
}
}
}
bool flag = 1;
// cout << "YES\n";
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
if((i + j) & 1) a[i][j] += (dis[i] - dis[j + n]);
else a[i][j] += (dis[j + n] - dis[i]);
if(a[i][j] < 0) flag = 0;
// cout << a[i][j] << ' ';
}
// cout << '\n';
}
if(flag){
cout << "YES\n";
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
cout << a[i][j] << ' ';
}
cout << '\n';
}
}
else cout << "NO\n";
}
int main(){
// freopen("matrix.in", "r", stdin);
// freopen("matrix.out", "w", stdout);
cin.tie(0) -> ios::sync_with_stdio(0);
cin >> T;
while(T --){
solve();
}
return 0;
}
题目3580 [统一省选 2021]矩阵游戏
AAAAAAAAAAAAAAAAAAAA
评论
2026-02-24 21:20:32
|