…ごとに数を求める。 包除原理の考え方から、まずは重なりを無視してそれぞれの左下マスから生成できるL字の組み合わせを掛け合わせる。 そこから重なるケースを引けばよい。 グリッドサイズ1辺をNとするとO(N^4)なので余裕。 class TwoLLogo { public: ll wid[31][31]; ll hei[31][31]; vector<pair<int,int> > OK; ll cross(int a,int b) { int ax=OK[a].first; i…

…である。あとはこれを包除原理の要領で足したり引いたりすればよい。 素因数の数の偶奇に合わせて(K^N-K)を足し引きする。 ただし素因数が2乗以上になっている場合は、足しも引きもしない。 9の倍数の数の集合は3の倍数の集合に含まれているので、さらに足し引きする必要がないためである。最後に注意点として、low=1の場合、lowだけで構成される数列は題意を満たすので1加算する。 本番は(K^N-K)の-Kの下りを導きだせず正答できなかった。 上記包除原理や平方数の下りだが、どうも…

…dyを素因数分解して包除原理を用いればよい。 dxのうち、dyの素因数を偶数個掛けて得られるものの倍数は足し、奇数個かけて得られるもの倍数は引く。 例えばdy=30=2*3*5なら： dxが1の倍数の時の2*(N+1-dx)の総和を足す dxが2・3・5の倍数の時の2*(N+1-dx)の総和を引く dxが2*3、3*5、2*5の倍数の時の2*(N+1-dx)の総和を足す dxが2*3*5の倍数の時の2*(N+1-dx)の総和を引く なお、dxがある数Pの倍数の時の2*(N+1…

…求めよ。」最初「これ包除原理なんだろうな…」と思って色々こねくりかえしてみたけど、結局かなり単純な方法で解けた。 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…