大事なこと
- 主客転倒(数え上げる対象を逆転してみる)
- まずはnaiveなDPを考える
考え中
包除を考える場合,ある状態の最大がhogehoge以上,とかいう包除はキツいことが多そう.管理しずらいので
E - LEQ and NEQ
これは連続する2つの値が同一にならないような列の数え上げだが,となる部分の個数の偶奇で数え上げて最後に包除している
数式記述メモ
できることのメモ
から個選ぶ,1個以上は連続を含む
選ばれなかったものの集合を考える.
間隔が以上の空間がある.この個数Xで包除
とする(選ばないもの)
->
->
...
->
掛け合わせている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
となる非負整数組の数え上げ
係数の総和を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...みたいな条件が付くが,差分を考えて変形することで項同士の関係を外してそれぞれの項が非負である条件のみを考えればよくなる