CFR635

CFR635 div1

好题:D、E

CF1336A Linova and Kingdom

请先思考后再展开

写复杂了点,其实按照dep-siz排序贪心选前k个就好了,因为一个点的父亲一定比他小

CF1336B Xenia and Colorful Gems

code

CF1336C Kaavi and Magic Spell

题意:长为$n \le 3e3$的字符串S,求$\sum_{前缀A} \sum_{B \in A} [reverse(B)+(A-B)有前缀T]$

请先思考后再展开

想了很久,并不会,看完题解,没救了

转化题解转了个寂寞,按照原题意,$dp(l,r)=用S的前r-l+1个拼出了T_{l,r}的方案数$

CF1336D Yui and Mahjong Set

题意:交互题。给定$n \in [4,100]$,存在长为n值域为$[0,n]$的数组c,维护$A=\sum_{i=1}^n C_{ci}^3,B=\sum_{i=2}^{n-1} c_{i-1} c_ic_{i+1}$,初始的A和B也给定,进行最多n次操作+ x表示永久性$c_x++$,且会返回此时的A和B。最后! c1 c2 c3 ... cn输出最初的c

请先思考后再展开

2n的解法很容易:先给每个位置++,然后只需要用A的增量即$C_{ci}^2$逐个还原

n+1的解法也很容易:最开始两个用2次确定后,当前在第i个且前面都已知且都是正数,自己的话知道是否是0。给自己++得到自己是什么,同时可以用B增量求出下一个是否是0。最后一个位用前面所有已知计算出来

如果用4次得出前3个以及第4个是否是0其实很容易,3113即可,但是没法保证c2是正数,会对后面有影响


正解是$n-1,n-2…3;1,2,1$

这一手操作还是比较厉害的,首先ans1可以确定,然后两次ask(1)的差为$(ans_2+1)(ans_3+1)-ans_2(ans_3+1)=ans_3+1$,最后1、2、3都确定了。接下来递增考虑当初ask(i)时B的差为$ans_{i-2}ans_{i-1}+ans_{i-1}(ans_{i+1}+1)+(ans_{i+1}+1)(ans_{i+2}+1)$,可以求出$ans_{i+2}$

1
2
3
4
5
6
7
int n=qread();ret[0].FR=qread(),ret[0].SE=qread();
fd(i,n-1,3) ret[i]=ask(i);ret[1]=ask(1),ret[2]=ask(2);
pii now=ask(1);ans[1]=sqrt((now.FR-ret[2].FR)*2);
ans[3]=(now.SE-ret[2].SE)-(ret[1].SE-ret[3].SE)-1,ans[2]=(ret[1].SE-ret[3].SE)/(ans[3]+1);
ans[2+2]=(ret[2].SE-ret[1].SE)/(ans[3]+1)-(ans[1]+1)-1;
fo(i,3,n-2) ans[i+2]=(ret[i].SE-ret[i+1].SE-ans[i-2]*ans[i-1])/(ans[i+1]+1)-ans[i-1]-1;
ans[n]++;printf("! ");fo(i,1,n) write1(ans[i]);fflush(stdout);

CF1336E Chiori and Doll Picking

题意:给出$n \le 2e5$个的数,值域$[0,2^m)其中m \le 53$,对于$\forall i \in [0,m],输出 \sum_{2^n种选数方案} |(异或和)_2|=i$(集合大小,下文同)

请先思考后再展开

首先,直接求出线性基B,根据线性基那套理论直接求答案,枚举时使用dfs,复杂度为$O(2^{|B|})$,看起来并没有前途

按照黎明前的巧克力的思路搞:$\prod_{i=1}^n (1+x^{a_i})$做异或卷积,那么手动FWT里面的集合幂级数

相当于对$[x^S]F=\prod_{i=1}^n (1+(-1)^{|a_i \cap S|})=[\forall i, |a_i \cap S|偶]*2^n$做IFWT,因此我们其实需要的是求出所有满足$|a_i \cap S|偶$的集合A

$ans_L=\frac{2^n}{2^m} \sum_{|S|=L} \sum_{a \in A} (-1)^{|S \cap a|}=\frac{2^n}{2^m} \sum_{a \in A} \sum_{k=0}^{|a|} (-1)^k C_{|a|}^k C_{m-|a|}^{L-k} $,因为后面只和|a|和L有关,预处理后求答案的复杂度为$O(|A|)$

因为异或不会影响并的奇偶性,我们可以把条件改为与B中所有人搞,直接枚举判断,复杂度为$O(|B|*2^m)$

为了寻找更有前途的做法,尝试继续按照黎明前的巧克力的思路用FMT推并卷积,然而依然止步于$O(m2^m)$

我们还可以继续挖掘,依然因为异或不会影响并的奇偶性,$x \in A,y \in A \rightarrow x \oplus y \in A$,因此A是个线性空间

接下来我们将构造出A:把B放到一个大小为m的表格中,其中主元为i的放在第i行。取出没有主元的所有列,顺时针旋转90度得到B,但是要给原第j列填上主元j(下面官方题解的图,符号和我的相反,刚好前两个为主元是幸运情况)

正确性是很明显的,因为$x \in A在A主元列中只有一个1,y \in B在B主元列中只有一个1,表格[x][y]=表格[y][x]$,因此一定是0或2

$ans_0=2^{n-|B|}=\frac{2^n}{2^m} |A|,|A|=2^{m-|B|}$,所以我们得到的A是极大的;如果你没发现这个,还有一种简单的证明方式:一个与A线性无关的东西可以被A消成一个只在B主元列区域的数,随便找这个数中某个1,则与以此为主元的B中某个基向量的交集大小为1

那么我们现在得到了$O(|B|)和O(m-|B|)$的做法,所以综合复杂度为$O(nm+m^3+2^{m/2})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vc<ll> can;int tim[100];
void dfs(int i,ll now){ if(i==sz(can)) tim[PC(now)]++; else dfs(i+1,now),dfs(i+1,now^can[i]); }
void main()
{
int n=qread(),m=qread();fo(i,1,n) BS::insert(qread());int B=BS::cnt;
if(B<=27)
{
fo(i,0,60) if(BS::bs[i]) can.PB(BS::bs[i]);
dfs(0,0);fo(L,0,m) write1(tim[L]*qpower(2,n-B)%MOD);
}
else
{
PRE();ll pre[100][100];mem(pre,0);fo(L,0,m) fo(a,0,m) fo(k,0,a) add(pre[L][a],(k&1?MOD-1:1)*Comb(a,k)%MOD*Comb(m-a,L-k)%MOD);
fo(i,0,m-1) if(!BS::bs[i]) { ll A=bin(i);fo(j,0,m-1) A|=(BS::bs[j]>>i)%2*bin(j);can.PB(A); }
dfs(0,0);fo(L,0,m){ ll sum=0;fo(a,0,m) add(sum,tim[a]*pre[L][a]%MOD);write1(sum*qpower(2,n+MOD-1-m)%MOD); }
}
}

CF1336F Journey

咕咕咕

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c878b90.html
转载请注明出处,谢谢!