Atcoder abc240

發表於 2022-09-17 更新於 2024-10-23 分類於 Atcoder ， ABC Disqus：文章字數： 1.8k 所需閱讀時間 ≈ 6 分鐘

G(排列组合)Ex(字典树,字符串,DP,单调队列)

https://atcoder.jp/contests/abc240/tasks

G - Teleporting Takahashi

从(0,0,0)开始,可以6邻移动1个单位, 不能不动

问 N次后恰好在(x,y,z)的方案数 mod 998244353

范围

n 1e7

x,y,z [-1e7,1e7]

我的思路

感觉有点生成方程 $( x+x^{-1} +y+y^{-1}+z+z^{-1})^n$

然后求$x^Xy^Yz^Z$的系数

如果x选了i 次, 那么x^{-1}选了 i-X 次

$\binom{n}{i}\binom{n-i}{i-X}$

如果y选了j 次, 那么y^{-1}选了 j-Y 次

$\binom{n-2i+X}{j} \binom{n-2i+X-j}{j-Y}$

那么z选了k次, 且z^{-1}选了k-Z次

有 2i-X+2j-Y+2k-Z = n

k = (n+X+Y+Z)/2 -i -j

$\binom{n-2i-2j+X+Y}{k} \binom{n-2i-2j+X+Y-k}{k-Z}$

所以合起来

$= \sum \binom{n}{i}\binom{n-i}{i-X}\binom{n-2i+X}{j}\binom{n-2i+X-j}{j-Y}\binom{n-2i-2j+X+Y}{k}\binom{n-2i-2j+X+Y-k}{k-Z}$

$= \sum \frac{n!}{i!(i-X)!j!(j-Y)!k!(k-Z)!}$

$= \sum \frac{n!}{i!(i-X)!j!(j-Y)!(\frac{n+X+Y+Z}{2}-i-j)!(\frac{n+X+Y-Z}{2}-i-j)!}$

$i \ge max(0,X)$

$j \ge max(0,Y)$

$\frac{n+X+Y+Z}{2} - i - j = k \ge max(0,Z)$

$i+j \le \frac{n+X+Y+Z}{2} - max(0,Z)$

直接算,得n^2会TLE

但如果给定i, 看能不能把j相关的变成一个表达式

$\sum_{j=max(0,Y)}^{\frac{n+X+Y+Z}{2}-max(0,Z)-i} \frac{1}{j!(j-Y)!(\frac{n+X+Y+Z}{2}-i-j)!(\frac{n+X+Y-Z}{2}-i-j)!} $

右侧看起来是$\frac{1}{j!(j-Y)!}$ 与剩余部分的卷积

题解

先推二维的表达式, 假设x,y,z >= 0

f(k) = 走x+y+2k步,从(0,0)到(x,y)的方案数

$=\sum_{i=0}^k \frac{(x+y+2k)!}{(x+i)!i!(y+k-i)!(k-i)!} $

$=\sum_{i=0}^k \binom{x+y+2k}{k}\binom{x+y+k}{x+i}\binom{k}{i} $, 分离与i无关的和与i有关的

$=\binom{x+y+2k}{k}\sum_{i=0}^k \binom{x+y+k}{x+i}\binom{k}{i} $ 范德蒙德卷积,小球法,看成一共选y+k个, 最后k个中选i个分类的讨论的和

$=\binom{x+y+2k}{k}\binom{x+y+2k}{y+k}$

最后把z维加进来

走X+Y+Z+2d = n步 , 走到(X,Y,Z)

其中x,y方向一共X+Y+2k步

那么Z方向一共Z+2(d-k) 步, 穿插进去即可, z的正方向走了Z+(d-k) 步,负方向走了d-k步

$ans = \sum_{k=0}^{d} \binom{N}{Z+2(d-k)}\binom{Z+2(d-k)}{d-k}\binom{X+Y+2k}{k}\binom{X+Y+2k}{Y+k}$

代码

https://atcoder.jp/contests/abc240/submissions/34962261

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#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;}

mint fac[10000010] = {1};
mint ifac[10000010];
mint binom(int n,int m){ return fac[n]*ifac[m]*ifac[n-m];}

