…はvを素因数分解し、包除原理の要領でvと素であるものを数え上げていく。 int N,M; int cnt[101010]; int num[101010]; 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; } void solve…

…。ここで、f(i)は包除原理の要領で、2^N通りの項の加減算で求めることができる。 この時、f(1), f(2), ...における各項の値は等比数列を成すので、2^N通りの項それぞれでその和を求めればよい。 class TestProctoring { public: double expectedTime(vector <int> p, vector <int> q) { vector<double> D; int N,i; N=p.size(); FOR(i,N) D.p…

…み合わせ とすると、包除原理より解Aは１回以下しか登場しないトッピングの数に応じて正負を切り替えつつ組み合わせを足しこみである。 あとはこのway(i)を求めよう。way2(i,j) := i個のトッピングについて、計j杯のラーメンで全トッピングが1回ずつ登場し、かつトッピングのないラーメンの存在しないトッピングの組み合わせ数 とすると、分割数と似た処理で要領でway2(i,j) = way2(i-1,j-1) + way2(i-1,j)*jで求まる。 あとは残りの(N-i)…

…素因数分解しておけば包除原理の要領で求めることができる。 const int prime_max = 1100000; int NP,prime[100000],divp[prime_max]; map<int,int> M; void cprime() { if(NP) return; for(int i=2;i<prime_max;i++) if(divp[i]==0) { //M[i]=NP; prime[NP++]=i; divp[i]=i; for(ll j=1LL…

…P(x)を求めたら、包除原理を用いてP(x)中のいくつかの要素を素因数とする数列の組み合わせの数を足し引きしていこう。 なお、最低1つはxを含まなければいけないので、全部が(x-1)以下となるケースを同様に求めて引くとよい。 int N,K; ll mo=1000000007; ll B[2020200]; const int prime_max = 2100000; vector<int> P[2020202]; int po[2020202]; ll modpow(ll …

…いけないので、そこは包除原理の要領でそういうケースを取り除いていこう。 int N,M; ll mo=1000000007; ll ret=0; const int prime_max = 1000000; int NP,prime[100000],divp[prime_max]; void cprime() { if(NP) return; for(int i=2;i<prime_max;i++) if(divp[i]==0) { //M[i]=NP; prime[NP++…

…exclusion 包除原理 22.4 Burnside’s lemma バーンサイドの補題 22.5 Cayley’s formula ケイリーの公式・Prüfer code 23 Matrices 行列 23.1 Operations 行列の和・積・累乗・行列式・逆行列 23.2 Linear recurrences 線形回帰・漸化式・フィボナッチ数列 23.3 Graphs and matrices 行列によるグラフ処理・パスの数え上げ・最短経路・キルヒホッフの定理 2…

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

…の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'が異なる場合で…

…; 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; } まとめ 包除原理は思いつかなかった。

…は限らない。 そこは包除原理の要領で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が与えられる。 ２つの整数を連結したものを２倍し…