Mitsubachiのメモ

組合せ論をしています

コンテスト中に注意すべきメモ(随時更新)

立ち回り

  • 誤読しない
  • 制約は丁寧に見る、ヒントがあるかも (これ / これ)

問題考察

  • 小規模な場合で実験してみる
  • 考えた必要条件が十分条件にならないか?
  • 0,1,2,...は0,1以上(あるない)にできないか? (これ)
  • 操作の前後で変わらないものはないか?
  • 操作回数の上限が最悪ケースでの回数より遥かに大きくないか? (これ)
  • 逆操作を操作で表現できるか?
  • 文字列の連続するn文字について操作するものはmodnで考える (これ)
  • A xor B <= A + B
  • 和の期待値 = 期待値の和
  • 個々の要素が寄与する分を考える
  • グリッド上の問題は行/列に対応する頂点を持ってきて二部グラフみたいにする、(i,j)は行iと列jに対応する頂点を結ぶ辺としてとらえる
  • 操作の最適化は操作によって得られる状態の条件を考える
  • 最小全域木でN^2辺ある設定の時、クラスカル(マトロイド)や分割統治的な方法で辺の数を削れないかを考える(両端を迂回して作る場合のほうがコストが小さくならないか?)
  • 区間に対する操作は端点での変化を利用できないか?
  • N以下の全てに対する総和を求めるとき、Nを固定してNのみについて考える
  • 同一視して数え上げしたいとき、代表元の存在について気づけないか?
  • オイラーグラフなら次数列の議論 これ
  • ランダムウォークは x か y のどっちかを inc の後に何もしない or 両方 dec と同じ これ

     

実装

  • 値が一定以上になるかを調べるdpでは一定以上になったらmin関数などを使ってオーバーフローを防ぐ
  • 掛け算をFFTで行うとき、底をできるだけ大きくした方がいい(100とか1000とか)
  • bool x,y に対してx != yACLの two_sat で ts.add_clause(x,true,y,true),ts.add_clause(x,false,y,false); として x == yts.add_clause(x,true,y,false),ts.add_clause(x,false,y,true); として実現できる mod2で値を割り当てたいとき使う
  • DFSとかで手元で動かないときはスタックオーバーフローの可能性があるので -Wl,-stack,10485760 をつけてコンパイルしてみる

不正解になったとき

  • オーバーフロー/配列外参照はないか?(intで二分探索するとき上限を2e9にするとオーバーフローすることがある)
  • (REの場合)ゼロ除算をしていないか?
  • (TLEの場合)定数倍と計算量のどっちでひっかかってるか
  • 探索回数が少なすぎることはないか?
  • A*B<CはA<C/Bとするとオーバーフローを避けれる
  • 二分探索の境界は本当に正しいか?ngとした値で実は可能だったりしないか?
  • mod 関係は TLE したら mint 使うか mod 取る回数を減らす

JOI/JOIG 2023/2024 春季トレーニング参加記(チューター視点)

3/20

交流会に行ったら脱葉が司会をしていた。

みんなが交流をしているのを横目にまい泉カツサンドをたくさん食べた。美味しかった。

けんちょんさん、つもいよろずさん、PFNの人などとお話をした。

3/21

遅刻しなかった。

地震速報を久しぶりに聞いた。ビックリした。

昼食の弁当は崎陽軒だった。美味しかった。

3/22

遅刻した。

昼食の弁当は浅草今半だった。美味しかった。

3/23

遅刻した。

昼食の弁当はチキン南蛮弁当だった。美味しかった。

お昼に参加者とSETとitoを遊んだ。

3/24

遅刻しなかった。

昼食の弁当はまい泉だった。美味しかった。

解説した。

オンサイト参加記: 学生選手権2023決勝 + TTPC2023

最近オンサイトに 2 つ参加したので。

 

学生選手権2023 決勝

会場が三田だったが、中高は関西にいた影響でつい「さんだ」と呼んでしまう。

配点が 3-6-7-9-9-12-16 なので 7 まで通したいなあと思ってコンテストを始める。

A - Apple Addiction

2 乗は自明だが、遷移の高速化にかなり詰まってしまった。 dp[i] - a[i] を持たせるのかとか色々迷走した結果、セグ木を 2 種類も使う謎解法になってしまった。 40 分もかかったのかなり痛い。

B - Max Degree Sum

A で詰まったのもあって、こちらの方が体感としては楽だった。 k までを赤色で塗って、他を青色で塗って考えると赤同士を結ぶ辺、赤青を結ぶ辺の順に貪欲をするのが最適で、それぞれで使える数が実は dsu を使えば管理できるという話。

