…は限らない。 そこは包除原理の要領でh(submask)の分を引いていけばよい。 int H,W; string S[1010]; int ok[1<<16]; ll mo=1000000007; int from[1<<16]; ll dpdp[1<<16]; ll dp[20]; inline int mulmod(int a,int b,int mo) { int d,r; if(a==0 || b==0) return 0; if(a==1 || b==1) retu…

…通りあるか。 解法 包除原理の要領でとく。 整数kの倍数がA中にf(k)個あるなら、最大公約数がkの倍数になる組み合わせg(k)はf(k)個から1個以上選ぶ2^(f(k))-1通りとなる。 そこから、kより大きなkの倍数ができてしまうケースg(ik) (i＞1)を引いていけばよい。 int N,A; ll mo=1000000007; int num[101010]; ll p2[101010]; ll pat[101010]; void solve() { int i,j,…

…H(x)を求めてから包除原理の要領でG(x)を求める。（CFが始まるのであとで埋める） int N; ll A[1010101],B[1010101],C[1010101],G[1010101]; ll p2[1010101]; ll mo=1000000007; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; p2[0]=1; FOR(i,1010000) p2[i+1]=p2[i]*2%mo; FOR(i,N) { …

…めればよい。 あとは包除原理の要領で1のままの要素が残っているケースを引こう。 L個中ちょうどK個しか1より大きな値が入っていないケースは、通りなので、K＜Lの各Kに対し、左の値を引いていこう。 ll mo=1000000007; ll dp[3000]; ll combi(ll N_, ll C_) { const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==…

…であってよい)そこで包除原理で数え上げていく。 直径が奇数なので、中心となる辺を挟んだ２頂点を(a,b)とする。a側にあるaの最遠点の集合をP、b側にあるbの最遠点の集合をQとする。 まず、以下を考える。 p∈Pに対しh(p)=0、q∈Qに対しh(q)=1か-1となるケースを数え上げる。 a側の頂点wに対し|h(w)|≦floor(A/2)-e(a,w) b側の頂点wに対し|h(w)|≦floor(A/2)+1-e(b,w) 最終的に、h(a)とh(b)に1差があるケースの積…

…R≦R'≦N-1） 包除原理より、上記値は以下のように更新できる。 Ins(L,R) = InsSum(L+1,R-1) + 1 (S[L]==S[R]の場合。S[L]!=S[R]の場合0) InsSum(L,R) = InsSum(L,R-1)+InsSum(L+1,R-1)-InsSum(L+1,R-1) + Ins(L,R) Out(L,R) = OutSum(L+1,R-1) (S[L]==S[R]の場合。S[L]!=S[R]の場合0) OutSum(L,R) = O…

包除原理を間違えた…。 http://agc005.contest.atcoder.jp/tasks/agc005_d 問題 1～NのPermutationである数列AはN!通りある。 このうち|A[i]-i|!=Kを満たす数列は何通りあるか。 解法 包助原理で解く。 N要素中、|A[i]-i|=Kとなる要素が少なくともx個あり、残り(N-x)個は未確定であるような数列の組み合わせをf(x)とする。 すると解はとなる。あとはf(x)を求められれば良い。 N要素を2*K個の組に…

…ばならない。 これは包除原理の要領で三角錐の足し引きをすればよい。 ll mo=1000000007; class TriangleTriples { public: ll tri(ll a) { if(a<1) return 0; return a*(a+1)%mo*(a-1)%mo*((mo+1)/6)%mo; } int count(int A, int B, int C) { if(A>B) swap(A,B); if(B>C) swap(B,C); if(A>B) …

…=1;i<=M;i++) { ll a = modpow(i,N)*combi(M,i)%mo; ret += ((M-i)%2==0) ? a : -a; } cout<<(ret%mo+mo)%mo<<endl; } まとめ 本番スターリング数云々は忘れてたけど、このパターンの包除原理はこんなもんだろうと適当に当てて解いてしまった。 これじゃ成長しないなぁ…。 (この記事書く前に包除原理こねくり回そうとしてうまく行かず、結局スターリング数をひっぱり出してしまった。反省。)

…数を答えよ。 解法 包除原理で解く。 Xの素因数をとする。 1～nの部分列として構成される数列iに対し、1～Nのうちでのすべてで割れ、残りの素因数で割れない正整数の数は個なので、kの偶奇に応じてこの値を加減算しよう。 あとは数列iの選び方(2^n)通りを列挙すればよい。 int T; ll X,N; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>X>>N; vector<ll> V;…

…N)になるのかな。 包除原理 他人のコードが何をやっているかわからなかったが、以下でわかった。 Topcoder Single Round Match 684 - Codeforces隣接要素の条件がなければ、数列の取り方はK^Nである。 ここから隣接要素の条件に反するケースを引こう。ここで重要な事実として、連続して隣接要素の条件に反するのは、高々logK要素までである。 隣接要素の条件に反するには、BがAの約数かつBがA未満でなければならない。 よって連続で条件に反する場合…

…の何れかで解ける。 包除原理の要領で、w[j]^w[i]通りの組み合わせのうち、w[j]個すべてに要素がマップされない組み合わせを削る。 ちょっと計算量が多く、定数倍高速化をしないと通らない。自分はインラインアセンブラで最初通した。 w[i]個をw[j]個に分ける分割数を求めたあと、w[j]の並べ方w[j]!を掛ける。 int N,M; int W[300]; int mat[300][300]; ll mo=1000000007; ll dp[1010][1010]; ll…

…n頂点グラフ)の分は包除原理の要領で処理できる。 n頂点のグラフのうち、1番の頂点を含む連結成分はx個(1≦x≦(n-1))だとする。 そのケースは、1番以外の(n-1)個の頂点から(x-1)個を選ぶ組み合わせと、残された(n-x)個が(連結か非連結かを問わず)次数が偶数の頂点を成すグラフを構成する組み合わせの積なので、通りである。 xを総当たりすると結局となる。 あとは上記DPをO(N^2)でやればよい。 ll mo=1000000007; ll modpow(ll a, …

…x)をどうするか。 包除原理でも解けるかもしれないが、DPしてしまった方が楽。 dp[最上位からの桁数][0-9の任意の値を取れるか否か][3の桁が登場済みか][各桁の和の3の余り][各桁の和の8の余り] := 条件を満たす整数の数 として上の桁から順にDPしていけばよい。 string A,B; ll mo=1000000007; ll dp[10101][2][2][3][8]; // digit, more, inc3, mod3, mod8 ll dodo(strin…

…);rit!=ndiv.rend();rit++) { rit->second=(P-1)/rit->first; ITR(it,ndiv) if(it->first>rit->first && it->first%rit->first==0) rit->second-=it->second; ret+=rit->second; } cout<<ret<<endl; } まとめ 前半のGCDに持って行く部分も、後半の包除原理にもっていく過程も自力じゃすんなり書けそうにないな。

