kmjp's blog

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

包除原理 の検索結果:

AtCoder ACLBC : F - Heights and Pairs

ARC

…は何通りか。 解法 包除原理で解く。 P(x) := x^nの係数は、同じ整数がnペア確実にできている分け方(それ以上できているかもしれない) という多項式を考える。このn次の係数をPnとすると とすると、が解となる。あとはP(x)を求めよう。 入力にある数vがc個あったとする。 これらが0~floor(c/2)個ペアを構築したとすると、多項式P_c(x)のn次の項はn個ペアを作る場合としてとする。 P(x)は、この各P_c(x)の積なので、いわゆるマージテクの要領で小さい順…

yukicoder : No.1227 I hate ThREE

…tring s; cin>>N>>C; ll ret=0; if(C>6*N) { ret=C-(6*N); C=6*N; FOR(i,N-1) ret=ret*2%mo; } FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } dfs(0,0); FOR(i,C) ret+=dp[0][i]; cout<<ret%mo<<endl; } まとめ 組み合わせや包除原理にとらわれすぎた。

yukicoder : No.1138 No Bingo!

…必要がある。そこで、包除原理の要領で、それぞれの条件を満たす組み合わせを求めよう。 片方の条件を満たすには、Pが完全順列であればよくO(N)で求められる。 両者を共に満たす条件は、OEISにO(N)の簡単な漸化式が掲載されているのでこれを使おう。 A003471 - OEIS ll N; const ll mo=998244353; ll S[5]; ll A[202020]; ll B[202020]; void solve() { int i,j,k,l,r,x,y; s…

yukicoder : No.1116 Cycles of Dense Graph

…法 Mが小さいので、包除原理を考え、M辺のうちいくつかを通るサイクルを数え上げよう。 M辺のうち必ず使用する辺の集合を総当たりする。その際以下のケースは除外する。 必ず使用する辺だけで次数が3を超える点ができる。 必ず使用する辺だけですでにサイクルが1つできており、それ以外にも辺が余っている。 それぞれの組み合わせは以下の通り。 必ず使用する辺がない場合、使う頂点数を3以上で総当たりして通り。2で割るのは順不同にするため。 使用する辺が1個だけの場合、他に最低1点を通らないと…

yukicoder : No.1100 Boxes

…めることを考えよう。包除原理を考えると、となる。 ただこれだとf(i)を求めるのにO(i)かかるので、f(i)を一通り求めるとO(K^2)かかることになる。 式を変形すると となり、sumの部分はNTTに持ち込める。 int N,K; const ll mo=998244353; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; …

AtCoder ABC #172 : E - NEQ

ARC

…しない) とする。 包除原理の要領で、上記dp(x)が求められればが解となる。dp(x)は、N要素中x要素で値が一致し、その値はM個中x個選ぶことになる。 また、A,Bの数列中残り(N-x)要素は(M-x)個の値を順次選んでいけるので、 となる。 ll dp[505050]; int N,M; const ll mo=1000000007; const int NUM_=600001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_…

AtCoder ABC #167 : E - Colorful Blocks

ARC

…hile(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>K; ll sum=0; for(i=0;i<=K;i++) { sum+=comb(N-1,i)*M%mo*modpow(M-1,N-i-1)%mo; } cout<<sum%mo<<endl; } まとめ 途中包除原理とか考えてしまったけど必要なかったね。

yukicoder : No.983 Convolution

…値を求めよ。 解法 包除原理を考えると、pをbitmask表記でkを含むN未満の整数全部、qをbitmask表記でkを含むN未満の整数全部からkを除いたものとして、 B[k] = sum(A[p])^2 - sum(B[q]) としてkを大きい順に求めることができる。 sum(A[p])を高速ゼータ変換で求めたうえ、後半の除算をメビウス演算で求めればいずれもO(NlogN)で求められる。その後Bの全要素のGCDを取ればよい。 …この演算、結局Bの各要素はAの各要素の2乗になる…

