沈阳开发网站的地方,帝国系统做网站地图,上海公司牌照价格2022,网站备案通讯地址概率论专题#xff1a;第二类斯特林数 目录 MT2224 矩阵乘法MT2231 越狱MT2232 找朋友MT2233 盒子与球MT2234 点餐 MT2224 矩阵乘法 难度#xff1a;黄金 时间限制#xff1a;5秒 占用内存#xff1a;128M 题目描述 输入两个矩阵#xff0c;第一个矩阵尺寸为 l…概率论专题第二类斯特林数 目录 MT2224 矩阵乘法MT2231 越狱MT2232 找朋友MT2233 盒子与球MT2234 点餐 MT2224 矩阵乘法 难度黄金 时间限制5秒 占用内存128M 题目描述 输入两个矩阵第一个矩阵尺寸为 l × m l×m l×m 第二个矩阵尺寸为 m × n m×n m×n 请你输出这两个矩阵相乘后的结果矩阵。 格式 输入格式第一行输入三个整数 l , m l,m l,m 和 n n n 接下来 l l l 行每行 m m m 个整数表示第一个矩阵 再接下来 m m m 行每行 n n n 个整数表示第二个矩阵。 输出格式输出 l l l 行每行 n n n 个整数表示结果矩阵。 样例 1 输入 4 3 4 1 2 3 4 -5 6 7 8 9 -3 2 1 4 5 6 7 8 6 9 7 0 0 1 0 输出 20 17 27 21 -24 -10 -15 -7 92 83 123 105 4 -3 1 -7 备注 其中 1 ≤ l , m , n ≤ 1000 1≤l,m,n≤1000 1≤l,m,n≤1000 − 1000 ≤ 矩阵中的元素 ≤ 1000 -1000≤矩阵中的元素≤1000 −1000≤矩阵中的元素≤1000。 相关知识点线性代数 题解 求解本题只需要知道矩阵乘法的规则即可。设 A A A 为 m × p m×p m×p 的矩阵 B B B 为 p × n p×n p×n 的矩阵那么矩阵 A A A 与 B B B 可进行乘法运算。设 C A B CAB CAB则矩阵 C C C 为一个 m × n m×n m×n 的矩阵且 C C C 的第 i i i 行第 j j j 列元素可被表示为 C i j ∑ k 1 p a i k b k j a i 1 b 1 j a i 2 b 2 j … a i p b p j C_{ij}\sum_{k1}^{p}{a_{ik}b_{kj}}a_{i1}b_{1j}a_{i2}b_{2j}\ldotsa_{ip}b_{pj} Cijk1∑paikbkjai1b1jai2b2j…aipbpj
如对 A 2 × 3 [ a 11 a 12 a 13 a 21 a 22 a 23 ] A_{2\times3}\left[\begin{matrix}a_{11}a_{12}a_{13}\\a_{21}a_{22}a_{23}\\\end{matrix}\right] A2×3[a11a21a12a22a13a23]、 B 3 × 2 [ b 11 b 12 b 21 b 22 b 31 b 32 ] B_{3\times2}\left[\begin{matrix}b_{11}b_{12}\\b_{21}b_{22}\\b_{31}b_{32}\\\end{matrix}\right] B3×2 b11b21b31b12b22b32 则有 C 2 × 2 A B [ a 11 b 11 a 12 b 21 a 13 b 31 a 21 b 11 a 22 b 21 a 23 b 31 a 11 b 12 a 12 b 22 a 13 b 32 a 21 b 12 a 22 b 22 a 23 b 32 ] C_{2\times2}AB\left[\begin{matrix}a_{11}b_{11}a_{12}b_{21}a_{13}b_{31}a_{21}b_{11}a_{22}b_{21}a_{23}b_{31}\\a_{11}b_{12}a_{12}b_{22}a_{13}b_{32}a_{21}b_{12}a_{22}b_{22}a_{23}b_{32}\\\end{matrix}\right] C2×2AB[a11b11a12b21a13b31a11b12a12b22a13b32a21b11a22b21a23b31a21b12a22b22a23b32]
下面直接给出求解本题的完整代码
/*MT2224 矩阵乘法
*/ #includebits/stdc.h
using namespace std;const int N 1005;
int mtx1[N][N], mtx2[N][N];// 输入一个 m*n 的矩阵
void getMatrix(int m, int n, int matrix[][N])
{for(int i1; im; i)for(int j1; jn; j)cinmatrix[i][j];
}// 执行矩阵乘法并打印结果
void matrixMuiti(int l, int m, int n, int matrix1[][N], int matrix2[][N])
{int tmp;for(int i1; il; i){for(int j1; jn; j){tmp 0;for(int k1; km; k)tmp matrix1[i][k] * matrix2[k][j];couttmp ;}coutendl;}
}int main( )
{// 录入数据 int l, m, n;cinlmn;getMatrix(l ,m, mtx1);getMatrix(m, n, mtx2);// 执行矩阵乘法并输出结果matrixMuiti(l, m, n, mtx1, mtx2);return 0;
}MT2231 越狱 难度钻石 时间限制1秒 占用内存128M 题目描述 监狱有 n n n 个房间每个房间关押一个犯人有 m m m 种宗教每个犯人会信仰其中一种。如果相邻房间中的犯人的宗教相同就可能发生越狱求有多少种状态可能发生越狱。 答案对1007取模。 格式 输入格式输入一行只有两个整数分别代表宗教数 m m m 和房间数 n n n。 输出格式输出一行一个整数代表答案。 样例 1 输入 2 3 输出 6 备注 其中 1 ≤ m ≤ 10 8 1 ≤ n ≤ 1010 1\le m\le{10}^81≤n≤1010 1≤m≤1081≤n≤1010。 相关知识点排列组合、快速幂 题解 首先对题目的意思进行简单梳理有 n n n 个并排的人非环形结构每个人有且仅有一个信仰现在有 m m m 种信仰问相邻两个人具有同一信仰的排列方式有多少种
“相邻两人具有同一信仰”的排列方式是非常繁杂的如同信仰的相邻人序列可以取 2、3、……的长度也可以是中间间隔若干人后出现同信仰的相邻人序列。因此对这道题采取直接求解法是困难的。此时我们可以求该事件的对立事件方案数并用总排列数减去该数即可总排列数为 m n m^n mn第 i i i 个人有 m m m 种选择。
“存在相邻两人具有同一信仰”的对立事件是“任何相邻的人的信仰彼此不同”。在这种情况下第一个人可以是任意信仰即 a 1 m a_1m a1m接下来第二个人只要不和前一个人信仰相同即可即 a 2 m − 1 a_2m-1 a2m−1第三个人同样只需要和其前一个人的信仰不同即 a 3 m − 1 a_3m-1 a3m−1……可以发现后续每个人都只需要满足不和其前一个人的信仰相同即可即 a i m − 1 ( i 2 , 3 , … , n ) a_im-1\left(i2,3,\ldots,n\right) aim−1(i2,3,…,n)。于是可得到“任何相邻的人的信仰彼此不同”的排列方案共有 ∏ i 1 n a i m ( m − 1 ) n − 1 \prod_{i1}^{n}a_im\left(m-1\right)^{n-1} ∏i1naim(m−1)n−1 种。
所以“相邻两人具有同一信仰”的排列方案共有 m n − m ( m − 1 ) n − 1 m^n-m\left(m-1\right)^{n-1} mn−m(m−1)n−1 种。
从题目给出的数据范围看所计算的两个值都非常庞大无标准的数据类型可以存储因此答案要求对指定数取模。于是这里就涉及到了模运算的一些性质
加法 ( a b ) % M ( ( a % M ) ( b % M ) ) \left(ab\right)\%M\left(\left(a\%M\right)\left(b\%M\right)\right)%M (ab)%M((a%M)(b%M))减法 ( a − b ) % M ( ( a % M ) − ( b % M ) ) \left(a-b\right)\%M\left(\left(a\%M\right)-\left(b\%M\right)\right)%M (a−b)%M((a%M)−(b%M))乘法 ( a × b ) % M ( ( a % M ) × ( b % M ) ) \left(a\times b\right)\%M\left(\left(a\%M\right)\times\left(b\%M\right)\right)%M (a×b)%M((a%M)×(b%M))
从模运算的乘法律可以看出在计算乘幂时可以边取余边计算进而降低中间环节求得的数据范围使标准数据类型可用。
通过循环求乘幂运算的方法很简单此处主要探讨快速幂的实现。
幂运算 m n m^n mn 有一个特性每次叠乘时的乘数一致。因此可通过在已算出的较低次数的乘幂结果上进行新的叠乘运算来降低总计算次数。说简单点就是 m , m 2 , ( m 2 ) 2 , … m,\ m^2,\left(m^2\right)^2,\ldots m, m2,(m2)2,… 直到 m n m^n mn。这实际上是一种分治的思想可采用基于递归的方式实现
int fastPow(int m, int n)
{if(n 1) return m;int tmp fastPow(m, n/2);// 幂为奇数 if(n1) return tmp*tmp*m;// 幂为偶数 else return tmp*tmp;
}不难看出采取这种方法实现快速幂的时间复杂度为 O ( l o g 2 n ) O\left({log}_2{n}\right) O(log2n)。
另一种基于位运算的快速幂实现方法则从幂的二进制形式出发通过对幂逐步移位来实现对幂的分解并完成累乘。例如对 m 11 m^{11} m11首先将幂转换为二进制得到 11 10 1011 2 2 3 2 1 2 0 {11}_{10}{1011}_22^32^12^0 111010112232120这说明对乘幂 m 11 m^{11} m11 的计算只需要将其幂 11 计算到 3 次即可。下面用一个实际例子予以说明计算 m 11 m^{11} m11初始化乘幂结果为 a n s 1 ans1 ans1当前底数为 b a s e m basem basem的流程如下
取幂 1011 的末位得到 1 说明当前需要进行一次累乘于是更新 a n s a n s ∗ b a s e m ans\ \ ans\ast base\ \ m ans ans∗base m。在这之后需要更新底数于是 b a s e b a s e ∗ b a s e m 2 base\ \ base\ast base\ m^2 base base∗base m2。最后将幂 1011 向右移一个单位得到 101取幂 101 的末位得到 1 说明当前需要进行一次累乘于是更新 a n s a n s ∗ b a s e m 3 ans\ \ ans\ast base\ \ m^3 ans ans∗base m3。在这之后需要更新底数于是 b a s e b a s e ∗ b a s e m 4 base\ \ base\ast base\ m^4 base base∗base m4 。最后将幂 101 向右移一个单位得到 10取幂 10 的末位得到 0 说明当前不需要进行累乘于是直接更新底数 b a s e b a s e ∗ b a s e m 8 base\ \ base\ast base\ m^8 base base∗base m8。最后将幂 10 向右移一个单位得到 1取幂 1 的末位得到 1 说明当前需要进行一次累乘于是更新 a n s a n s ∗ b a s e m 11 ans\ \ ans\ast base\ \ m^{11} ans ans∗base m11。在这之后需要更新底数于是 b a s e b a s e ∗ b a s e m 16 base\ \ base\ast base\ m^{16} base base∗base m16。最后将幂 1 向右移一个单位得到 0由于幂已经为 0故退出算法输出最终的乘幂结果。
基于位运算的快速幂具有更快的迭代速度因此在现实中更为常用。下面给出其具体实现注意底数 b a s e base base 可以直接在参数 m m m 的基础上直接进行变换而无需单独设置一个变量
int fastPow(int m, int n)
{int ans 1;while(n){if(n1) ans * m;// 更新底数m * m;// 更新幂n 1;}return ans;
}对本题而言由于涉及到的乘幂运算具有较大数据范围因此需要在求幂的过程中加入取模运算。下面直接给出基于以上思路得到的求解本题的完整代码
/*MT2231 越狱 排列问题m^n - m*(m-1)^(n-1)
*/ #includebits/stdc.h
using namespace std;const int MOD 1007;// 含取模运算的快速幂模板
int fastPow(long m, long n, long mod)
{m % mod;int res 1;while (n){if (n 1)res (res * m) % mod;m (m * m) % mod;n 1;}return res;
}int main( )
{// 录入数据 long m, n;cinmn; // 输出结果注意为了防止出现负数需要加上 MOD 后再取模cout(fastPow(m, n, MOD)-m*fastPow(m-1, n-1, MOD)%MOD MOD)%MODendl; return 0;
}MT2232 找朋友 难度黄金 时间限制5秒 占用内存128M 题目描述 将 n n n 个人分成 m m m 组每组至少一人在比赛结束时同一组的人两两之间都会成为朋友不同分组的分组方案得到的朋友对数不同。你的任务是求出最小和最大的朋友对数。 格式 输入格式两个正整数 n , m n,\ m n, m 输出格式两个整数表示答案。 样例 1 输入 5 1 输出 10 10 备注 其中 1 ≤ m ≤ n ≤ 10 9 1\le m\le n\le{10}^9 1≤m≤n≤109 相关知识点排列组合 题解 题目让我们将 n n n 个人分进 m m m 个组中而在同一个组中的所有人都将成为朋友即任意两人相互认识。然后题目的要求是求在给定人和组数情况下的最小朋友数和最大朋友数。
首先要弄清楚朋友数的含义。例如 n n n 个人一组时有多少朋友数实际上这个问题等价于 n n n 个顶点最多能形成多少条边 以某个点为视角它可以与除自身以外的任何顶点连线得到一条边因此对这个点而言它能形成 n − 1 n-1 n−1 条边。一共有 n n n 个顶点则一共能形成 n ( n − 1 ) n\left(n-1\right) n(n−1) 条边。但是由于每条边都有两个顶点因此在按这样的算法遍历点统计边数时所有边都会被额外记录一次。所以 n n n 个顶点最多能形成 n ( n − 1 ) 2 \frac{n\left(n-1\right)}{2} 2n(n−1) 条边。
当然也可以从排列组合的角度来求解。“ n n n 个顶点最多能形成多少条边”等价于“从 n n n 个顶点中选择 2 个顶点有多少种选法”显然这个问题的答案是 C n 2 n ( n − 1 ) 2 C_n^2\frac{n\left(n-1\right)}{2} Cn22n(n−1)。
而本题有所不同它要求计算将 n n n 个人分进 m m m 个组时整个系统内的最小和最大朋友数。那什么时候系统内的朋友数最少什么时候又最大呢前面提到单个组内的人数假设为 x x x 能形成的朋友数为 x ( x − 1 ) 2 \frac{x\left(x-1\right)}{2} 2x(x−1)。这是一个关于人数的二次函数因此其在人数更多的情况下会产生比人数更少时更多的朋友数。所以为了使整个系统内的朋友数尽可能少就需要让各个分组内的人数较为平均为了使整个系统内的朋友数尽可能多就需要让一个分组得到尽可能多的人而剩余分组则仅分一人。基于此可分别有以下结论
最小朋友数将 n n n 个人平均分配到 m m m 个组中。则 n % m n\%m n%m 的组会分到 n m 1 \frac{n}{m}1 mn1 个人剩余 m − n % m m-n\%m m−n%m 个组将分到 n m \frac{n}{m} mn设为 t m p tmp tmp个人。因此系统内的总朋友数为 ( n % m ) ∗ C t m p 1 2 ( m − n % m ) ∗ C t m p 2 (n\%m)*C_{tmp1}^2(m-n\%m)*C_{tmp}^2 (n%m)∗Ctmp12(m−n%m)∗Ctmp2。最大朋友数将 m − 1 m-1 m−1 个人分到 m − 1 m-1 m−1 个组中各组一个人再将剩余 n − ( m − 1 ) n-(m-1) n−(m−1) 个人分至最后一个组中。则前面的 m − 1 m-1 m−1 个组不会产生朋友数而剩余一个组将产生 C n − ( m − 1 ) 2 C_{n-(m-1)}^2 Cn−(m−1)2个朋友数。
下面给出基于以上思路得到的完整代码
/*MT2232 找朋友
*/
#includebits/stdc.h
using namespace std;int main( )
{// 录入数据 int n, m;cinnm;// 最大的朋友对数 long tmp n-(m-1);long maxPairs tmp*(tmp-1)/2;// 最小的朋友对数 tmp n / m;long minPairs (m-(n%m))*tmp*(tmp-1)/2 (n%m)*tmp*(tmp1)/2;// 输出结果coutminPairs maxPairsendl; return 0;
}MT2233 盒子与球 难度黄金 时间限制1秒 占用内存128M 题目描述 现有 r r r 个互不相同的盒子和 n n n 个互不相同的球要将这 n n n 个球放入 r r r 个盒子中且不允许有空盒子。请求出有多少种不同的放法。 两种放法不同当且仅当存在一个球使得该球在两种放法中放入了不同的盒子。 格式 输入格式输入一行只有两个正整数分别代表 n n n 和 r r r。 输出格式输出一行一个整数代表答案。 样例 1 输入 3 2 输出 6 备注 其中 1 ≤ r ≤ n ≤ 10 1\le r\le n\le10 1≤r≤n≤10。 相关知识点排列组合、第二类斯特林数 题解 这是一道经典的盒子放球问题简化描述如下 n n n 个不同的球放入 r r r 个不同的盒子使每个盒子至少有一个球问总的放置方案。
有关此类问题的一个总结性帖子n 球放 m 盒子问题汇总。
这实际上是一个集合划分问题为解决此类问题定义第二类斯特林数 { n m } \begin{Bmatrix}n \\ m\end{Bmatrix} {nm} 表示将 n n n 个不同元素划分成 m m m 个非空集合读作 “ n n n 子集 m m m”。由于该定义是将元素分成若干集合故又将第二类斯特林数称为斯特林子集数。从该定义不难看出这类数的一些特例
当 n m nm nm 时 { n m } 0 \begin{Bmatrix}n \\ m\end{Bmatrix}0 {nm}0。因为总存在集合没有任何元素当 n ≥ 1 n\geq1 n≥1 时 { n 1 } 0 \begin{Bmatrix}n \\ 1\end{Bmatrix}0 {n1}0。因为只有一种划分方案即将所有元素视为一个集合当 n m 时 nm\ 时 nm 时 { n m } 1 \begin{Bmatrix}n \\ m\end{Bmatrix}1 {nm}1。因为只有一种划分方案即各元素单独形成一个集合当 n ≥ 2 n\geq2 n≥2 时 { n 2 } 2 n − 1 − 1 \begin{Bmatrix}n \\ 2\end{Bmatrix}2^{n-1}-1 {n2}2n−1−1。在这种情况下可将某一元素视为一个集合 Φ \mathrm{\Phi} Φ其他元素视为另一个集合 Ω \mathrm{\Omega} Ω接下来对集合 Φ \mathrm{\Phi} Φ 中的 n − 1 n-1 n−1 个元素而言每个元素都有 2 种选择要么加入集合 Φ \mathrm{\Phi} Φ要么留在集合 Ω \mathrm{\Omega} Ω 中因此这将产生 2 n − 1 2^{n-1} 2n−1 种组合方案。但是这里面包含了全部元素都被分至集合 Φ \mathrm{\Phi} Φ 中的情况因此要再减去 1。
接下来我们讨论第二类斯特林数的递推关系。还是以 “将 n n n 个元素划分成 m m m 个非空集合” 为例假设现在我们要对第 n n n 个元素进行分配那么它面对的场景只有两种情况
前面 n − 1 n-1 n−1 个元素形成了 m − 1 m-1 m−1 个集合。在这种情况下要得到 m m m 个非空集合就只能将第 n n n 个元素单独形成一个集合只有这一种方案故其总方案数为 { n − 1 m − 1 } \begin{Bmatrix}n-1 \\ m-1\end{Bmatrix} {n−1m−1}。前面 n − 1 n-1 n−1 个元素形成了 m m m 个集合。在这种情况下第 n n n 个元素可任选一个集合加入共有 m m m 种选法故总方案数为 m ∗ { n m } m*\begin{Bmatrix}n \\ m\end{Bmatrix} m∗{nm}。
于是可得到第二类斯特林数的递推关系 { n m } { n − 1 m − 1 } m { n − 1 m } n ≥ 1 \begin{Bmatrix}n \\ m\end{Bmatrix}\begin{Bmatrix}n-1 \\ m-1\end{Bmatrix}m\begin{Bmatrix}n-1 \\ m\end{Bmatrix}n≥1 {nm}{n−1m−1}m{n−1m}n≥1
有了递推关系和初始化条件便能计算第二类斯特林数
// 第二类斯特林数递归实现
int getStirling(int n, int m)
{if(nm) return 0;else if((nm) || (m1)) return 1;else if(m2) return pow(2, (n-1))-1;else return getStirling(n-1, m-1) m*getStirling(n-1, m);
}注意到一点本题中的球和盒子都是不同的而第二类斯特林数仅认定元素之间不同换言之用第二类斯特林数计算盒子放球问题时它得到的结果是盒同而球不同。为此我们需要在第二类斯特林数的基础之上再乘以盒子的全排列方案数即有 m ! { n m } m!\begin{Bmatrix}n \\ m\end{Bmatrix} m!{nm}
这便是将 n n n 个不同球放入 m m m 个不同盒子的总方案数。
下面给出基于以上思路得到的求解本题的完整代码
/*MT2233 盒子与球 分球问题、第二类斯特林数
*/ #includebits/stdc.h
using namespace std;// 第二类斯特林数递归实现
int getStirling(int n, int m)
{if(nm) return 0;else if((nm) || (m1)) return 1;else if(m2) return pow(2, (n-1))-1;else return getStirling(n-1, m-1) m*getStirling(n-1, m);
}
// 阶乘递归实现
int getFactorial(int n){if(n1) return 1;else return n*getFactorial(n-1);
}int main( )
{// 录入数据 int n, r;cinnr;// 输出结果coutgetFactorial(r)*getStirling(n, r)endl; return 0;
}MT2234 点餐 难度黄金 时间限制1秒 占用内存128M 题目描述 小码哥和他的两个朋友一起去吃饭他们决定每个人先从菜单上选几道菜然后点三个人都选中的菜。假设菜单中有 n n n 道菜他们三人分别点了 a , b , c a,\ b,\ c a, b, c 道菜小码哥想知道是否有可能不存在三个人都选中的菜。 格式 输入格式一行4 个以空格分隔的正整数 n , a , b , c n,\ a,\ b,\ c n, a, b, c 满足 0 a , b , c ≤ n ≤ 1000 0a,\ b,\ c\le n\le1000 0a, b, c≤n≤1000。 输出格式一行若可能不存三个人都选中的菜就输出 YES否则输出 NO。 样例 1 输入 5 3 4 4 输出 NO 相关知识点排列组合 题解 求解这道题一定要理解题目所说 “是否有可能不存在三人都选中的菜” 的含义。例如现在有 5 道菜三个人分别点了 2、3、4 道菜则我们需要考虑是否存在一种选菜方案使 “不存在三人都选中的菜” 这种局面出现。例如一种可能的 “巧合” 如下 在上面的选菜方案中没有任何一个菜被三人同时选中因此对原问题而言我们的回答是 “YES”。
又比如现在有 5 道菜三个人分别点了 2、4、4 道菜其中有两个人的选菜方案如下 接下来对第三个人而言假设他已经知道了另外两个人的选菜方案具有上帝视角则为了使 “不存在三人都选中的菜” 这种局面出现那他就只能选择 “红烧肉” 和 “青菜汤”。 因此对原问题而言在这样假设下的回答依然是 “YES”。从这里可以看出原问题是一个 “证存在” 的题设因此我们在求解时要做的假设是这三个人都足够聪明且足够有默契相当于直接假设他们彼此可交流。
注意到一件事如果给第三个人再多增加一道菜即现在三人点菜数为 3、4、4则接下来无论怎样安排每个人的选菜方案始终会存在某个菜被三人都点一次。即对原问题回答 “NO”。
可以看出如果要使得 “不存在三人都选中的菜” 的局面出现相当于每个菜最多会被点两次。考虑极限情况即每个菜恰好被点两次。在这种情况下相当于每个人点的菜的总数之和恰好为总菜品的 2 倍类似于上图中的情况。基于此一旦所有人点的菜的总数之和再多出 1都会使得某个菜会被点 3 次。因此不难发现该问题的答案仅取决于 “所有人点的菜的总数之和” 与 “菜品总数” 的大小关系。基于此可得到求解本题的完整代码
/*MT2234 点餐
*/ #includebits/stdc.h
using namespace std;int main( )
{// 录入数据 int n, a, b, c;cinnabc;// 输出结果 if(abc 2*n) coutNOendl;else coutYESendl;return 0;
}END
