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

…えていこう。 これは包除原理の応用で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…

…)が定まる。 これは包除原理で確率を求めることができる。 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-…

…る個数を列挙しつつ、包除原理の要領で、求めよう。 仮に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 …

…20個しかないので、包除原理で求めよう。 隣接セルが４つ来る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…

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

未だに包除原理が漢字変換できません。 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…

…)を答えればよい。 包除原理で解く。 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…

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

…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; } まとめ 点数で包除原理やるかと思ったら、人数でやるのか…。

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

…を求めよう。すると、包除原理の要領で、求める面積は下記の通り。 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…

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

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

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

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

…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); } まとめ 包除原理苦手なのでこういうのしんどい。

…数を求めよ。 解法 包除原理の要領で解く。 以下を考える。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…

…は何通りか。 解法 包除原理で解く。 辺集合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と…

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