Atcoder abc289

發表於 2023-05-23 更新於 2024-10-23 分類於 Atcoder ， ABC Disqus：文章字數： 1.4k 所需閱讀時間 ≈ 5 分鐘

Ex(inverse of polynomial,生成函数,NTT)

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

Ex - Trio

整点A,B,C 每个时刻 +1/-1 等概率

求 T时刻, A,B,C首次三个同时共点的概率 mod 998244353

范围

A,B,C,T [0,1e5]

1025mb

我的思路

p(t) = t时刻首次共点

q(t) = t时刻共点

h(t) = 初始共点, t时候后依然共点

p(t) = q(t) - sum(i < t) p(i)h(t-i)

首先如果能快速/预处理求q和h，就是个分治的卷积

那么问题是如何求q和h

先sort A,B,C

考虑间距(d0,d1)=(AB,AC)，这样的话，h不过是初始(d0,d1)=(0,0)的q的特例而已，所以如何算q?

那么是1/8等概率

(+0,+0)
(+0,-2)
(-2,+0)
(-2,-2)
(+2,+2)
(+2,+0)
(+0,+2)
(+0,+0)

似乎比较难弄其个数关系?

容斥似乎也不好容斥

换成距离考虑A增加dA,B增加dA+AB,C增加dA+AC

P(t,d)=t时间，增加d的概率:

d = inccnt - deccnt
t = inccnt + deccnt
inccnt = (d+t)/2
P(t,d) = binom(t,(d+t)/2) / 2^t

q(t) = for dA: sum p(t,dA) * p(t,dA+AB) * p(t,dA+AC)

这样对于给定t 需要(幂次和binom可以预处理) O(t) 来算

题解

inverse of polynomial

f(t) = t时刻首次一致概率

g(t) = t时刻一致的概率

h(t) = 初始一致经过t一致的概率

emmm 和我想的拆解一样的

$f(t) = g(t) - \sum_{0 \leq u \lt t} f(u) h(t - u).$

也是 DP就是$O(n^2)$, 所以分治卷积

但是这里上生成函数

$F(x) = \sum_{i=0}^\infty f(i) x^i, G(x) = \sum_{i=0}^\infty g(i) x^i, H(x) = \sum_{i=0}^\infty h(i) x^i.$

$\begin{aligned} \sum_{t=0}^\infty f(t) x^t = \sum_{t=0}^\infty \left( g(t) - \sum_{0 \leq u \lt t} f(u) h(t - u) \right) x^t \\ \to F(x) = G(x) - F(x) (H(x) - h(0)),\end{aligned}$

注意到$h(0) = 1$带入有

$F(x) = \frac{G(x)}{H(x)}$

因为只需要$F(T)$, 所以如果算出$\frac{1}{H(x)}$ 直接for一下就行，而生成方程的负一次方在abc269ex中有用过$O(T \log T)$

综上得到的结论是只需要g,h (和我上面不会的一样)

问题还是求初始在X,Y,Z, g(t) = 在同一个位置的概率， h只是特例的X=Y=Z

为了简单起见 $K < 0$或$K$非整数,令$\frac{1}{K!}=0,\binom{N}{K}=0$

$p(t,w)=$, t时刻三个人在位置w

$\displaystyle p(t,w) = \frac{1}{2^{3t}}\binom{t}{\frac{t+w-X}{2}}\binom{t}{\frac{t+w-Y}{2}}\binom{t}{\frac{t+w-Z}{2}}$

令$\displaystyle q(i) = \frac{1}{\binom{i-X}{2}!\binom{i-Y}{2}!\binom{i-Z}{2}!}$,$\displaystyle r(i) = \frac{1}{\binom{i+X}{2}!\binom{i+Y}{2}!\binom{i+Z}{2}!}$

则$p(t,w) = \frac{(t!)^3}{2^{3t}}q(t+w)r(t-w)$

$\displaystyle p(t) = \sum_{w} p(t,w) = \frac{(t!)^3}{2^{3t}}\sum_{u}q(u)r(2t-u)$