ゆるふわ競プロオンサイト #3 : Yet Another Cake Division

…は何通りか。 解法 包除原理で解く。 C色以下で塗るケースを列挙しよう。 その際、グリッドの罫線部に着目し、左上角を(0,0)、右下角を(W,H)とする。 4色の塗り分け方は、左上から右下と左下から右上に線にそってそれぞれ分割したときの組み合わせに等しいのでComb(H+W,W)^2。 以降同様に1・2・3色以下のケースを求め増減させればよい。これらは上の4色に比べると単純な数え上げで計算できる。 ll mo=1000000007; ll comb(ll N_, ll C_)…

yukicoder : No.1001 注文の多い順列

…>V[1].size()) continue; if(x<V[0].size()) (dp[x+1][y]+=dp[x][y]*(cand0-(V[0].size()-x-1)))%=mo; if(y<V[1].size()) (dp[x][y+1]+=dp[x][y]*(cand1-y))%=mo; } } ll ret=0; FOR(i,N+1) ret+=dp[i][N-i]; cout<<ret%mo<<endl; } まとめ 包除原理よりこっちのほうが楽な気はする。

Codeforces ECR #073: G. Graph And Numbers

…は何通りか。 解法 包除原理で解く。 f(S) := S内の値が辺の値として登場することを許容するような組み合わせの数 とすると、解はf({0,1,2})-f({0,1})-f({0,2})-f({1,2})-f({0})-f({1})-f({2})となる。 ここで、辺の値を01反転することを考えるとf({0,1})=f({1,2})、f({0})=f({2})となる。 以下それぞれ考えよう。 f({0,1,2}) : 各点何を振ってもいいので2^N通り f({0}), f(…

AtCoder ABC #152 : F - Tree and Constraints

ARC

包除原理の良い練習。 https://atcoder.jp/contests/abc152/tasks/abc152_f 問題 N頂点の気をなすグラフが与えられる。 各辺を白黒に塗るとき、その塗り方は2^(N-1)通りある。 ここでM個の条件が与えられる。 各条件は指定された2頂点を結ぶ最短パスにおいて、1個以上の辺が黒くなければいけないことを意味する。 条件を満たす塗り方は何通りか。 解法 Mが小さいことを利用しよう。 M個のうちあるいくつかが条件に反している場合を数え、包…

TopCoder SRM 775: Div1 Easy Div2 Hard IterateOverACube

SRM

…えていこう。 これは包除原理の応用で1つの総和に対し組み合わせはO(1)で求められる。 総和が確定したら、同様に第1要素を総当たりしつつ第2・3要素の組み合わせをO(1)で数えていけばよい。 ll comb(int P_,int Q_) { if(P_<0 || Q_<0 || Q_>P_) return 0; ll p=1,q=1; Q_=min(Q_,P_-Q_); for(int i=1;i<=Q_;i++) p=p*P_, q=q*i,P_--; return p/q…

Codeforces ECR #067: F. Expected Square Beauty

…)が定まる。 これは包除原理で確率を求めることができる。 int N; int L[202020],R[202020]; ll P[202020]; ll mo=1000000007; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } ll hoge(int i) { if(i==0) return P[1]; ll t=1-…

第一回日本最強プログラマー学生選手権-予選-: F - Candy Retribution

…る個数を列挙しつつ、包除原理の要領で、求めよう。 仮にb個以上になる要素がp個とする。するとAの要素のうちa*M+b*p個分は割り当てが決まるので、残りを(N+1)人で割り振ることを考えると C(N-M,p)*H(N+1,x-(a*M+b*p))をpの偶奇に応じて足し引きしていくとよい。 ll N,M,L,R; ll mo=1000000007; ll ret; ll comb(ll N_, ll C_) { const int NUM_=700001; static ll …

TopCoder SRM 756 Div1 Hard Newgenerations

SRM

…20個しかないので、包除原理で求めよう。 隣接セルが4つ来るspecialセルが決まっていれば、その隣接セルはactiveでなければならず、残りはどうでもよい。 ll mo=1000000007; ll p2[5050]; vector<int> L; class Newgenerations { public: int count(vector <string> S) { int H=S.size(),W=S[0].size(); vector<vector<int>> V…

Codeforces #548 Div2 D. Steps to One

…先はxの約数なので、包除原理の要領で、1~Mが出たときGCDが各約数になるケースを数え上げていけばよい。 int M; ll mo=1000000007; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } ll dp[101010]; void solve() { int i,j,k,l,r,x,y; string s; ci…

yukicoder : No.802 だいたい等差数列

未だに包除原理が漢字変換できません。 https://yukicoder.me/problems/no/802 問題 整数N,M,D1,D2が与えられる。 以下を満たす整数列Aは何通りか。 AはN要素の単調増加列で、1~Mの範囲を取る。 隣接要素間の差はD1以上D2以下である。 解法 B[i] = A[i]-D1*(i-1)-1 とする。 するとBの隣接要素間の差は0以上(D2-D1)以下であり、かつ0~(M-(D2-D1)*(N-1))-1の範囲の値を取ることになる。D=D…

TopCoder SRM 748 Div1 Easy, Div2 Hard EraseToGCD

SRM

…)を答えればよい。 包除原理で解く。 f(k) := GCDがkの倍数になる組み合わせ、とすると、f(k)はS中のkの倍数の要素数mに対しf(k)=2^m-1となる。 g(k) := GCDがkの倍数になる組み合わせ、とするとg(k) = f(k) - g(2k) - g(3k) - ...なのでg,fを大きい順に求めていけばよい。 本番は後者で解いたが、前者の方が楽だね。以下のコードは前者。 ll dp[1010][1010]; ll mo=1000000007; clas…

Educational DP Contest : Y - Grid 2

…mjp's blog包除原理の要領で解く。 f(k) := 通ってはいけないマスを少なくともk個通過しつつ左上から右下に移動する方法 とすると、解はが解となる。 良く見ると、kの具体的な値は余り関係なくて、kの偶奇だけ考えればよい。そこで、まずN個のマスを左上に近い順にソートしよう。 dp(k, b) := k個目の通ってはいけないマスを通る通り方のうち、通ったマスの数の偶奇がb(even or oddの2値)であるような経路の組み合わせ これは直前のマスを総当たりすればO(…

Codeforces ECR #057: E. The Top Scorer

…t i,j,k,l,r,x,y; string s; cin>>P>>S>>R; ll ret=0; for(i=R;i<=S;i++) { for(x=1;x<=P;x++) { (ret+=comb(P-1,x-1)*modpow(x)%mo*hoge(S-i*x,P-x,i-1))%=mo; } } ret=ret*modpow(comb(S-R+P-1,P-1))%mo; cout<<ret<<endl; } まとめ 点数で包除原理やるかと思ったら、人数でやるのか…。

yukicoder : No.767 配られたジャパリまん

…数を答えよ。 解法 包除原理を駆使する。 以下の順でbitdpの要領求めていく。 f(mask) := maskで指定したマスを全て通る経路数を求める。mask以外のマスは通っても通らなくてもよい。 通るべきマスが指定されれば、左上に近い順に通るしかないので通る順も確定し、結果経路数も容易に計算できる。 g(mask) := maskで指定したマスを全て通り、maskで指定されないマスは通らない経路を求める。 これは高速メビウス変換の要領で求める。 h(mask) := ma…

yukicoder : No.764 浮動点

…を求めよう。すると、包除原理の要領で、求める面積は下記の通り。 P(0)を中心とする半径maxR1の円とP(N+1)を中心とする半径maxR2の円の共通部分 - P(0)を中心とする半径minR1の円とP(N+1)を中心とする半径maxR2の円の共通部分 - P(0)を中心とする半径maxR1の円とP(N+1)を中心とする半径minR2の円の共通部分 + P(0)を中心とする半径minR1の円とP(N+1)を中心とする半径minR2の円の共通部分 int N; int L[1…

Advent Calendar 2018 : ブログを書く速度を少しだけ上げる

…してくれる。 凸包・包除原理が固有名詞として認識されている。あいにく強連結成分分解は一般的な複数の単語に分割されてしまった。 AtCoder、SRM、Codeforcesあたりが固有名詞判定された。英単語も割と行けるようだ。 $ mecab -d /usr/lib/x86_64-linux-gnu/mecab/dic/mecab-ipadic-neologd/ 凸包を包除原理で強連結成分分解した 凸包 名詞,固有名詞,一般,*,*,*,凸包,トツホウ,トツホー を 助詞,格助…

Code Festival Team Relay 2018 : H - 最悪のバス停決定戦

…sk)の求め方だが、包除原理を用いてO(3^N)または高速ゼータ変換の要領でO(N*2^N)で処理できる。 前者だとおそらく間に合わないので後者を考える。まずdp(mask)となる条件として、(幸いにも)maskを2進数の値をみなすと、A人がこれらの回戦の勝者となりうるケースはComb(mask, A)である。 そこから、mask中A人を配置してみたけど、実際にはA人が配置されない回戦もあるケースを高速ゼータ変換で引いていくとよい。 int N,M,K; int A,B; c…

九州大学プログラミングコンテスト2018 : I - Buffalo

…X,Y)がKの約数 包除原理を用いて、前者を満たす組み合わせを、GCD毎に分類しよう。 前者は尺取り法の要領で求めることができる。 あとはGCDがKの約数になるものの総和が解。 int N,K; ll A[3010101]; ll SA[3010101]; ll P[3010101]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; FOR(i,N) cin>>x, A[x]++; ll ret=0; for(i=…

Codeforces #519 F. Make It One

…;j+=i) A[i]+=A[j]; } for(i=1;i<=7;i++) { for(x=300000;x>=1;x--) { dp[i][x]=comb(A[x],i); for(j=2*x;j<=300000;j+=x) dp[i][x]-=dp[i][j]; dp[i][x]=(dp[i][x]%mo+mo)%mo; } if(dp[i][1]) return _P("%d\n",i); } cout<<-1<<endl; } まとめ 包除原理に頭がいかなかった…。