int main(){
  int n = read(); // 1e7
  int x = abs(read());
  int y = abs(read());
  int z = abs(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);
  if(n < x+y+z || (n-x-y-z)%2){
    printf("0\n");
    return 0;
  }
  int d = (n-x-y-z)/2;
  mint ans = 0;
  rep(i,0,d+1) ans += binom(n,z+2*(d-i)) * binom(z+2*(d-i),d-i) * binom(x+y+2*i,i) * binom(x+y+2*i,y+i);
  printf("%d\n",ans.val());
  return 0;
}

Ex - Sequence of Substrings

给定一个01串s

求最大的k, 能从s中选出k个不重叠的连续子字符串, 且字符串间字典序严格递增

可切分成3个

范围

1024mb

|S| 2.5e4

我的思路

之所以叫做字典序,就是和数值有区别, 比如上面010 比10小,

考虑一个合法的方案中

t[i-1] < t[i] < t[i+1]

t[i-1][0..j-1] == t[i][0..j-1], t[i-1][j] < t[i][j]

那么 t[i][0...j] 是一个t[i]的方案

也就是说一个最优的方案中,总是可以调整成, 当当前字符串开始出现比前面的大时,从此处截断即可

因为这是至少要到j,同时到j也满足

所以len[i] <= len[i-1]+1

所以最大长度是 sqrt N

然而似乎没有太大帮助, 因为如果想dp的方向

需要记录到i位置,划分了j段最小字典序的 s 是什么, 是个 n^2状态, n^2.5 方空间的玩意儿

另一个就是, dp[i][len] = 最后一个选出的是 s[i-len+1..i] 的最长划分次数

这样状态就是n^1.5, 而dp[i][len] 需要考察dp[j<=i-len][>=len-1]转移代价似乎爆炸了?

这是从收集的角度来看, 而如果从贡献的角度

当前S有方案, 那么比它大的长度在 [1..|S|+1]

并且根据上面的截断性质, 只会是把原来的0变成1 然后截断, 或末尾补0/1

虽然可减少一些无效的状态, 但数量级还是下不来

题解

题意转换一样的

构建一个含有所有后缀的trie, 直接做的话,需要N^2

也是和我上面一样的观察, 只用构建长度为sqrt N的后缀数组

dp[0] = 0

dp[i] = map{dp[i],max{dp[0],...,dp[l-1]} + 1}

答案是 max{dp[1..N]}

这里 dp[i] = 以i结尾的最大长度, 在trie上比[i-len+1..i] 小, 且坐标比i-len+1小的最大dp结果

上面推的也是 len不会超过sqrt N

因此直接优先队列+延迟更新

代码

1.5s, 要再快,可以用trie把子串映射成数值, 或者简单的减少字符串操作, 用下标做中间记录

https://atcoder.jp/contests/abc240/submissions/34974635

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

char s_[25010];
vector<string>dp; // 单调递增的子字符串, 长度越大字典序越大!!!!!, dp[len-1] = substr
vector<pair<int,string> >q[25010]; // q[end pos] = {在dp中的index, substr}
int main() {
  int n = read();
  scanf("%s",s_);
  string s = s_;
  rep(i,0,n){
    string t;
    rep(j,0,250)if(i+j<n){ // maxj(maxj+1)/2 > 25000
      t+=s[i+j]; // t = s[i...i+j]
      int p=lower_bound(dp.begin(),dp.end(),t)-dp.begin(); // 单调队列, dp 中存的全是 < i 的结果, 
      if(p==(int)dp.size()) dp.push_back("2"); // 占位
      q[i+j].push_back({p,t}); // dp[p] = s[i...i+j], 在遍历到i+j时再插入, 这里的p也不会变, 因为相对于直接更新,只是延时而已
    }
    for(auto [p,s1]:q[i]) dp[p] = min(dp[p],s1); // 延时更新, 子串结束右侧 到i时 才把左侧起始p加入优先队列
    q[i] = {}; // fix MLE
  }
  printf("%d\n",(int)dp.size());
  return 0;
}

总结

另外一个,很简单但是有效的处理是,先让x,y,z都非负, 这样的话,也不至于我推的里面还有各种min/max

先处理2维也会简单很多, 最后插入3维

k越大, 字典序越大!!!!!, 连长度的性质都推出了,不知道为啥没观察到这么显然的性质

艹怎么感觉我是单调队列不熟悉

参考

官方题解