…irst && P[x].second<=P[i].second) { dp[i] -= dp[x]*combi(P[i].first-P[x].first+P[i].second-P[x].second,P[i].second-P[x].second)%mo; } dp[i]=((dp[i]%mo)+mo)%mo; } cout<<dp[N]<<endl; } まとめ 一見O(2^N)に見えてO(N^2)に出来る包除原理、苦手意識があったけど今回自力回答できて少し自信回復。

最近O(2^N)系の包除原理の苦手意識が消えてきたと思ったけど、O(N^2)な包除原理はやっぱり苦手。 http://yukicoder.me/problems/643 問題 基本設定は(1)と同じ。 今度は条件を満たす割り振り方の組み合わせ数を求めよ。 解法 Editorialを見て解いた。出席番号iを嫌いな生徒数をf(i)とする。 0～(N-1)の部分集合Sで衝突(出席番号がその番号を望まない生徒に割当たっている)するような組み合わせは、となるので、これを包除原理の要領で…

…カウントしないよう、包除原理の要領で数え上げていく。 vector<ll> enumdiv(ll n) { vector<ll> V; for(ll i=2;i*i<=n;i++) { if(n%i==0) V.push_back(i); while(n%i==0) n/=i; } if(n>1) V.push_back(n); return V; } int N,Q; int A[202000]; int on[202000]; ll non; int num[502000…

…がかかるので、うまく包除原理を使いp^2で処理していく。 このあたりは以下のForumを参考にすると良い。 TopCoder Forumsなお、上記Forumの記載は一部ミスがあるね。 N=9, pos=2,4,5の場合、V=[2,2,1,4]になるので解は じゃないかな。 上の式を見ると、どう包除原理で解けるか想像つくね。 階乗の個数の偶奇で符号の正負が反転してる。 ll mo=1000000007; ll dp[3000]; const int NUM_=1000001;…

…で離脱したのだけど、包除原理で混乱していたのであと１時間で101pt取れたかは微妙。 http://abc020.contest.atcoder.jp/assignments A - クイズ 問題番号1か2が与えられるので、それぞれ回答を返せ。問題内容は原文を見てもらうとして、"ABC"か"chokudai"を返せばよい。 print ["ABC","chokudai"][input()-1]; B - 足し算 ２つの整数A,Bが与えられる。 ２つの整数を連結したものを２倍し…

…{ ret -= area(XX[x+1]-XX[x],YY[y+fil[x][y]]-YY[y],min(j,pat[x][y])); y+=fil[x][y]-1; } else { ret -= area(XX[x+1]-XX[x],YY[y+1]-YY[y],min(j,pat[x][y])); } } cout<<ret<<endl; } } まとめ 包除原理を考えたのが失敗。 Nが1000な時点でそれはないと思ったが…。 座圧まで思いつけばあとは自力で解けたのに。

