数え上げ memo

大事なこと

  • 主客転倒(数え上げる対象を逆転してみる)
  • まずはnaiveなDPを考える

考え中

包除を考える場合,ある状態の最大がhogehoge以上,とかいう包除はキツいことが多そう.管理しずらいので
E - LEQ and NEQ
これは連続する2つの値が同一にならないような列の数え上げだが, X _ i == X _ {i+1}となる部分の個数の偶奇で数え上げて最後に包除している

数式記述メモ

 _N {C _ K}

できることのメモ

 1\sim Nから M個選ぶ,1個以上は K連続を含む

選ばれなかったものの集合を考える.
間隔が K以上の空間がある.この個数Xで包除
 T=N-Mとする(選ばないもの)
 X=0 ->  _ N {C _ T}
 X=1 ->  _{T+1} {C _ 1} * _ {N-T} {C _ T} ...
 X ->  _ {(T+1)} {C _ X} * _ {(N - X * K)}{C _ T}
掛け合わせている1つ目はどこの隙間を間隔k以上にするか
2つ目はその隙間を確保した上で,どう塗るか
これを包除してあげると解ける
No.1414 東大文系数学2021第2問改 - yukicoder
https://yukicoder.me/submissions/635358

間隔をK以上開けて配置するパターン数

https://atcoder.jp/contests/typical90/tasks/typical90_o

物をT個置く -> 物の間にK以上追加でそれぞれ何個置くかをcombinationでやってやる

カタラン数関連

下のsnukeさんの記事の斜め線がどこに置いてあっても折り返しを考えれば解ける snuke.hatenablog.com

https://yukicoder.me/submissions/635379

 {C _ 0} * {X _ 0} + {C _ 1} * {X _ 1} ... = Sとなる非負整数組 ({X _ 0}, {X _ 1}, ...)の数え上げ

係数の総和をKとしたとき,O(K3 log S)

// coef_0 * x_0 + coef_1 * x_1 ... =s
// をみたす非負整数(x_0, ...)の組の数を求める
// sum(coef)の行列を累乗する. 
mint myfunc(vector<int> coef,ll S){
    if(S<0) return mint(0);
    int n=(int)coef.size();
    int cs=0;
    for(auto &x:coef){
        assert(x>0);
        cs+=x;
    }
    assert(cs<=1000);// 多分1000でも耐えない

    vector<mint> A(cs+1,0);
    for(int bit=1;bit<(1<<n);bit++){
        int t=0;
        for(int i=0;i<n;i++)if((bit>>i)&1) t+=coef[i];

        if(__builtin_parity(bit)) A[t]+=1;
        else                      A[t]-=1;
    }

    Matrix<mint> M(cs);
    rep(i,cs) M[0][i]=A[i+1];
    for(int i=1;i<cs;i++) M[i][i-1]=1;

    M=M.pow(S);
    return M[0][0];
}

Editorial - AtCoder Beginner Contest 198

この問題では条件にx_1 < x_2...みたいな条件が付くが,差分を考えて変形することで項同士の関係を外してそれぞれの項が非負である条件のみを考えればよくなる