kmjp's blog

競技プログラミング参加記です

包除原理 の検索結果:

Codeforces #428 Div2 D. Winter is here

…和を求めよ。 解法 包除原理の要領で解く。 まず、A中にaの倍数が単純にf(a)個あったときを考える。 f(a)個中k個の要素の選び方を考えると、これらによるスコアの総和はとなる。 最後の総和の部分の式変形はWikipedia等に掲載されている。 二項係数 - Wikipediaaの係数の部分を考える。 実際はaの倍数がf(a)個あったとして、その部分集合のうちGCDがaより大きなものがあるかもしれないので、それを取り除こう。 としてg(a)を大きな順を求め、g(a)*aの総…

yukicoder : No.546 オンリー・ワン

…のdp(mask)を包除原理の要領で加減算していこう。 dp(mask)のうちmaskが1箇所だけビットが立っているものの和が解である。f(mask) := maskで示すbitmaskでセットされたiに対応するC[i]の最小公倍数 dp(mask) := [L,R]のうちf(mask)の倍数であり、かつ他のf(mask')の倍数ではないもの先にf(mask)を計算しておけば、maskとmask'を総当たりしてもO(4^N)なので間に合う。 maskとmask'が異なる場合で…

CSAcademy Round #32 : G. Sum of Powers

…; ll ret=0; for(i=1;i<=N;i++) { ll v=1; FOR(j,M) v=v*i%mo; for(j=1;j<=K && i*j<=N;j++) { ll pat = sp[K-j][N-i*j]; if(j+1<=K && i*(j+1)<=N) pat += mo- sp[K-(j+1)][N-i*(j+1)]; (ret += v*j%mo*pat)%=mo; } } cout<<ret<<endl; } まとめ 包除原理は思いつかなかった。

CSAcademy Round #31 : F. Tokens on a grid

…は限らない。 そこは包除原理の要領で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…

Codeforces ECR #020: F. Coprime Subsequences

…通りあるか。 解法 包除原理の要領でとく。 整数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,…

Codeforces #409 Div1 D. Varying Kibibits

…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) { …

TopCoder SRM 711 Div1 Medium OrderedProduct

SRM

…めればよい。 あとは包除原理の要領で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]==…

Mujin Programming Challenge 2017 : D - Oriented Tree

…であってよい)そこで包除原理で数え上げていく。 直径が奇数なので、中心となる辺を挟んだ2頂点を(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差があるケースの積…

TopCoder SRM 708 Div1 Medium PalindromicSubseq

SRM

…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…

AtCoder AGC #005 : D - ~K Perm Counting

ARC

包除原理を間違えた…。 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個の組に…

TopCoderOpen 2016 Round2B Easy TriangleTriples

SRM

…ばならない。 これは包除原理の要領で三角錐の足し引きをすればよい。 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) …

yukicoder : No.391 CODING WAR

…=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; } まとめ 本番スターリング数云々は忘れてたけど、このパターンの包除原理はこんなもんだろうと適当に当てて解いてしまった。 これじゃ成長しないなぁ…。 (この解説書く前に包除原理こねくり回そうとしてうまく行かず、結局スターリング数をひっぱり出してしまった。反省。)

lay_contest beta round 00001: D - 素

…数を答えよ。 解法 包除原理で解く。 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;…

TopCoder SRM 684 Div1 Medium DivFree、Div2 Medium DivFree2

SRM

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

yukicoder : No.329 全射

…の何れかで解ける。 包除原理の要領で、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…

TopCoder SRM 672 Div1 Medium AlmostEulerianGraph

SRM

…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, …

yukicoder : No.260 世界のなんとか3

…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…

Codeforces #210 Div1 D. Levko and Sets

…);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に持って行く部分も、後半の包除原理にもっていく過程も自力じゃすんなり書けそうにないな。

Codeforces #313 Div1 C. Gerald and Giant Chess

…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)に出来る包除原理、苦手意識があったけど今回自力回答できて少し自信回復。

yukicoder : No.243 出席番号(2)

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

Codeforces #305 Div1 C. Mike and Foam

…カウントしないよう、包除原理の要領で数え上げていく。 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…

TopCoder SRM 656 Div1 Medium PermutationCounts、Div2 Hard PermutationCountsDiv2

SRM

…がかかるので、うまく包除原理を使い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;…

AtCoder ABC #020 : Python練習編

ARC

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

dwangoプログラミングコンテスト予選 : E - 電波局

…{ 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な時点でそれはないと思ったが…。 座圧まで思いつけばあとは自力で解けたのに。

TopCoder SRM 644 Div1 Hard SquareOfSquareMatrix

SRM

…る可能性があるので、包除原理の容量でそれらを減算していけば良い。 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…

yukicoder : No.122 傾向と対策:門松列(その3)

…行えばよい。 自分は包除原理で解いた。 まず、以下をそれぞれ求める。 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…

Codeforces #257 Div1 D. Jzzhu and Numbers

…[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…

Codeforces #258 Div2 E. Devu and Flowers

…められる。 ここから包除原理を使い、各種類の花が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…

Codeforces #251 Div2 E. Devu and Birthday Celebration

…持っていたとすると、包除原理より求める答えは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; //同一の要素を複数含まない素…

TopCoder SRM 540 Div1 Medium RandomColoring

SRM

…事前に求めた累積和と包除原理を適用することで(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>…

TopCoder SRM 616 Div2 Hard TwoLLogo

SRM

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

TopCoder SRM 613 Div1 Medium RandomGCD

SRM

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

Codeforces #235 Div2. E. Olympic Games

…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…

TopCoder SRM 602 Div2 Hard BlackBoxDiv2

SRM

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

AtCoder ABC #003 : Python練習編

ARC

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

Codeforces #216 Div2. E. Valera and Queries

…んでいたりするので、包除原理で解けるかもしれないがちょっと面倒。 ここでは、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…