…る可能性があるので、包除原理の容量でそれらを減算していけば良い。 ll mo=1000000007; int R[501],C[501]; const int CN=601; ll CC[CN][CN]; ll dp[CN][CN]; class SquareOfSquareMatrix { public: int count(int n, vector <int> r, vector <int> c) { int i,j,y,x; vector<ll> p2; p2.pus…

…行えばよい。 自分は包除原理で解いた。 まず、以下をそれぞれ求める。 x=min(b,d,f)となる異なるb,d,fの組み合わせ数up_even(x) x=max(b,d,f)となる異なるb,d,fの組み合わせ数down_even(x) x=min(a,c,e,g)となる異なるa,c,e,gの組み合わせ数up_odd(x) x=max(a,c,e,g)となる異なるa,c,e,gの組み合わせ数down_odd(x) するとx＜yとなる各x,yについてdown_even(x)*u…

…[x]がわかり、後は包除原理の要領でS[0]を求めればよい。 P[x]の求め方は、一見O(K*M)かかりそうだが、bitごとの畳み込みを使うとO(K*logM)で処理できる。 巷では高速ゼータ変換とか呼ばれているようだ。 ll N,A[1<<21],P2[1<<21]; ll mo=1000000007; void solve() { int f,i,j,k,l,x,y; cin>>N; FOR(i,N) cin>>x, A[x]++; P2[0]=1; FOR(i,1<<2…

…められる。 ここから包除原理を使い、各種類の花がF[i]を超えるケースを除いていけばよい。各花の種類がF[i]を超えるかどうかをbitmaskで管理し、総当たりする。 bitmaskで超えると判定される種類は最低(F[i]+1)本の花を含むので、その分Sから(F[i]+1)を引いていく。 最終的に残った値をS'とすると、をbitmask1の1が立ったbit数で符号反転したものを足しこんでいけばよい。 int N; ll S,F[30]; ll mo=1000000007; l…

…持っていたとすると、包除原理より求める答えはg(x)=f(x,F)として とNを素因数奇数個で割った値に対する関数gの値を引いて、偶数個で割った値に対する関数gの値を足せばよい。 Nの計算を何度も行うので、事前に累積積を取っておき、CombinationをO(1)で計算できるようにしておこう。 計算量は各クエリで素因数分解するためO(Q*√N)。 int Q; int N[100001],F[100001]; ll mo=1000000007; //同一の要素を複数含まない素…

…事前に求めた累積和と包除原理を適用することで(N*maxR*maxG*maxB)まで計算量を落とすことができる。 double dpdp[2][51][51][51]; double sum[4][55][55][55]; class RandomColoring { public: double calc(int r2,int r1,int g2,int g1,int b2,int b1) { double ret=0; int r,g,b; if(r1>r2 || g1>…

…ごとに数を求める。 包除原理の考え方から、まずは重なりを無視してそれぞれの左下マスから生成できる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…