think-cell Round 1

發表於 更新於 分類於 ， Disqus： 文章字數： 3.5k 所需閱讀時間 ≈ 12 分鐘
E(排列组合)F(bitmask)G()H()I()

https://codeforces.com/contest/1930

E. 2..3…4…. Wonderful! Wonderful!(3s,256mb)

a[i]=i

for k = 1..(n-1)/2:

输出 原序列 任意次操作(>=0) 后能得到的不同的序列的方案数 mod 998244353

每次操作选择2k+1个数（不需要连续），删掉被选中的里的左边k个和右边k个

n 1e6

2e3组测试

我的思路

容易想到 操作w次，那么就要删除2kw个

而 w \in [0,n/k]

所以sum(w) = O(n log n)

所以如果对于给定的(k,w)能够 常数时间或均摊常数时间求出来就好了

先不考虑时间限制

考虑被删除的 [k-1]个随便选,中间的[2kw-(2k-1)]个不能全部连续,[k-1]个随便选

必要性: 显然每个实际方案最后一次删除一定保证了最左k和最右侧k之间有未被删除的

充分性: 倒着恢复，如果满足，则可以让最后一次删除的一侧恢复到所有删除中的中间部分，归纳得证

这样就是容斥了 binom(n,2kw)- 固定中间连续的方案

for 连续的一坨的 起点是i

$\sum_{i=k}^{n-(2kw-(k-1))+1} \binom{i-1}{k-1}\binom{n-(i+(2kw-(2k-1))-1)}{k-1}$

令$a=k-1$ 会发现是$\sum \binom{a+t}{a}\binom{b-t}{a}$

的形式

$=[x^{n-2kw}] (\sum_{i=0}^{\infty} \binom{a+i}{i}x^i)^2$

或者

$=\frac{1}{(a!)^2}[x^{n-2kw}] (\sum_{i=0}^{\infty} \frac{(a+i)!}{i!}x^i)^2$

然后这个的话， 对于给定的a也就是给定的k来说

可以一次性计算，这样子不同的w只需要取值一下就好了

但 如果 for k {ntt, for w} 的话， ntt的部分的总代价还是 (n^2logn)

不知道 这样能变成 什么函数 从而快速求得系数

题解

考虑 给定数组b,k 判断是否是能从a得到的

那么 b首先一定是a的子序列也就是a是严格递增 即可

然后 考虑 c = a-b(也就是c是被删除的数组)

len(c) mod 2k = 0

b存在一个值同时 > c中的k个，< c中的k个

这个结论 和我得到的一样

然后这里转化的是s=0/1串，1表示未删除，0表示删除

也是 容斥 计算所有-非法串

s有2k倍数的0, 且 左k个0右侧 和 右k个0左侧 没有任何1

所以 s = [k个0任意放]000[k个0任意放]

t = s中间钦定的连续0直接合并成一个

所以 变化后的t只有 2k-1个0了

而对于 给定t,只有唯一的s存在，因为 t中间只有正中的0能展开，而展开的个数 = n-现在的长度

所以 t和s 一一对应

而t的好处是没有任何限制，就很简单了

$\binom{n-2kw+(2k-1)}{2k-1}$

所以 就应该可以证明 $\displaystyle \binom{a+2b+1}{2b+1}=\sum_{i=0}^a \binom{b+i}{b}\binom{a+b-i}{b}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def binom(n,m):
    s = 1
    for i in range(1,m+1):
        s*=n+1-i
        s//=i
    return s


for a in range(1,10):
    for b in range(1,10):
        left = binom(a+2*b+1,2*b+1)
        right = 0
        for i in range(0,a+1):
            right += binom(b+i,b)*binom(a+b-i,b)
        print(a,b,left == right)

然而 wolframalpha给我的是

sum_(i=0)^n binomial(a + i, a) binomial(a - i + n, a) = (4^(-a - 1) Γ(-a - 1/2) binomial(a + n, a) Γ(-a - n))/(sqrt(π) Γ(-2 a - n - 1))