着実に一歩ずつ考察を進められたのでスムーズだった。

C - Power Convergence

x^k と x-1 が互いに素なので x-1 が N の素因数をどれだけ持つかを管理すると f の値も分かるところまでは良くて、実験すると N の素因数の種類数が少ないときだけ重たい解法になった。というわけで埋め込みを考えたが、コンテスト終了までに埋め込みが間に合わなかった。

約数で包除みたいな形になるので、それをちゃんと詰めた方が良かったかもしれない。

スポンサーのプレゼンの間にもパソコンを回したら20分ぐらい遅れて通ったので A をスムーズに行ければ間に合った可能性がある。やらかし。

 

結果

44人 / 55位。 C を 6 割近くが通してるのもだけど解くのが遅かったのが良くなかった。反省。

 

懇親会

食事が豪華だった。春のトヨタと違って50人ぐらいしかいないのでたくさん食べられた。

Yu_212 さんに筑波大セットの tester ありがとうございますと言われた。木上を移動する問題の実装がかなり大変でしたと伝えたら「実装枠です」と返された。まあそうだよねーみたいな気持ちに。

Maspy さんに「LCの準備できてなくてすいません」と伝える。許してもらえた。

帰った後、 22:00 - 3:00 に Ucup Stage 3 に出た。疲れた。

 

 

TTPC2023

1 週間ぐらい前にキャンセル待ちで compass に参加申し込みをしたらキャンセル出て行けることになった。割と直前に参加申し込みしたのでチーム決めのツイートを探したら、 riano_ さんが探していたので組みませんかと連絡を送る。結局 riano_ さんと riantkb さんと組むことになった。

会場が六本木ヒルズのメルカリオフィスだった。豪華。景色もいいしタダの自販機もあって良かった。

チーム名を始めるまで決めてなかったが riano_mtbc という案が挙がったのでそれにすることに。

 

A から C ですぐ実装できるのがあれば僕が書きますということで始めた。後ろを見ているが割と難しそうだし、お二人とも悩んでいそうなので A から C も難しいっぽい。

 

L は半分全列挙ですね、とりあえず 15 点は取れますね。というところはすぐだったので軽く粘着していたが進捗がない。その間にお二人が A から C を通してくださった。感謝。

 

気分転換に M を見てみると P を hash でとって有理数 mod の累積和を使えば解けそう。「p, q <= 1e5 だから P は 2e10 よりデカくしたいので __int128 ですね」と主張してそうですねーになったけど p <= q だったので別に __int128 を使う必要はなかったらしい。(が、有名素数は落とすようにしてたらしいのでラッキー)

あとは適当に書いて AC 。

 

H をみると LCP + SA で解けそうな見た目をしている。サンプル 2 の aba みたいなケースで a を正確に数えるのが少し大変で、特に今見ている index が元の文字列、 LCP 、 SA のどの index に対応するかが分からなくて頭が混乱した。こういうのをサクッと通せるようになりたい。

 

実装に詰まってる途中に riano_ さんから G の議論を確認してほしいと言われる。確かに式変形で綺麗な形になって、 prod(1-x^i) とか 1/(1-x)^n とかを高速に計算したい気持ちになる。

prod(1-x^i) がオイラーの五角数定理の主張なのでそれで行けませんかとなったが、有限項で prod を取ると次数が変わらないか?となった。が、実はそれで良かったらしい。しくじったー。

log と exp 使えば O(nlogn) なので 70 点は取れます。満点の線形時間は分からないです。と返して H の実装に戻った。もう少し G を見るべきだったかもだが、負の二項定理の話を知らなかったので結局無理だった可能性はある。

 

後は L の 15 点を回収した後に K を考えるが難しい。 20 点を取れそうな実装は思いついたがバグらせて時間切れ...

解説を開くと途中で riantkb さんが出した解法で 20 点は取れていた。やってしまった。

 

結果

15 位。そこそこチームに貢献できたかな?割としっかり考えられて良かった。

 

懇親会

去年の UTPC 運営に今度の UTPC の writer をしたいですと打診する。全体的に人手不足らしく歓迎ですと言われた。嬉しい。

恵比寿のサイゼリヤで打ち上げをした。楽しかった。

帰った後、 23:00 - 3:00 に Ucup Stage 5 に途中参加した。疲れた。

 

