https://atcoder.jp/contests/abc288/tasks
G - 3^N Minesweeper [0…3^n-1]的位置上 有0个或1个炸弹
如果两个数在三进制表示下， 所有对应位的差<=1,那么两个数相邻
对于p=0..3^n-1 位置p相邻的位置上有 $a[p]$个炸弹(包括自己)
请构造一个满足的方案
范围 n 12
2s
1024mb
我的思路 3^12 = 531441
注意到 111111111111111111(3进制下) 和所有相邻
而 111111111111111110(3进制下) 和除了 ???????????????????2(3进制下)以外的相邻
因此可以计算 ???????????????????2 中炸弹的个数
同理可以计算 ???????????????????0 中炸弹的个数
因此也就有算 ???????????????????1 中炸弹的个数
换成表就是
1 2 3 4 0 1 2 0 x x 1 x x x 2 x x
考虑两位
1 2 3 4 5 6 7 8 9 10 00 01 02 10 11 12 20 21 22 00 x x x x 01 x x x x x x 02 x x x x 10 x x x x x x 11 x x x x x x x x x 12 x x x x x x 20 x x x x 21 x x x x x x 22 x x x x
看起来就是解一个超大的线性方程组
并且 在2位的时候, 它依然是 线性无关的, 也就是有唯一解
如果要记录 个数关系可能需要7 ^ 12=13841287201 很大
而上面形状可以知道
1 2 3 4 5 6 7 f(00,10,20) = (00+01 , 10+11 , 20+21 ) f(01,11,21) = (00+01+02, 10+11+12, 20+21+22) f(02,12,22) = ( 01+02, 11+12, 21+22) (00,01,02) = f(f(00,10,20)[0],f(01,11,21)[0],f(02,12,22)[0]) (10,11,12) = f(f(00,10,20)[1],f(01,11,21)[1],f(02,12,22)[1]) (20,21,22) = f(f(00,10,20)[2],f(01,11,21)[2],f(02,12,22)[2])
还是不是特别能知道
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 000 001 002 010 011 012 020 021 022 100 101 102 110 111 112 120 121 122 200 201 202 210 211 212 220 221 222 000 x x x x x x x x 001 x x x x x x x x x x x x 002 x x x x x x x x 010 x x x x x x x x x x x x 011 x x x x x x x x x x x x x x x x x x 012 x x x x x x x x x x x x 020 x x x x x x x x 021 x x x x x x x x x x x x 022 x x x x x x x x 100 x x x x x x x x x x x x 101 x x x x x x x x x x x x x x x x x x 102 x x x x x x x x x x x x 110 x x x x x x x x x x x x x x x x x x 111 x x x x x x x x x x x x x x x x x x x x x x x x x x x 112 x x x x x x x x x x x x x x x x x x 120 x x x x x x x x x x x x 121 x x x x x x x x x x x x x x x x x x 122 x x x x x x x x x x x x 200 x x x x x x x x 201 x x x x x x x x x x x x 202 x x x x x x x x 210 x x x x x x x x x x x x 211 x x x x x x x x x x x x x x x x x x 212 x x x x x x x x x x x x 220 x x x x x x x x 221 x x x x x x x x x x x x 222 x x x x x x x x
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 (100,101,102) = f( 100+101, 100+101+102, 101+102 ) (100+101) = f( 100+101+110+111, 100+101+110+111+120+121, 110+111+120+121, ) [0] (100+101+110+111) = f( a[000], a[100] a[200] ) [1]
这样能看出一点规律
最叶子的是高位0~2其它位一致,
然后 按照从高到低在组内交换
代码 https://atcoder.jp/contests/abc288/submissions/38933950
Ex - A Nameless Counting Problem 求满足条件长n序列个数 mod 998244353
$a \in [0,M]$, a的值非严格单调递增, a的至的xor = X
范围 n 200
$M [0,2^{30})$
$X [0,2^{30})$
3s
1024mb
我的思路 这个n 小，但想不出任何关联的东西
如果X > M 就把X放到所有的后面, 如果X<=M就把X插入到前面某个位置之间
插入以后， 就变成了让整个数组xor ==0 了，且X出现次数>=1
对于bit从高到低考虑
那么对于第p位
在整个数组中出现偶数次
那么[....][.....] 切成两半, 一半是p位是0的一半是1的, 那么 要保证的是 X 在其中一个, 以及右侧的 < M
那么跟踪记录, dp[和x高位一致的个数][和M高位一致的个数]
但这还是不够， 还需要记录这两种以外的不同的组的个数, 问题是一个一个记录就太多了
根据差分想法变成map<长度,个数> 注意到 (1+20) * 20 / 2= 210 > 200 所以最多19个不同长度
但实际需要的是, 200 能切成多少个两两不同的 状态表示个数?
感觉, 似乎, 大概, 好像, 应该这样搞吧
一个是状态上限, 一个是如何状态转移, 每次可能把多个长度进行切割
感觉这两个时间复杂度就T了
题解 如果有相邻相同, 则移除这对, 不影响结果
所以考虑两两不同的时的答案 有长度为$i$的两两不同的不要求严格递增的方案数为$g_i$
$ans = \sum_{0\le i\le \frac{N}{2}} \frac{g_{N-2i}}{(N-2i)!}\binom{M+i}{i}.$, 就是插板法 和 去掉无序
$f_i$ 表示长度i且满足 $< M$ 和异或的方案数
同样用容斥 可以 从$f$ 推出$g$
考虑长度为$l$ 的 (i个出现奇数次元素,j种奇数次数字,k种出现偶数次数字) 的方案数
j < length 时有重复元素, 可以缩减成$(j,j,0)$
那么方案数为$\binom{l}{i}\mathrm{odd}(i,j) g_j \mathrm{even}(l-i,k) (M+1-j)^{\underline{k}}.$
其中$ \mathrm{odd}(i,j)$ 表示$i$个可区分数划分成$j$个不可区分的奇数长度集合
其中$ \mathrm{even}(i,j)$ 表示$i$个可区分数划分成$j$个不可区分的偶数长度集合
第一部分binom就是 就是选哪$i$个是奇数个的, 剩下的$l-i$就是偶数个的
odd,even 的部分就是对相同的数的划分
$g_j$ 就是用来完成 满足条件的
最后的就是剩余的偶数种的$k$选择方案了
$g_l = f_l - \sum_{i \in [0,l],j < l, l\equiv j \pmod{2}, k\in[0,l-i]} \binom{l}{i}\mathrm{odd}(i,j) g_j \mathrm{even}(l-i,k) (M+1-j)^{\underline{k}}.$
右侧$\sum_{k=0}^{i} \mathrm{even}(l-i,k) (M+1-j)^{\underline{k}}.$ 可以预处理一下
f 就是 dp[bit b以上][和m一样的个数] 且高位xor是X 的方案数 就能算出
for b = 从大到小
一点数位dp,但又比数位dp简单很多的一个dp
代码 https://atcoder.jp/contests/abc288/submissions/38936088
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 #include <bits/stdc++.h> #include <atcoder/modint> const int MOD=998244353 ;using mint = atcoder::static_modint<MOD>;using namespace std;#define rep(i,a,n) for (int i=a;i<(int)(n);i++) #define per(i,a,n) for (int i=n;i-->(int)(a);) int read () int r;scanf ("%d" ,&r);return r;}const int PWR=32 ;mint fac[210 ]={1 }; mint ifac[210 ]; mint binom[210 ][210 ]; mint downpow (int x,int y) { mint res=1 ; rep (i,x-y+1 ,x+1 ) res*=i; return res; } int main () int n=read (); int m=read (); int x=read (); rep (i,1 ,n+1 ) fac[i]=fac[i-1 ]*i; ifac[n] = fac[n].inv (); per (i,0 ,n) ifac[i]=ifac[i+1 ]*(i+1 ); rep (i,0 ,n+1 ) rep (j,0 ,i+1 ) binom[i][j]=(j?binom[i-1 ][j]+binom[i-1 ][j-1 ]:1 ); vector<mint> f (n+1 ,0 ) ; rep (l,1 ,n+1 ){ vector dp (PWR, vector<mint>(l+1 ,0 )) ; dp[PWR-1 ][l]=1 ; per (i,0 ,PWR-1 ){ int cm=(m>>i)&1 ; int cx=(x>>i)&1 ; rep (j,0 ,l+1 ){ array<mint,2> cnt = {0 ,0 }; rep (k,0 ,l-j+1 ) cnt[k&1 ]+=binom[l-j][k]; if (cm) rep (k,0 ,j+1 ) dp[i][k]+=dp[i+1 ][j]*binom[j][k]*cnt[cx^(k&1 )]; else { int k=0 ; dp[i][j]+=dp[i+1 ][j]*binom[j][0 ]*cnt[cx^(k&1 )]; } } } rep (j,0 ,l+1 ) f[l]+=dp[0 ][j]; } vector odd (n+1 ,vector<mint>(n+1 ,0 )) ; vector even (n+1 ,vector<mint>(n+1 ,0 )) ; odd[0 ][0 ]=even[0 ][0 ]=1 ; rep (i,1 ,n+1 ) rep (j,1 ,i+1 ) rep (k,1 ,i+1 ) { auto &arr=((k&1 )?odd:even); arr[i][j]+=binom[i-1 ][k-1 ]*arr[i-k][j-1 ]; } vector right (n+1 ,vector<mint>(n+1 ,0 )) ; rep (i,0 ,n+1 ) rep (j,0 ,n+1 ) rep (k,0 ,i+1 ) right[i][j]+=even[i][k]*downpow (m+1 -j,k); vector<mint>g (n+1 ,0 ); g[0 ]=!x; rep (l,1 ,n+1 ){ g[l]=f[l]; rep (i,0 ,l+1 ) rep (j,0 ,min (i,l-1 )+1 ) g[l]-=binom[l][i]*odd[i][j]*g[j]*right[l-i][j]; } mint ans=0 ; rep (i,0 ,n/2 +1 ) ans+=g[n-2 *i]*ifac[n-2 *i]*downpow (m+i,i)*ifac[i]; printf ("%d\n" ,ans.val ()); return 0 ; }
总结 VP了一下, 超时4min, 无wa过了A-F, D和E编码起来有点卡手,思路倒是一下就有了
G 从小的去枚举，发现了规律，然后就是个递归过程,没啥其它的了，虽然想得比较久，还是自己搞出来了
apiad只用了3min
Ex
还是容斥感觉少了, 对这种有序与无序的, 一上来大方向都走错了
然后这里 拆的时候也是先拆了奇偶，再在奇偶内去拆，
主要问题是, 第一感觉没有去觉得 没有顺序限制时 是容易计算的
很奇怪,感觉这个题的题解学习了以后,感觉一切都很自然,没有一个点是觉得妙手,但是却自己没有向这个方向去考虑,之前有些Ex或者CF的题总觉得有些妙的地方，这个题就感觉还算朴素，还是基础不熟自己不行
参考 官方题解
洛谷