…求めよ。」最初「これ包除原理なんだろうな…」と思って色々こねくりかえしてみたけど、結局かなり単純な方法で解けた。 H行W列からi行j列を選ぶとその選び方はで、またi行j列のグリッドの埋め方は2^(i+j)通り。 後は(H-i)+(W-j)の偶奇によって、上記のを加減算すればよい。 ll mo=1000000007; ll p2[2501]; ll comb(int P_,int Q_) { static const int N_=1020; static ll C_[N_][…

… > D+Lの時は、包除原理で求める。 一番上の行および下の行、左および右の列がそれぞれある・ない場合の数を求めて、除いた数のパリティによって組み合わせ数を加減算する。ちなみに、自分は本番は4ツ角および角以外の上端・下端・左端・右端のそれぞれにものがあるかないかを2^8通り列挙しようとしたけど、本番中にバグがとりきれなかった。 mo = 1000000007 R,C=map(int,raw_input().strip().split(" ")) X,Y=map(int,raw…

…んでいたりするので、包除原理で解けるかもしれないがちょっと面倒。 ここでは、N個のセグメントのうちP[i]を1個も含まないものを除く、というアプローチで行く。 つまり、0～(P[0]-1)、(P[0]+1)～(P[1]-1)、(P[1]+1)～(P[2]-1)、…、(P[C-1]+1)～1000001に含まれるセグメントを除けばよい。これにはBITを用いて対応できる。 数xを1～1000000まで増やしていき： 途中x==R[i]となるセグメントがあれば、SegTree上でL…