牛客练习赛64 D-宝石装箱（容斥定律，背包） 链接：https://ac.nowcoder.com/acm/contest/5633/D来源：牛客网 题意： n颗宝石装进n个箱子使得每个箱子中都有一颗宝石。第i颗宝石不能装入第ai个箱子。求合法的装箱方案对998244353取模。 两种装箱方案不同当且仅当两种方案中存在一颗编号相同的宝石装在 不同编号的箱子中。 思路： 设代表第个箱子不能装入的宝石数量。 设为有个箱子装了不合法的宝石的方案数， 可以通过背包形式的动态规划来求解： 初始： 转移：对于每一个箱子，我们更新 设为有个箱子可以任意放个宝石的方案数，则 那么答案即...

Codeforces Round #628 (Div. 2)] D-Ehab the Xorcist 题意： 给定两个整数 让你构造一个长度最小的数组，使其： 1、 2、 不存在这个数组就输出“-1”。 思路： 先考虑不存在的情况： 1、当时，一定不存在，因为异或是不进位的加法，不可能一群数异或起来比加起来还大。 2、奇偶性不一样，考虑异或运算和加法运算的对最低位的影响是相同的（因为没有位置给最低位进位）。 然后都是存在解的情况： 也是分情况讨论： 1、当，如果，那么空数组就可以满足条件，否则构造一个的数组即可。 2、令，即异或运算不进位时的损失值， 如果的二进制与等于0，那么答案为： 否...

P3400 仓鼠窝 题目描述 萌萌哒的Created equal是一只小仓鼠，小仓鼠自然有仓鼠窝啦。 仓鼠窝是一个由nm个格子组成的行数为n、列数为m的矩阵。小仓鼠现在想要知道，这个矩阵中有多少个子矩阵！（实际上就是有多少个子长方形嘛。）比如说有一个23的矩阵，那么11的子矩阵有6个，12的子矩阵有4个，13的子矩阵有2个，21的子矩阵有3个，22的子矩阵有2个，23的子矩阵有1个，所以子矩阵共有6+4+2+3+2+1=18个。 可是仓鼠窝中有的格子被破坏了。现在小仓鼠想要知道，有多少个内部不含被破坏的格子的子矩阵！ 题意： 给定一个的01矩阵，让你计算有多少个子矩阵只包含数字1？ 思路： ...

[Educational Codeforces Round 56 (Rated for Div. 2)] —G. Multidimensional Queries（二进制状压，线段树） G. Multidimensional Queries time limit per test 6 seconds memory limit per test 512 megabytes input standard input output standard output You are given an array aa of nn points in kk-dimensional space. Let t...