然后 我把a换成m，wolframalpha就正常了？？

sum_(i=0)^n binomial(i + m, m) binomial(-i + m + n, m) = ((2 m + n + 1)!)/((2 m + 1)! n!)

所以它认为a不是整数???

代码

https://codeforces.com/contest/1930/submission/246962299

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/* ... modint lib ... */

#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)
#define per(i,a,n) for(ll i=(n);i-->(ll)(a);)

ll read(){ll r;scanf("%lld",&r);return r;}
// a[i]=i
// for k=1..(n-1)/2
//   能获得的新序列种数
using mint = CMM::modint;

int n;
const int N=1000000;
mint fac[N+10];
mint ifac[N+10];
mint binom(int n,int m){assert(n<=N);return (n<m or m<0)?0:fac[n]*ifac[n-m]*ifac[m]; }
void w(){
  n = read();
  rep(k,1,(n-1)/2+1) {
    mint ans = 1;
    rep(w,1,n+1) {
      if(2*w*k+1 > n) break;
      ans += binom(n,2*k*w) - binom(n-2*k*w+(2*k-1),2*k-1);
    }
    printf("%d ",ans.val());
  }
  printf("\n");
}

int main(){
  fac[0]=1;
  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);
  int t = read();
  while(t--) w();
  return 0;
}

F Maximize the Difference

对于 b[m] 非负整数数字， $\displaystyle f(b) = \max(\max_{i=1}^m (b_i|x) - \min_{i=1}^m (b_i|x))$，其中x可以取任何非负数，这里竖线是或运算

a=[]

q个询问

a.append(v) 然后输出 f(a)

$v \in[0,2^{22})$, 然后 这里有加密 要求强制在线

$q \in[1,10^{6}]$

3s

256mb

我的思路

对于给定数组，如果x是 让表达式最大的值，那么高于 b_i中最高位的 左侧和右侧一定相等，因为在或运算中bi对该位贡献为0,x对该位贡献为x的这一位

所以$x < 2^{22}$

然后 考虑 右侧表达式的 max-min的意义

对于x的位是1的，那么 max和min在这里都是1

对于x的位是0的，那么 这里其实无法确定而是需要从高位向低位看

对于sort(a)来讲，sz=a中最大的2进制位数

如果a中 sz 存在1和0

1
2
3
4
5
6
7
8
9
10
11
12
那么 令
x   = 0111111
则
max = 1111111
min = 0111111
这样的差是
      1000000

而如果x 最高位取1
max = 1??????
min = 1??????
则 差 一定小于 上面的

所以x怎么取:

  1. a中所有最高位都是1, 变成所有a减去最高位 的子问题
  2. x最高位取0, 对于剩余的位，max在高位是1中和x运算，而min在高位是0中和x运算, 贡献 1<<sz

对于 当前位来说，两种情况

  1. min的区间有0 且 max的区间有1，那么分别缩减到对应的区间, 贡献1<<pwr
  2. 区间不变化, 贡献0

怎么实现呢，感觉就是tire树就秒了吗？，每次log级别的计算代价

那么问题在于上面的区间不变化时，这时候有可能需要 对下一个bit做排序！？

而这种情况发生有两种可能

mn 有0和1,但mx只有0

mx 有0和1,但mn只有1

其它情况 要么 本身就只有唯一分支，而且分叉的过程中 也可能选择0或1

然后要设计状态的话 就是从高到低 [0/1/all],$3^{22}=313’8105’9609$

状态记录 下一个bit是否存在0,然而这状态数量记录不下一点

下一个观察就是 max 是全1的，因为上面的方案列成表格

1
2
3
4
5
        0             1       01 mx
0     1-1(x=1) 1-0(x=0)  1-0(x=0)
1     1-1(x=1) 1-1(x=0)  1-1(x=1)
01    1-1(x=1) 1-0(x=0)  1-0(x=0)
mn

从这个思路来看 就是要 找x使得 某个 ai | x=全1, 同时 min(aj | x)尽量小