CODE FESTIVAL 2018 Qual B : D - Sushi Restaurant

…ouble PS[2020]={}; FOR(j,M) { S[j+1]=S[j]+X[j]*dp[j][i]; PS[j+1]=PS[j]+dp[j][i]; } long double be=1e10; FOR(j,M) { be=min(be,(S[M]-S[j+1])-X[j]*(1-PS[j+1])+X[j]*PS[j]-S[j]); } ret+=be; } _P("%.12lf\n",(double)ret); } まとめ 包除原理苦手なのでこういうのしんどい。

HackerRank University CodeSprint 5 : E. Cube-loving Numbers

…数を求めよ。 解法 包除原理の要領で解く。 以下を考える。f(a) := N以下の正整数Xのうち、と書けるものの g(a) := N以下の正整数Xのうち、と書けるもののうち、取りえるa'の最大値がaであるもの解は なので、g(i)を求めればよい。 f(i)、g(i)は以下の関係があるので、f(i)、g(i)を大きい順に求めていこう。 int T; ll N; ll cnt[1010101]; void solve() { int i,j,k,l,r,x,y; string s…

AtCoder ARC #101 : E - Ribbons on Tree

ARC

…は何通りか。 解法 包除原理で解く。 辺集合Eのうち、絶対にパスが通過しない辺の集合をFとするペアの組み方をg(F)とする。 すると求める解はである。 g(F)は|F|+1頂点のペアの組み方なので、実際は辺の数のみで決まる。 |F|+1が偶数の場合、|F|!! |F|+1が奇数の場合、0 よって、DFSで葉の頂点から、子頂点との辺を残す場合と減らす場合について、以下を順次更新すればO(N^2)で求められる。 dfs(v,n,o) := vを根とするsubtreeにおいて、vと…