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)

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

Kirchhoff’s theorem(基尔霍夫定律)

无自环，可重边无向图$G$的生成树个数 = G的Laplacian矩阵(基尔霍夫矩阵)的$n-1$阶余子式的行列式

https://atcoder.jp/contests/abc338

G - evall

给定字符串S,由123456789+*组成

最开始和最后的字符是数字，没有相邻的非数字

对于$(i\le j)$, 如果s[i],s[j]都是数字，则eval(i,j)为这一段字符串的表达式结果

否则 为0

求 $\displaystyle \sum_{i=1}^{|S|}\sum_{i=j}^{|S|} eval(i,j)\mod 998244353$

$|S| \le 10^6$

2s

1024mb

我的思路

这里虽然没有括号，但是有乘法的优先运算

如果固定前面

1
2
3

1234123*234*345+3245*145+324*45*345
[............]
fix          i->

那我们得到的是 [base + prodbase * (cur=34)]

每次遇到数字就是cur*=10,cur+=int(s[i])

而进入新的乘法则是prodbase*=cur, cur = 0

而进入新的加法则是base+=prodbase*cur,prodbase=1,cur=0

这个方法的问题在于 如果想用矩阵表示，那么在做prodbase * cur的时候 无法做这个乘法

再增加prodres东西

1
2
3
4
5
6

1234123*234*345+3245*145+324*45*345
                                 i
[base                  ]          
                         xxxxxx      prodbase 
                                xx   cur
                         xxxxxxxxx   prodres

ans = base + prodres

prodres = prodbase * cur, 而新的转移 发现cur不需要了

那么 遇到数字时,

1
2
3
4
5
6

			sumall     base prodres    prodbase    1
sumall        1 
base          1         1     
prodres      10                 10
prodbase   int(char)         int(char)     1  
1                                                  1

那么 遇到+时,

1
2
3
4
5
6

			sumall    base prodres    prodbase     1
sumall        1 
base                   1          
prodres                1                
prodbase            
1                                         1        1

那么 遇到*时,

1
2
3
4
5
6

			sumall    base prodres    prodbase    1
sumall        1 
base                   1          
prodres                                   1               
prodbase            				       
1                                                 1

所以，后缀矩阵乘法就秒了

前置的是[0,0,0,1,1]

Hall’s theorem, 霍尔定理

二分图 左侧$n$点,右侧$m$点, $n\le m$

二分图的最大匹配个数$=n$ 的充要条件, 左侧点$n$的任意大小$(=k)$的子集 连到右图的点的个数都满足$\ge k$

$f(a,b,c,n) = \sum_{x=0}^n \lfloor \frac{ax+b}{c} \rfloor$

代码

1
2
3
4
5
6
7

// \sum_{x=0}^n \lfloor \frac{ax+b}{c} \rfloor
ll floor_sum(ll a,ll b,ll c,ll n){
  if(a==0) return (b/c)*(n+1);
  if(a >= c or b >= c) return n*(n+1)/2*(a/c) + (n+1)*(b/c) + floor_sum(a%c,b%c,c,n);
  ll m = (a*n+b)/c;
  return m*n - floor_sum(c,c-b-1,a,m-1);
}