这样又变成卷积形式了！！！！

编码, x <= y <= z, 转换成0 <= y-x <= z-x

$w \in [-t,+t]$

$u=i=t+w \in[0,2t]$

$2t-u \in[0,2t]$

代码

https://atcoder.jp/contests/abc289/submissions/41657051

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
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;}

namespace CMM{
  template<class T>
    class Poly{
      std::vector<T>_d;
    public:
      Poly(const std::vector<T> &d={}):_d(d){};
      friend Poly operator-(const Poly&p0,const Poly&p1){
        std::vector<T>r=p0._d;
        if(p1._d.size()>r.size())r.resize(p1._d.size());
        for(int i=0;i<(int)p1._d.size();i++)r[i]-=p1._d[i];
        return r;
      }
      friend Poly operator*(const Poly&p0,const Poly&p1){ // ntt
        return atcoder::convolution(p0._d,p1._d);
      }
      std::vector<T> coef()const{
        return _d;
      }
      Poly Modn(int n) const{ // return (this) mod x^n
        std::vector<T>r=_d;
        if((int)r.size()>n) r.resize(n);
        return r;
      }
      Poly Inv(int n) const{ // return this^{-1}, s.t. this this^{-1} \equiv 1 \pmod{x^n}
        assert(_d[0] != 0);
        Poly r = std::vector<T>{_d[0].inv()};
        for(int pwr=1;pwr<n;pwr*=2){
          r = r.Modn(pwr);
          r = r * (Poly({2}) - r * _d);
        }
        return r.Modn(n);
      }
    };
};
// --------

const int N=300000; // 2t+z
mint fac[N+10]={1};
mint ifac[N+10];
mint inv2=mint(2).inv();

using poly=CMM::Poly<mint>;

int main(){
  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);
  auto _=[&](int p){return (p<0 || p%2!=0)?0:ifac[p/2];};

  array<ll,3> xyz;
  rep(i,0,3) xyz[i]=read();
  ll t=read();

  auto calc=[&](int X,int Y,int Z)->vector<mint>{
    // u \in [0,2t],
    vector<mint> q(2*t+1,0); // q(u)= 1/(((u-X)/2)!((u-Y)/2)!((u-Z)/2)!)
    vector<mint> r(2*t+1,0); // r(u)= 1/(((u+X)/2)!((u+Y)/2)!((u+Z)/2)!)
    rep(i,0,2*t+1) q[i]=_(i-X)*_(i-Y)*_(i-Z);
    rep(i,0,2*t+1) r[i]=_(i+X)*_(i+Y)*_(i+Z);
    vector<mint> qr = atcoder::convolution(q,r);

    vector<mint> p(t+1,0);
    mint times = 1; // (i!)^3 / (2^{3i})
    rep(i,0,t+1) {
      p[i] = qr[2*i]*times;
      times *= ((i+1)*inv2).pow(3);
    }
    return p;
  };
  sort(begin(xyz),end(xyz));
  auto [X,Y,Z]=xyz;
  auto pxyz = calc(0,Y-X,Z-X);
  auto p0 = calc(0,0,0);
  auto invp0 = poly(p0).Inv(2*t+1).coef();
  mint ans=0;
  rep(i,0,t+1) ans += pxyz[i]*invp0[t-i];
  printf("%d\n",ans.val());
  return 0;
}

总结

从拆解上和题解一样的想到的三个函数，也能想到分治卷积，这两个点说明前面补的ABC有收获效果(abc 212h)

已经看到卷积了，但是完全没去想生成函数还是完全不应该的，应该形成条件反射的，但这里的作用也仅仅是不需要了分治卷积了，而又多需要了生成函数的逆，本身对g/h的求是没有帮助的

包括后面的通过位置来累计概率也是想到了

然后这里其实题解里的设 q,r 再次转化成卷积，说复杂也不复杂，说显然也很显然，但是自己就是没想到，等这个卷积有了，整个题目就没了

参考

官方题解