EDPC-Y Grid2

この記事はBoostnoteで書かれた記事をコピペしてきているのでBoostnoteと同様の働きをするMarkdownで読んでね
テーマはlucarioを強くオススメします（俺が好きなので）
一応画質悪いスクショも貼っておくのでどうしても環境がない人はそっちで
基本的に記事は自分の理解を深めるためのoutputとしてやっているので他人への親切心よりも自分のコスパを優先したらこう言う形になった



壁がない場合は$\binom{H-1+W-1}{H-1}$で終わり

壁が一つの場合はそこから「その壁を通る道の数」を引けばいい

具体的には、$\binom{r-1+c-1}{r-1}\times\binom{H-r+W-c}{H-r}$を引いてやる

壁がN個の場合も基本的には同様で

$\sum_{i=1}^{N}\binom{r_i-1+c_i-1}{r_i-1}\times\binom{H-r_i+W-c_i}{H-r_i}$を引く

ただこれだけだと、a個の壁を通るコースをa回も引いてしまっているのでどうにかする これはいわゆる包除原理というやつで、簡単に説明をすると N個の制約のうち一つでも満たしているものの合計は、 （奇数個の制約を満たしているもの）-（偶数個満たしているもの） で求まるってやつ なんか言葉の定義から曖昧すぎて何言ってるか分からないと思うので、知らない人は包除原理で調べて

で、この奇数個のやつ偶数個のやつを全部愚直に計算しようとすると結局$2^N$のパターンがあるのでここで遷移を眺めて纏められるところを纏める まず各壁は$r-1+c-1$だけ歩いたところに存在することから、$r-1+c-1$でソートをしていいことが分かる $i$番目の壁に$a$個目の壁として到着する道の数を$way(i,a)$ $i$番目の壁から$(H,W)$に行く道の数を$A(i)$ と書くと求めたいのは

$\sum{i=1}^{N}(\sum{j:odd}way(i,j)-\sum_{j:even}way(i,j))A(i)$

であり遷移はi番目の壁からj番目の壁に行く道の数をA(i,j)と書くと $way(i,j)=\sum_{k=1}^{i-1}way(k,j-1)A(k,i)$

で、求めたい式も遷移の式も$way$の第二引数は偶奇しか注目していないことが分かるのでそれを纏めてしまうと $way(i,odd)=\sum{k=1}^{i-1}way(k,even)A(k,i)$ $way(i,even)=\sum{k=1}^{i-1}way(k,odd)A(k,i)$ となり、$O(N²)$で全ての$way$が求められる Aは前計算で$O(1)$なのでこれで解けた

MintやnCkは汚いし邪魔になるので省略 見たい人はACコードから

#include <bits/stdc++.h>
using namespace std;

struct wall{int r,c;};
bool cmp(wall a,wall b){return a.r+a.c<b.r+b.c;}
int dp[3001][2],ans;//dp[i][j]:最後に訪れた壁がiで偶奇j個目の時の通り数

int main(){
  int h,w,n;cin>>h>>w>>n;
  vector<wall> v(n);
  for(int i=0;i<n;i++){
    int r,c;cin>>r>>c;
    v[i]={r,c};
  }
  v.push_back({1,1});//スタートに壁があると考えると求めるものが壁を通る道の数1つになって簡単
  sort(v.begin(),v.end(),cmp);

  dp[0][1]=1;//(1,1)を0つ目の壁として通るパターンは1通り
  for(int i=1;i<=n;i++)
    for(int j=0;j<i;j++)
      for(int k=0;k<2;k++)
        dp[i][k]+=dp[j][k^1]*nCk(v[i].r-v[j].r+v[i].c-v[j].c,v[i].r-v[j].r);

  for(int i=0;i<=n;i++)
    for(int k=0;k<2;k++)
      if(k)ans+=dp[i][k]*nCk(h-v[i].r+w-v[i].c,h-v[i].r);
      else ans-=dp[i][k]*nCk(h-v[i].r+w-v[i].c,h-v[i].r);

  cout<<ans<<endl;
}

Submission #11385056 - Educational DP Contest