问题是上面都用了 自顶向下尝试，贪心基本不可能，如果让x尽量小 那么 x=全1-max(ai)

这样的问题就是，对于低位来说 如果 x=0而a中全1, 这样这个带来的 更小 在更低位就可能反效果

1
2
3
4
5
6
7
1101
1011
0100

x=1111-1101 = 0010,

0100 | 0010 = 0110 > 0100 = (1111-1011)|0100

贪不了一点

再回到上面的状态转移

注意到 mn有0 且 mx有1时 转移到的 下层(0,1)状态

而其它情况，都是转移到的 下层(all,all) 的状态

而 对于给定的 数组，分叉点唯一，分叉之后 mn的只有0转移和all转移，而mx的只有1转移和all转移

而分叉点不能下降只能越來越接近根，最多22次

所以每次分叉点更新时，重新计算

而 左右其实是同时转移的

状态数只在分叉后 还是 state = 2^22

state[pwr] = 这一位 分叉/不分叉 的（mn侧个数，mx侧个数）

而注意到 分叉 正好是贡献 1<<pwr, 所以 也就是 最大的（满足高位前缀 和 现有一致）个数乘积非0 state

那么对于 分叉mx侧的就是所有 value的mask子集的 mx侧个数+=1

那么对于 分叉mn侧的就是所有 (value取反)的mask子集的 mn侧个数+=1

不是连续的区间

题解

x = 某个ai !!!!!!!!!!!!!!!!!!!!!!!!, 啊 ！？！？！?！?！?！?

有道理啊 如果x 产出了最小的

那么 考虑 ans = (a_i | x) - (a_j | x)

根据上面推过的， 显然 $a_i \ge a_j$

所以对于高 相同的位来说，$x_0$也取相同的

而对于 从首个不同的开始，按照上面同样的想法，

1
2
3
4
       0            1
0     x=0,ans=0    x=0,ans=1
1     x=1,ans=0    x=1,ans=0
mn

所以$x_0 = a_j$ 且不小于$x$的产出结果

并且是 上面的结论是 $ans = \max_{i,j}((b_i|b_j)-b_j)$

$ans = \max_{i,j}(b_i\mathrm{and} \sim b_j)$

所以两个集合A,B

A包含所有bi的bitmask子集

B包含所有~bi的bitmask子集

f(b) = 最大同时在 A和B中出现的

显然 如果动态添加的话， 如果一个值 被添加了，那么它的bitmask子集一定被添加了

所以 “暴力添加” 就好了，然后最大的维护，简单每次新增的时候check一下就好

代码

1496 ms

https://codeforces.com/contest/1930/submission/247082292

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(int)(n);i++)
const int PWR=22;
int read(){int r;scanf("%d",&r);return r;}
bitset<(1<<PWR)> A,B;
template<class T>
void add(bitset<(1<<PWR)>&S,int v,const T&fn){
  if(!v or S[v]) return;
  S[v] = true;
  fn(v);
  for(int vv=v;vv;vv=vv&(vv-1)) add(S,v-(vv&-vv),fn);
}

