https://atcoder.jp/contests/abc228/tasks
w乘h的矩阵初始全白色,每个有数字aij
T 可以染黑 h1 w1
A 可以染白 h2 w2
T 操作一次, S操作一次
分数= 黑色块之和
T 让尽可能大, A让T尽可能小, 求答案
h,w 1000
aij [1,1e9]
2s 1024mb
感觉就是二维常见运算
因为长度如果超了长度, 可以贪心把对应位置全覆盖,可以取min, h2=min(h2,h1), w2=min(w2,w1)
ans = max(f(i,j))
f(i,j) = sum(i,j) - max(g((range))
应该就过了吧
这场UI还有红色特效
https://atcoder.jp/contests/abc227/tasks
长n数组a
每次选k个不同的下标, 让值减1,(保证所有值非负), 求多减的次数
n 2e5
ai [1..1e12]
2s
1024mb
感觉如果数据量小,每次最大k个下标减1
但这样每次要排序, 而且ai很大
https://atcoder.jp/contests/arc146/tasks/arc146_c
求多少个 元素值范围在[0,2^N)的集合满足
集合的任意偶数个数的非空子集合,元素xor均不为0
mod 998244353
先是在想 线性基, 但实际上 1 2 3 4, 也是合法的, 因为, 虽然3可以由2线性表出,但是它们是3个不是偶数个
然后想转移 n -> n+1
显然集合合法,它的子集也是合法
如果n 合法的方案, 拆一部分 高位填,0 另一部分高位填1, 这样的方案一定是合法, 那么 ans[n][len] 乘2^len, 贡献到a[n+1][len]
如果对于n合法,必定不存在 a,a+高位,b,b+高位 同时存在的情况, 因此至多有一个 自身和自身+高位同时存在
那么考虑 合法的选定一个 做这种自身和高位都存在, 剩下的依然拆分, 这样依然是合法的, ans[n][len] * len * 2^{len-1} 贡献到a[n+1][len+1]
然后这样似乎能多次做路径计算+组合数可以做
但是问题是 这样算出来 n=3时答案=141, 而正确的是149
也就是漏情况了
可能存在 不合法的n的方案 但是赋予高位0,1 以后变成n+1的方案 就合法了?
那么就是任意在n中 的 xor(A)^xor(B) = 0,
在n+1中 = xor(A)^xor(B+高位) = 高位
也就是n+1 中所有低位产生xor = 0 的必然对应的高位个数是奇数
不会推了
排列P,
初始,i号人有球i
每次 所有 i != pi 的人, 把球给pi号人
在 > 0 次后,如果所有人又是i号人有球i, 那么就停止
分数 = 最小的次数
求所有排列方案 的分数的k次方的和
mod 998244353
N 50
k 1e4
2 s
1024 mb
很明显, 交换的圈构成环, 次数 = lcm(每个环长)
N 很小, 是不是可以枚举因数
dp[i][j] = 使用i个,最大是j,的{lcm,方案数}
dp[i][j] 贡献来自 dp[i- tm][m],m > j, t > 0, 即n-i+tm个中选tm个, 然后分成t组每组m个
因为组合tm中分成t组,每组m个
这样想,tm中最小的作为开头,依次剩下的选m-1个, 然后剩余就是(t-1)m 同样的
这样每次考虑最小的所在环, 就不重不漏
$\binom{n-i+tm}{tm} A(tm-1,m-1) \cdot A((t-1)m-1,m-1) \cdots$
$ = \binom{n-i+tm}{tm} \frac{(tm)!}{m\cdot 2m \cdots tm}$
$ = \binom{n-i+tm}{tm} \frac{(tm)!}{m^t * t!}$
似乎就对了
感谢google翻译和maspy大佬的几篇博客, 见下方链接
用很多例子来实例如何使用 多项式乘积
状態ごとに何らかの値が計算されているときに、その計算結果を多項式の形で持ちます。この際、 「多項式の次数」が「考えている状態」、「係数」が状態ごとの「計算した値」（多くの場合、数え上げ）を表すように多項式を持つのが原則です。
括号内是或关系, 括号间幂次是加和关系,系数是代价倍数一般是1
翻译了一下, 统一了一下格式,增加了一些步骤
以下未强调的都是非负整数
注意的是有不少都可以写成无限次方的上限,因为超过n不会影响n,看具体情况哪个更好用用哪个
问题1, $A=\{2,3\},B=\{2,4\},C=\{3,5,7\} , a+b+c=n$ 有多少种方法可以
$\lbrack x^n \rbrack (x^2+x^3)(x^2+x^4)(x^3+x^5+x^7)$, 就是乘开后$n$次项的系数