\(\mathit1\)
题意：给定长度为 \(n\) 的序列 \(a\)，\(m\) 次询问，每次给定 \(l,r\) 和 \(k\)，求 \(\sum\limits_{i=l}^r a_i\left(\begin{matrix}i-l\\k\end{matrix}\right)\) 的值。
\(1\le n,m,\sum k\le10^5\)。模数为素数。
我们先思考 \(\sum k\le10^5\) 这个限制。容易让人联想到根号分治。\(k>\sqrt n\) 时直接暴力，最多 \(O(\sqrt n)\) 次。但 \(k\le\sqrt n\) 时怎么做？有一个很厉害的东西就是：
\[\left(\begin{matrix}i-l\\k\end{matrix}\right)=\sum\limits_{j=0}^k\left(\begin{matrix}i\\j\end{matrix}\right)\left(\begin{matrix}-l\\k-j\end{matrix}\right)=\sum\limits_{j=0}^k\left(\begin{matrix}i\\j\end{matrix}\right)\dfrac{(-l)^{\underline{k-j}}}{(k-j)!} \]那么这个就可以直接预处理 \(f(i,j)=\sum\limits_{x=0}^j a_x\left(\begin{matrix}i\\x\end{matrix}\right)\)，然后查询的时候按照上式算即可。
\(\mathit2\)
题意：计数 \(n\times m\) 的矩阵，其元素属于 \(1\) 到 \(c\) 中的整数，且没有两行一模一样，也没有两列一模一样。
\(1\le n,m,c\le4\times10^3\)。任意模数。
这个题直接推通项好像是不太可做，但是有一个特别巧妙的思路。令 \(f_i\) 表示 \(n\) 行 \(i\) 列的答案数量。那么考虑容斥，有以下式子：
\[f_i=\left(\begin{matrix}c^i\\n\end{matrix}\right)n!-\sum\limits_{j=0}^{i-1}\begin{Bmatrix}i\\j\end{Bmatrix}f_j \]这个枚举的 \(j\) 就是在枚举本质不同列数，看成 \(j\) 个无标号盒子。而斯特林数表示枚举每一列所在的盒子情况。然后缩成了 \(j\) 列。不难发现这个矩阵每两列互不相同就等价于原来矩阵原来矩阵每两个盒子所代表的列互不相同。这样就不重不漏地减去了不合法方案。
标签：begin,right,end,matrix,sum,做点,数学题,left From： https://www.cnblogs.com/tulipenoire/p/17793125.html