帰りに六本木ヒルズを出たら東京タワーが見えて驚いたが、そういえば S セメの間に大学の友人とこの周辺を散歩していた。懐かしい。

マトロイドのお勉強メモ - Combinatorial Optimization Fifth Edition

下書きにあったので雑に放流することにする。岡山はいいところでした。

 

-----------------------

 

岡山の数物セミナー spmAd3rd に備えて Combinatorial Optimization の 13 章 Matroids を読む。東京大学に所属しているので無料で PDF が落とせる、良い話。分かりにくいところがあったらここにメモする。
電気通信大学の授業スライド が分かりやすい日本語資料として紹介されたのでこれを適宜活用。

定義まとめ

  • r \left( X \right) : \max\{|Y| : Y \subseteq X, Y \in \mathcal{F}\}
  • \sigma \left( X \right) :  \{y \in E : r \left( X \cup \{ y \} \right) = r \left( X \right) \} 要は入れても r が変わらない要素からなる集合。
  • \rho \left( X \right) : \min\{|Y| : Y \subseteq X, Y \in \mathcal{F} かつ任意の x \in X \ \setminus Y に対して Y \cup \{x\} \notin \mathcal{F} となる \}
  • q \left( E, \mathcal{F} \right) :  \min_{F \subseteq E} \frac{\rho \left( F \right)}{r \left(F\right)}
  • \mathcal{F}^* :  \{ F \subseteq E : F \cap B = \emptyset となる  \left( E, \mathcal{F} \right) の base B が存在する \} マトロイドの双対の定義。

13.1 Independence Systems and Matroids

P321

circuits, bases, bases of X あたりの話が分かりにくかった。整理すると

  • base: B \in \mathcal{F} で任意の e \in E \ \setminus B に対して  B \cup \{e\} \notin \mathcal{F} となるもの
  • circuit:  C \notin \mathcal{F} で任意の e \in C に対して  C \ \setminus {e} \in \mathcal{F} となるもの
  • base of X:  B_X \subseteq X, B_X \in \mathcal {F} で任意の e \in X \ \setminus B_X に対して  B_X \cup \{e\} \notin \mathcal{F} となるもの

で、こいつらからなる集合をそれぞれ bases, circuits, bases of X としている。 電気通信大学第3回スライド がかなり分かりやすかった。

P324

Theorem 13.5. の By (M3''), ... の文章が分かりにくかった。 X,Y \in \mathcal{F} なのだから X は base of X である。第3回スライドのP44の絵を見ると分かりやすいが、 X \subseteq X \cup Y なので base of X \cup Y を一つ B_{X \cup Y} として取れば、 |X| \leq |B_{X \cup Y}| となる。これと |Y| \lt |X| と仮定 (M3'') より示される。この文章より後の議論は straightforward なので良い。

13.2 Other Matroid Axioms

P326

Theorem 13.9. の Namely, ... の文章の下にある1行の式が分かりにくかった。左辺が |B_2| に等しくなるのは絵を書くと分かりやすい。後半の不等号は B_2 \cap \left( X \ \setminus Y \right) = \emptysetX \subseteq B_1 より  X \ \setminus Y \subseteq B_1 \ \setminus B_2 となるので示せる。その先は上の式の左辺と右辺から |B_1 \cap B_2| を引いてあげれば見えやすい。

Theorem 13.10. の A can be ... の文章が(文法的にも)分かりにくかった。 X \ \setminus Y の base を B とすると \left( X \cap Y \right) \cap \left( X \ \setminus Y \right) = \emptysetA \subseteq \left( X \cap Y \right), B \subseteq \left( X \ \setminus Y \right) なので A \cap B = \emptyset となる。 CA \cup B に何かつけて X \cup Y の base にしようという感じなので A,B,C はどの 2 つをとっても共通部分を持たない。
よって so 以下の式が成立する。

P327

