T1
Statement
一个容量为 \(M(\le10000)\) 的背包。\(n(\le1000)\) 个物品,重量为 \(m_1,m_2,...,m_n\)。问在不装物品 \(i(1\le i\le n)\) 的条件下装入重量为 \(j(0\le j\le M)\) 的物品有多少种方案?对于所有的 \(i\) 和 \(j\) 作答。
Solution
\(f(i,j)\) 表示前 \(i\) 个物品,重量为 \(j\) 的方案数,\(f(0,0)=1\)
\[f(i,j)=f(i-1,j)+[j\ge m_i]\cdot f(i-1,j-m_i) \]\(g(i,j)\) 表示不选 \(i\),重量为 \(j\) 的方案数
\[g(i,j)=f(n,j)-[j\ge m_i]\cdot g(i,j-m_i) \]这个方程中 \(g(i,j-m_i)\) 意思是不选 \(i\) 选出 \(j-m_i\) 的方案数,等于必须选 \(i\) 选出 \(j\) 的方案数
\(\mathcal O(nm)\)
T2
Statement
求包含 \(k\) 个逆序对的长度为 \(n\) 的排列个数,\(n\le300\)。
Solution
考虑从 \(1\) 到 \(n\) 一个一个插入每个数
设插入 \(i\),则所有前 \(i-1\) 个数都比 \(i\) 小,\(i\) 可以产生 \(0\sim i-1\) 个逆序对
\(f(i,j)\) 表示前 \(i\) 个数,产生 \(j\) 个逆序对的方案数,\(f(1,0)=1\)
\[f(i,j)=\sum_{k\in[1..i]}[j-i+k\ge0]\cdot f(i-1,j-i+k) \]转移思路:枚举 \(i\) 的插入位置,复杂度:\(\mathcal O(n^2k)\)
T3
Statement
求 \(n(n\le1000)\) 的排列个数,满足有 \(k\) 个位置 \(a_i>i\)。结果对 \(Q\) 取模。
Solution
考虑从 \(1\) 到 \(n\) 加入排列,先是加到末尾,然后可以与之前的数进行交换。
当前数为 \(i\),要交换的位置为 \(j\):
- 若 \(a_j\le j\),则答案增加 \(1\);
- 若 \(a_j>j\),则答案不变。
\(f(i,j)\) 表示前 \(i\) 个数,\(j\) 个位置 \(a_i>i\) 的方案数,\(f(1,0)=1\),其余初始为 \(0\)
\[f(i,j)=(j+1)\cdot f(i-1,j)+(i-j)\cdot f(i-1,j-1) \]- 不交换,则方案数为 \(f(i-1,j)\)
- 与 \(a_p>p\) 交换,则方案数为 \(j\cdot f(i-1,j)\)
- 与 \(a_p\le p\) 交换,则方案数为 \([(i-1)-(j-1)]\cdot f(i-1,j-1)=(i-j)\cdot f(i-1,j-1)\)
答案:\(f(n,k)\),复杂度:\(\mathcal O(n^2)\),注意中间要取个模
T4
Statement
给长度为 \(n(\le2\times10^5)\) 的数列 \(a\) 和 \(b(1\le a_i,b_i\le2000)\)。求
\[\sum_{i=1}^n\sum_{j=i+1}^nC_{a_i+a_j+b_i+b_j}^{a_i+a_j}\bmod(10^9+7) \]Solution
把 \((-a_i,-b_i)\) 看成点 \(A\),\((a_j,b_j)\) 看成点 \(B\),\(C_{a_i+a_j+b_i+b_j}^{a_i+a_j}\) 即为从点 \(A\) 走到点 \(B\) 的方案数
也就是在第一、三象限都有 \(n\) 个点,坐标绝对值 \(\le2000\),求两两走到的方案数之和
考虑从一个第三象限的点 \((x,y)\) 出发走到所有第一象限的点的方案数是怎么求的:
初始 \(f(x,y)=1\),\(f(i,j)=f(i-1,j)+f(i,j-1)\)(假设可以有负数下标)
因为对于所有第三象限的点都是这么求,然后把所有第一象限的 \(f(x,y)\) 加起来,转移方程一模一样
故我们事先把所有第三象限的 \(f(x,y)\) 设为 \(1\),一遍求即可,\(\mathcal O(4000^2)\)
然后减去关于原点对称的点对的方案数再除以 2 即为答案
T5
Statement
给 \(n(n\le2000)\) 个平面整点 \((x_i,y_i)(0\le x_i,y_i\le10^5)\)。问从 \((0,0)\) 走到 \((X,Y)(0\le X,Y\le10^5)\) 且不经过任何一个给定点的方案数。
Solution
答案 = 总数 - 经过任意一个给定点的方案数
我们钦定一个点 \((x_i,y_i)\) 是必须第一次经过的,则路径被分成了从 \((0,0)\) 到 \((x_i,y_i)\) 和从 \((x_i,y_i)\) 到 \((X,Y)\) 两部分
由于从 \((x_i,y_i)\) 走到 \((X,Y)\) 没有任何限制,也就是随便走,故这一部分的答案为 \(\binom{X-x_i+Y-y_i}{X-x_i}\)
而第一部分恰好是个完全相同的子问题,故可以 dp 算,算完后两部分乘起来即可
形式化地:\(f(i)\) 表示考虑前 \(i\) 个点,从 \((0,0)\) 走到 \((x_i,y_i)\) 且不经过任何一个给定点的方案数,\(f(1)=\binom{x_1+y_1}{x_1}\)
\[f(i)=\binom{x_i+y_i}{x_i}-\sum_{j\in[1..i-1]}f(j)\cdot\binom{x_i-x_j+y_i-y_j}{x_i-x_j} \]答案为 \(f(n)\),复杂度 \(\mathcal O(n^2)\)
T6
Statement
已知 \(k\) 次方和的通项公式为
\[\sum_{i=0}^ni^k=\dfrac1{k+1}\sum_{i=0}^kC_{k+1}^iB_i(n+1)^{k+1-i} \]给出 \(B_i\) 的求解方式。
Solution
代入 \(n=0\) 得
\[\sum_{i=0}^kC_{k+1}^iB_i=0 \]即对于 \(n>0\),有 \(\sum_{i=0}^nC_{n+1}^iB_i=0\)
而 \(B_0=1\),根据上式即可 \(\mathcal O(n^2)\) 递推
标签:方案,le,cdot,sum,Statement,mathcal,数学题 From: https://www.cnblogs.com/laijinyi/p/18148218/Maths-2