int n;
void w(){
  n = read();
  int pwr = 0;
  while((1<<pwr)-1 < n-1) pwr++;
  rep(i,0,1<<pwr) A[i]=B[i]=false;
  int last=0;
  int q=read();
  while(q--) {
    int v = (read()+last)%n;
    add(A,v           ,[&](int x)->void{ if(B[x]) last = max(last,x); });
    add(B,(1<<pwr)-1-v,[&](int x)->void{ if(A[x]) last = max(last,x); });
    printf("%d ",last);
  }
  printf(" \n");
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

G Prefix Max Set Counting

f(arr)=arr 中 每个是前缀最大值的

$f([3,10,4,10,15,1])=[3,10,10,15]$

给定 根1，n个点的树

对于排列p: 如果对于任意i满足树上p[i]的子树中所有点，刚好相邻的在p中放在它后面，则称作pre-order

求 (所有不同的 f(pre-order a)) mod 998244353

n 1e6

5s

512mb

我的思路

这个pre-order是啥呢，很显然，就是 我们遍历多叉树的时候，先访问根，但是子节点顺序随便先后的 访问 顺序而已

所以 如果不考虑 f()的处理， 方案数 = 所有节点的叶子节点个数的阶乘的乘积

那么问题 是 这样的树的遍历顺序 与 f变化的关系是啥

对于一个 子树内的 反应到 f()的方案数是

受到它之前的最大值w 影响

而最多 分为 sz[u]+1种不同的结果

1
2
         u
f_v0(), f_v1()

问题是没看到什么能合并起来的东西，这里n也很大，也不能bitmask，否则可以

f_u(进入范围) = 方案数

在其中[进入u的范围][mask 已经使用的直接儿子] = 方案数 这里转移上其实有一点是当 转移后的 值为w0时，那么 mask将变成 所有 <= w0的儿子都为1了，因为它们的 对于f()的贡献是 无贡献的

所以 考虑对所有子节点 的子树 的w出 排序

1
2
3
     u

v0 v1 v2 (进入后出来的w从小到大，且全部大于（等于（因为两两不等所以可以去掉等于））当前的(进入范围))

那么其实 进入 u走的 一定是v单调递增的，不一定连续

1
2
3
4
5
6
7
8
9
10
11
12
13
把进入范围一起考虑
    u
v0  v1  v2....v[sz] （拍过序）

ways[sz] = [0 0 0 0 0...]

[...i-1] [i....]
          进入范围

首先 所有 > 进入范围的 way[i..sz] += f_v(进入)
然后 for j = i...sz:
		for k = i..j-1:
			ways[j] += ways[k]*f_j(from k)

感觉很难算

不如倒着，既然最后是v[sz]

考虑进入的来源，就变成了 v[sz]子节点+1个对 v0 ... 的区间加法

似乎是能做的？？？， 因为需要操作 O(所有子节点+n)次，每次是一个区间加法log n操作

然后每个点u向上 的状态（u子树中最大值，（u直接子节点个数+1 => 方案数））

1
2
3
4
info[u]
	mx => 使用后的最大值
	[ v0 v1 v2 ....  v[mx] ]
	[w0 w1 w2      w[mx]  1（最大一定是1）]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
dfs(u):
	info[u].mx = u
	for v in G[u]:
		dfs(v)
		chmax(info[u].mx, info[v].mx)
	sort(all(G[u]),cmp = (v)=> info[v].mx)
	info[u].v_arr = G[u].map((v)=> info[v].mx)
	info[u].w_arr = [0 for len(G[v])+1]
	tmp_arr = [0 for len(G[v])] # 临时方案数
	tmp_arr[-1] = 1
	for i in len(G[u])-1..0:
		v = G[u][i]
		calc tmp_arr[i]
		for vl,vr in info[v].v_arr:
			info[u].w_arr.add(vl,vr,wl * tmp_arr[i]) # 根直接到v ????????
			info[u].tmp_arr.add(vl,vr,wl * tmp_arr[i]) # 从前面到v
	dump(info[u].w_arr)

问题在于 不只是 受到max的影响

1
2
3
4
5
       1
     2     3
    4 8  6  10

这样的话 进入1的时候，5,7,9 是不同的，

所以每个info[u]的切割会达到 所有子节点的v_arr，这样状态就太多了？？？？

题解

TODO

总结

官方题解

E: 虽然性质能自己想到了，

但这个所有0合并成1个这么显然的我没有想到哎，那这个 组合求和 我 自己没推出来不应该，

还试过wolframalpha, 然后 似乎它把m看作整数而a没看作整数，如果当时我尝试m 应该就ac了

F: 没有智力，没观察到这个性质

但从做题的角度， 应该要除了考虑大的，还要考虑小的，这里从枚举情况的角度，是完全可以去尝试的，说明尝试的过程做得不彻底