Theorem 13.10. の続き。 (R2') から r \left(X\right) \leq |X| を示しているが、これは \emptyset から 1 つ要素を追加していくごとに r は高々 1 しか増えないので示される。

Theorem 13.11. の (S2) を示すところ。 r\left(\left(X \cup \{ z\}\right)\cap Y\right) \geq r \left(X\right) を示したいが、これは zY の外、 Y の中かつ X の外、 X の中の 3 パターンのどれかであり、どれでも X \subseteq Y なので \left(X \cup \{z\}\right)\cap YXX \cup \{ z\} になる。これと \sigma の定義より良い。

13.4 The Greedy Algorithm

P336

Theorem 13.21. のまず主張のところの話。 F \in \mathcal{F} の incidence vector x|E| 次元ベクトルで、 e \in E について、 xe 成分は e \in F のとき 1 で、そうでないとき 0 となるもの。
その下の Proof. 始まってすぐの式の cx とは \sum_{e \in E} c \left(e\right) x_e のこと。

上限下限付き広義単調増加列の数え上げ

noshi91さんの記事 を大いに参考にしています。実装に苦労したので載せます。 verify 用問題は現在 Library Checker で作業しています。

以下の問題を考えます。

整数 N,M と長さ N の非負整数列 A = \left( A_0, A_1, \cdots, A_{N-1} \right), B = \left( B_0, B_1, \cdots, B_{N-1} \right) が与えられます。非負整数列 x = \left( x_0, x_1, \cdots, x_{N-1} \right) で以下の条件を満たすものの個数を \bmod 998244353 で求めてください。

  • 0 \leq x_0 \leq \cdots \leq x_{N-1} \lt M
  • A_i \leq x_i \lt B_i
ただし 0 \leq A_i \lt B_i \leq M は保証されています。

条件式の \ltM,B_i1 を足せば \leq に変えれるので、以降上の問題文の \lt\leq に変えたものを考えます。
次に A_i = \max \left( A_0, A_1, \cdots , A_i \right) , B_i = \min \left( B_i, B_{i+1}, \cdots, B_{N-1} \right) として良いのでこのように A_i,B_i を変更します。実装上においては A_ii が小さいものから、 B_ii が大きいものから上の式を当てはめれば良いです。
また、 A_i,B_i の全てを同じ数減らしても良いので、 A_0=0 とします。

 

まず、部分問題である A_i = 0 の場合すなわち上限のみが指定されている場合を考えます。

dp_{i,j}x_i=j となる個数と考えるナイーブな DP を考えるとこの問題は O \left( NM \right) で解けることがひとまず分かります。

この DP の遷移は A_i \leq j \leq B_i を満たしているとして i=0 においては dp_{i,j} = 1 とし、 i \gt 0 では dp_{i,j} = \sum_{k \leq j} dp_{i-1,k} です。

ここで、 DP の遷移をよく考えると dp_{0,0} = 1 を初期値として dp_{i,j} = dp_{i-1,j} + dp_{i,j-1} としても問題ないことが分かります。答えは \sum_j dp_{N-1,j} なので、この問題は以下のように言い換えることができます。

xy 平面において x=i 上には A_i \leq y \leq B_i の範囲で線分が引かれている。ただし x=N 上には A_{N-1} \leq y \leq B_{N-1} の範囲で線分が引かれている。線分がその上を通っている各格子点において、一つ右(すなわち x 座標に 1 足したもの)の格子点にも線分が通っている場合、その 2 点間にも線分を引く。このようにしてできた図形において  \left( 0,0 \right) から  \left( N,B_{N-1} \right) への経路は何通りか。

例えば N = 3, A = \left( 0,0,0 \right), B = \left( 2,3,5 \right) においては以下のような図形になります。

ここで、格子点の左上に書かれた赤い数字はいわゆる経路数え上げ DP の途中結果であり、特に  dp_{i,j} \left( i,j \right) に書かれた赤い数字です。別の経路と数列の言い換えをすると、 i 回目に右に進んだ時の y 座標の値が x_i に対応しています。例えば青色の経路は  \left( 1,3,3 \right) に、緑色の経路は  \left( 0,0,5 \right) に対応しています。

 

これを分割統治で解くことを考えます。まず、問題を言い換えて一番下の線分には数字 v_0, v_1, \cdots , v_N が書かれている状態から始め、一番右の線分に書かれた赤い数字 B_{N-1} - A_{N-1} +1 個(以降  \left( s_0, s_1, \cdots , s_{B_{N-1}+1} \right) とします) を列挙するものとします。

具体例として A_i,B_i は上の画像のままで  v = \left( 1,10,100,1000 \right) とする場合を考えます。下の画像の通り \left( 1111,1234,1370,1519,1668,1817 \right) がこの場合の答えです。

下辺の真ん中を通る縦線 x=m で図形を分け、その縦線における値を求めます。上の画像なら m=1 であるので x=1 上の赤い数字です。ただし、実装上ではここで再帰的に関数を呼び出しますがその際 v_m の値(今回なら v_1 )を 0 にして呼び出してください。今回なら返り値は  \left( 1,2,3,3 \right) となります。

まず、  s_0, s_1, \cdots , s_{B_m-1} を求めます。 v_m, v_{m+1}, \cdots, v_{N} による寄与、 x=m における答え t_0,t_1, \cdots, t_{B_m} による寄与を考えると、以下の 2 種類の問題が解ければ良いです。イメージとしては下の画像のようになります。

数列 a_0, a_1, \cdots , a_{n-1}m が与えられる。 f \left( x \right) = \sum_i {}_{n-1-i+x} \mathrm{C}_{x} \ a_i として、 f \left( 0 \right), f \left( 1 \right) , \cdots , f \left( m-1 \right) を求めよ。

数列 a_0, a_1, \cdots , a_{n-1}l が与えられる。 g \left( x \right) = \sum_i {}_{l-i+x} \mathrm{C}_{l} \ a_i として、 g \left( 0 \right), g \left( 1 \right) , \cdots , g \left( n-1 \right) を求めよ。

 

 

まず f について解きます。 f \left( x \right) = \sum_i {}_{n-1-i+x} \mathrm{C}_{x} \ a_i = \sum_i \frac{\left(n-1-i+x\right)!}{x!\left(n-1-i\right)!} \ a_i = \frac{1}{x!} \sum_i \left(n-1-i+x\right)! \frac{a_i}{\left(n-1-i\right)!} と式変形できるので数列 p_f = \left( \frac{a_0}{\left(n-1\right)!}, \frac{a_1}{\left(n-2\right)!}, \cdots , \frac{a_{n-1}}{0!} \right), q_f = \left( 0! , 1!, \cdots \right) として p_f,q_f を convolution すると n-1 番目から順に  0! f \left( 0 \right), 1! f \left( 1 \right) , \cdots となります。

次に g について解きます。 g \left( x \right) = \sum_i {}_{l-i+x} \mathrm{C}_{l} \ a_i = \frac{1}{l!} \sum_i \frac{\left( l-i+x \right)!}{\left(-i+x\right)!}a_i と式変形できます。ただし負の階乗がある部分については二項係数の関係上、適切に 0 とする必要があります。数列 p_g = \left( a_0, a_1, \cdots , a_{n-1} \right), q_g = \left( 0,0, \cdots, 0, \frac{l!}{0!}, \frac{\left(l+1\right)}{1!}, \cdots , \frac{\left(l+n-1\right)!}{\left(n-1\right)!} \right) として(ただし q_g の先頭の 0n-1 個です) p_g,q_g を convolution すると n-1 番目から順に  l! g \left( 0 \right), l! g \left( 1 \right) , \cdots となります。

以下が ACL を使用した C++ での実装例です。

実装例
#include <atcoder/modint>
#include <atcoder/convolution>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

vector<mint> fac,finv,inv;
// i!, 1/i!, 1/i

/*
適切に fac,finv,inv の前準備がされているものとする
*/

// v = (v_0, v_1, ... , v_{n-1}) に対し
// f(x) = sum_i ( n-1-i+xCx v_i ) とする
// {f(0), f(1), ... , f(m-1)} を返す
vector<mint> enumerate_f(int n,vector<mint> &v,int m){
  vector<mint> _v=v;
  reverse(_v.begin(),_v.end());
  for(int i=0;i<n;i++)_v[i]*=finv[i];
  reverse(_v.begin(),_v.end());
  // _v = (v_{0}/(n-1)!, v_{1}/(n-2)!, ... , v_{n-1}/0!)
  
  vector<mint> fsub(_n+m);
  for(int i=0;i<n+m;i++)fsub[i]=fac[i];
  
  vector<mint> f=convolution(_v,fsub),res;
  for(int i=0;i<m;i++)res.emplace_back(f[_n-1+i]*finv[i]);
  return res;
}

// v = (v_0, v_1, ... , v_{n-1}), l に対し
// g(x) = sum_i ( l-i+xCl v_i ) とする
// {g(0), g(1), ... , g(n-1)} を返す
vector<mint> enumerate_g(int n,vector<mint> &v,int l){
  vector<mint> _v=v;
  
  vector<mint> gsub(n-1,0);
  for(int i=0;i<n;i++)gsub.emplace_back(fac[l+i]*finv[i]);
  
  vector<mint> g=convolution(_v,gsub),res;
  for(int i=0;i<n;i++)res.emplace_back(g[_n-1+i]*finv[l]);
  return res;
}

 

ここで、右上部分の再帰のために y=B_m 部分の値も求める必要があり、これも縦横を入れ替えて考えることで先ほどと同じようになります。ただし、 t についての f,g の値を求める際にメビウス変換を施す必要があります。なぜなら、 t の部分は既に格子上の数え上げの求め方を行っているために、上側の値は下側の値の影響を受けており、このままでは同じ経路を複数回数え上げることになるためです。

(追記:

Mitarushi さんより、メビウス変換した後の結果は k を整数として x=k+0.5 で区切った時の値とも考えられると指摘されました。その理解の方がわかりやすいかも知れません。 )

このメビウス変換については右上部分の再帰における引数についても行う必要があることに注意してください。

つまり上の例では \left(1,0\right) を引数として左下部分を考え、 \left(1,2,3,3\right) を得ます。その後これをメビウス変換して \left(1,1,1,0\right) とします。次にこれと下の部分である \left(0,0,0\right) から x=3,y \leq 3y=3 の部分の値を求めます。これにより y=3 の部分は \left(3,9,19\right) となります。
これもやはりメビウス変換して \left(3,6,10\right) とし、これを引数部分にして右上部分を考えます。その結果 \left(19,28,37\right) を得ます。 x=3,y \leq 3 とまとめて全体としての結果は \left(1,4,10,19,28,37\right) となり、特に求める問題の答えは 37 です。

全体としての実装は以下のようになります。

実装例
// 長さ n の(広義単調増加な)非負整数列 a に対し以下を考える
// 横の長さを n とする辺がある 左から i の地点から a[i] だけ上に伸びる辺がある
// 上手い具合に横線が引いてある
// また下辺の左から i の地点には start[i] が書かれている
// この状態でマス目数え上げ DP をしたとき、一番右の辺に書かれた数字 a[n-1] 個を返す
vector<mint> sub(int n,vector<int> &a,vector<mint> &start){
  int m=a[n-1];
  vector<mint> res(m+1);
  
  if(n==1){
    for(int i=0;i<m+1;i++)res[i]=start[0];
    return res;
  }
  if(n==2){
    for(int i=0;i<m+1;i++)res[i]=start[0]*min(i+1,a[0]+1)+start[1];
    return res;
  }
  
  //n > 2
  int mid=n/2;
  int m_front=a[mid];
  vector<int> a_front(mid+1),a_back(n-mid);
  vector<mint> start_front(mid+1),start_end(n-mid,0);
  
  for(int i=0;i<mid+1;i++){
    a_front[i]=_a[i];
    start_front[i]=start[i];
    if(i==mid)start_front[i]=0;
  }
  for(int i=mid;i<n;i++){
    a_back[i-mid]=a[i]-m_front;
    start_end[i-mid]=start[i];
  }
  
  vector<mint> sub_front=sub(mid+1,a_front,start_front);
  // sub_front は長さ m_front+1
  
  for(int i=m_front;i>=1;i--)sub_front[i]-=sub_front[i-1];
  
  vector<mint> sub_front_f=enumerate_f(m_front+1,sub_front,n-mid),sub_front_g=enumerate_g(m_front+1,sub_front,n-mid-1);
  vector<mint> start_end_f=enumerate_f(n-mid,start_end,m_front+1),start_end_g=enumerate_g(n-mid,start_end,m_front);
  
  for(int i=0;i<m_front;i++)res[i]=sub_front_g[i]+start_end_f[i];
  for(int i=0;i<n-mid;i++)start_end[i]=sub_front_f[i]+start_end_g[i];
  for(int i=n-mid-1;i>=1;i--)start_end[i]-=start_end[i-1];
  
  vector<mint> sub_end=sub(n-mid,a_back,start_end);
  
  for(int i=0;i<(int)sub_end.size();i++)res[i+m_front]=sub_end[i];
  return res;
}

全体の計算量は O \left( \left( N+M \right) \left( \log \left( N+M \right) \right)^2 \right) です。

 

A_i=0 の制約がない場合を考えます。

まず、先ほどと同じように図形上の経路数え上げに帰着させます。 A_i \lt A_{i+1} の場合において A_i \leq x_i \lt A_{i+1} の場合も数える必要があることに注意すると、以下のような図形を考えれば良いです。

xy 平面において x=i 上には A_{i-1} \leq y \leq B_i の範囲で線分が引かれている。ただし x=0 上には 0 \leq y \leq B_0 の範囲で、 x=N 上には A_{N-1} \leq y \leq B_{N-1} の範囲で線分が引かれている。線分がその上を通っている各格子点において、一つ右(すなわち x 座標に 1 足したもの)の格子点にも線分が通っている場合、その 2 点間にも線分を引く。このようにしてできた図形において  \left( 0,0 \right) から  \left( N,B_{N-1} \right) への経路は何通りか。

\left(0,0\right) から右に進めるだけ進み、突き当たりでは上に進めるだけ進み、と繰り返し  \left( N,B_{N-1} \right) に到達する経路を考えます。

例えば N=7, A = \left( 0,0,1,3,3,4,6 \right), B = \left( 2,5,5,7,7,7,8 \right) では以下のようになります。

 

となります。ここで、この経路は複数の線分の結合として書けます。
上なら格子点の列  \left( 0,0 \right) , \left( 2,0 \right), \left( 2,5 \right), \left( 6,5 \right), \left( 6,8 \right), \left( 7,8 \right) について、隣接する 2 点を結ぶ線分からなるものが赤い経路です。

ここで、線分から線分へ書かれた数字を求めるのは先ほど説明した A_i=0 がある場合の問題(上の実装例では sub に相当)を解けば良いです。この場合では \left(1,1,1\right) から  \left(1,3,6,9,12,15\right), \left( 15,45,93,159,225 \right) , \cdots と求めていきます。

ただし、上でも説明したように適宜メビウス変換を施してから上で説明した問題(上の実装例では sub に相当)を解く処理を行わせることに注意してください。

実装例
// https://noshi91.hatenablog.com/entry/2023/07/21/235339

#include <atcoder/modint>
#include <atcoder/convolution>

using namespace std;
using namespace atcoder;


#include <iostream>

// 以下を満たす "広義" 単調増加の整数列 x を数える
// a_i <= x_i <= b_i
// a,b の単調性は要求しない(内部で補正する)
// ただし、 a,b が非負整数列であることは要求される
struct number_of_increasing_sequences_between_two_sequences{
private:
  using ll = long long;
  using mint = static_modint<998244353>;

  #define all(a) a.begin(),a.end()
  #define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
  #define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)

  int n;
  vector<int> a,b;
  int zelo_flg=0;
  long long mod = 998244353;
  vector<mint> fac,finv,inv;
  // i!, 1/i!, 1/i

  // v = (v_0, v_1, ... , v_{n-1}) に対し
  // f(x) = sum_i ( n-1-i+xCx v_i ) とする
  // {f(0), f(1), ... , f(m-1)} を返す
  vector<mint> enumerate_f(int _n,vector<mint> &v,int m){
    // 省略
  }

  // v = (v_0, v_1, ... , v_{n-1}), l に対し
  // g(x) = sum_i ( l-i+xCl v_i ) とする
  // {g(0), g(1), ... , g(n-1)} を返す
  vector<mint> enumerate_g(int _n,vector<mint> &v,int l){
    // 省略
  }

  // 長さ _n の(広義単調増加な)非負整数列 _a に対し以下を考える
  // 横の長さを _n とする辺がある 左から i の地点から _a[i] だけ上に伸びる辺がある
  // 上手い具合に横線が引いてある
  // また下辺の左から i の地点には start[i] が書かれている
  // この状態でマス目数え上げ DP をしたとき、一番右の辺に書かれた数字 _a[_n-1] 個を返す
  vector<mint> sub(int _n,vector<int> &_a,vector<mint> &start){
    // 省略
  }

public:
  number_of_increasing_sequences_between_two_sequences() = default;
  number_of_increasing_sequences_between_two_sequences(int _n,vector<int> _a,vector<int> _b){
    n=_n,a=_a,b=_b;

    rep(i,0,n){
      if(a[i]>b[i])zelo_flg=1;
      if(i>0&&b[i]<a[i-1])zelo_flg=1;
    }

    per(i,n-2,0)b[i]=min(b[i],b[i+1]);
    rep(i,1,n)a[i]=max(a[i],a[i-1]);

    int al=a[n-1],bl=b[n-1];

    per(i,n-1,1)a[i]=min(a[i],a[i-1]);

    int dec=a[0];
    rep(i,0,n)a[i]-=dec;
    rep(i,0,n)b[i]-=dec;

    n++;
    a.emplace_back(al-dec);
    b.emplace_back(bl+5-dec);

    rep(i,0,n){
      if(a[i]>b[i])zelo_flg=1;
      if(i>0&&b[i]<a[i-1])zelo_flg=1;
    }

    int m=max((n+max(a[n-1],b[n-1]))*2+10,100);
    fac.resize(m);finv.resize(m);inv.resize(m);
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    rep(i,2,m){
      fac[i]=fac[i-1]*i;
      inv[i]=-inv[mod%i]*(mod/i);
      finv[i]=finv[i-1]*inv[i];
    }
  }
  
  void debug_a(){
    for(int val:a)cout<<val<<" ";
    cout<<endl;
  }
  
  void debug_b(){
    for(int val:b)cout<<val<<" ";
    cout<<endl;
  }
  
  // 以下を満たす "広義" 単調増加の整数列 x の個数を返す
  // a_i <= x_i <= b_i
  mint answer(){
    if(zelo_flg)return 0;
    if(n==1)return (mint)b[0]-a[0]+1;

    int dist=upper_bound(all(a),a[0])-a.begin();
    // [0,dist) までは a_i = a_0

    int px=0,py=a[0];
    int qx=dist-1,qy=a[0];
    if(qx==0)qy=b[0];

    vector<mint> now(abs(qx-px)+abs(qy-py)+1,0);
    now[0]=1;

    while(qx!=n-1||qy!=b[n-1]){
      int sz=now.size();
      per(i,sz-1,1){
        if(i==1&&px==0&py==0)break;
        now[i]-=now[i-1];
      }

      if(py==qy){
        // 上に伸ばす
        vector<int> _a(qx-px+1);
        rep(i,0,qx-px+1)_a[i]=b[px+i]-py;
        now=sub(qx-px+1,_a,now);
        px=qx,py=qy;
        qy=b[qx];
      }
      else{
        // 右に伸ばす
        int index=upper_bound(all(a),qy)-a.begin();
        // (px,py), (qx=px,qy) ->
        // (qx,qy), (index,qy)
        vector<int> _a(qy-py+1);
        rep(i,0,qy-py+1){
          int index2=upper_bound(all(a),py+i)-a.begin();
          _a[i]=index2-px;
        }
        per(i,qy-py,0)_a[i]-=_a[0];
        now=sub(qy-py+1,_a,now);
        px=qx,py=qy;
        qx=index-1;
      }
    }
    return now[now.size()-1];
  }
};

using ll = long long;

#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)

using mint = modint998244353;

mint naive(int n,vector<int> a,vector b){
  int mx=3000;
  mint dp[n][mx]={};
  rep(i,a[0],b[0]+1)dp[0][i]=1;
  rep(i,1,n){
    rep(j,a[i],b[i]+1){
      rep(k,0,mx){
        if(j<k)break;
        dp[i][j]+=dp[i-1][k];
      }
    }
  }
  mint res=0;
  rep(i,0,mx)res+=dp[n-1][i];
  return res;
}

int main(){
  int n;cin>>n;
  vector a(n),b(n);
  rep(i,0,n)cin>>a[i];
  rep(i,0,n)cin>>b[i];
  number_of_increasing_sequences_between_two_sequences num(n,a,b);
  //num.debug_a();
  //num.debug_b();
  //cout<<endl;
  cout<<num.answer().val()<<endl;
  cout<<naive(n,a,b).val()<<endl;
}

経路の長さは経路によらず N+B_{N-1} であることを考えると全体の計算量は O \left( \left( N+M \right) \left( \log \left( N+M \right) \right)^2 \right) です。

Div1バチャ日記5 - Codeforces Round #596

C、通したかったな。

codeforces.com

AB2完。Cは終了後にAC。

 

A - p-binary

最初のとっかかりが分かりにくかったが、個数を固定して作れるか考えると Na 個の 2^i の和で表現できるか?という話になる。これは ARC164-A とほぼ同じ設定で、簡単に解ける。

 

B - Power Products

素因数分解した上で、各素因数の指数を \mathrm{mod}\ k すればもう一方の相方(の素因数の指数)が分かる。後はその相方をオーバーフロー回避のため途中で打ち切りつつ具体的に求めれば良い。 AGC003-D とほぼ同じ考え方。 Div1-B にしては簡単?

 

C - Rock Is Push

マス目ごとに何かを管理する O \left( nm \right) の DP だとは考えたが、岩の状態が同じマス目にいて、かつその後の進行方向を固定しても(その後に通りうる部分でさえ)一意に定まらないのでどうすればいいか分からなかった。

解説を開くとそのマス目で方向転換すればいいというのがあり、確かにこれなら岩の状態が一意に定まるなあとなった。マス目 DP において今いるマスを方向転換のキーとして持っておく考え方、覚えておきたい。