…エーションについて、包除原理により、同じ領域を占める場合の木の配置パターンを数え上げる。 ll N,M,K; const int 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; } template <class T> using vec=vector<T>; //using vec=valarra…

…サイズである。これは包除原理の要領で、xorは共通部分に置き換えることができる。 Aの部分集合A[a],A[b],A[c]....のうち、素因数分解したときの各要素の2の位数と3の位数が、要素間で1以下であればS[A[a]]とS[A[b]]とS[A[c]]…の要素が正となる。 そのようなAの部分集合の選び方を総当たりしよう。 ll L; int N; ll A[1010]; int p2[1010],p3[1010]; const int prime_max = 200000…

…は何通りか。 解法 包除原理を考える。 f(x)をx文字の正しい括弧列の数とする。例えばn個の区間が正しい括弧列であるようなものは、区間長に対応する列をAとすると、 (-f(A[0]))*(-f(A[1]))*....*(-f(A[n]))*f(N-sum(A)) だけ解に寄与する。 これをFFTで解こう。 M個の区間の区間長をBとすると、多項式 (1-f(B[0])*x^(B[0]))*(1-f(B[1])*x^(B[1]))*....*(1-f(B[M-1])*x^(B[…

…subsetに関する包除原理で計算できる。 また、n+1回目のカードを引く確率は(1-p(n))なので、解はこの値を各nに対し総和をとったものとなる。 式変形するとこの総和は、(1-x^(C[v]))の積を用いて表現できるので、FFTでこの多項式の係数を求めよう。 int N,M; int C[202020]; const ll mo=998244353; ll modpow(ll a, ll n = mo-2) { ll r=1; a%=mo; while(n) r=r*(…

…以上存在する条件は、包除原理で解ける。結局で良い。 const 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 comb(ll N_, ll C_) { const int NUM_=1400001; static ll fact[NUM_+1],factr[NUM_+1],inv[…

…されているケースを、包除原理の要領で省いていこう。各クエリに対しては、各dp(x,y)に対し、追加したランタンがx,yの着目点を両方カバーしないような強さの範囲を求めればよい。 int D,N,M,Q; int L[202020],P[202020]; ll dp[20][20]; ll dpL[20]; ll dpR[20]; const ll mo=998244353; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(…

…は何通りか。 解法 包除原理で解く。 f(bitmask) := 使ってよい辺の色がbitmaskの範囲内であるときの全域木の数 とすると、bitmaskのうちビットが立っている数の偶奇に応じてf(bitmask)を足し引きすればよい。 全域木の数は行列木定理で計算できる。 int N,K; vector<pair<int,int>> E[5]; const ll mo=998244353; ll modpow(ll a, ll n,ll mo) { ll r=1; whil…

…Bのバリエーションは包除原理で表現出来、無限和を取る過程があるのでe^iが登場する。 ll N; const ll mo=998244353; const int NUM_=2000003; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; 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; retur…

…い。 これをもとに、包除原理の要領で、そのような多重数え上げを回避しよう。 同じ重さとする重りの集合に対し、その集合内の重りの間の判定組はすべて縮約関係とした場合、連結成分数の偶奇に応じて組み合わせを加減算するとよい。 int N,M; vector<pair<int,int>> E; ll dp[1<<17]; const ll mo=998244353; template<int um> class UF { public: vector<int> par,rank,cn…

…たす数列の長さの総和包除原理の要領で、条件に違反する隣接要素対の偶奇に応じ、加減算しよう。 f(i) := 同じ整数をL個並べて総和がiとなる整数列のうち、(-1)^(L-1)を取った総和 g(i) := 同じ整数をL個並べて総和がiとなる整数列のうち、L*(-1)^(L-1)を取った総和dp0(i-j)の状態の数列の末尾にjを追加するとdp0(i)になる、と考えると、以下のように遷移する。 dp0(i)、dp1(i)はそれより小さな添え字の値だけに依存するので、分割統治+F…

…い。 次数2の点は、包除原理の要領で、その点が隣接する2点と同じ色になるケースを考えて足し引きすればよい。 残すケースは、各点が次数3以上の場合であり、この際頂点数はM*2/3=20以下である。 あとはN=20以下の場合の彩色を考える。 同じ色を取ってよい点の組み合わせをK個集めて、N頂点を構成することを考える。 これはO(N*3^N)で解けるがN=20だと間に合わない。そこでO(N^2*2^N)に落とし込む必要がある。これはEditorialにある通り2^N個のN次式をたた…

…アを求めよ。 解法 包除原理と高速ゼータ変換で解く。 文字列集合に対し、各文字の頻度の最小値を取って、全文字列の部分列の個数を数えよう。 その後、包除原理と高速ゼータ変換を行えば、1個以上の文字列の部分文字列を数えることができる。 int N; int C[23][26]; ll dp[1<<23]; ll F[1<<23]; ll G[1<<23]; const ll mo=998244353; void solve() { int i,j,k,l,r,x,y; strin…

…B[i+1] 解法 包除原理の応用で、同じ値を持つ連続区間の個数が偶奇のケースを数え上げる。 dp[i][b] := i番目までのprefixの値を定めたとき、同じ値を持つ連続区間の個数の偶奇がbに一致するケースの数とする。区間[j,i]で同じ値を取ると、 dp[i][b] += dp[j-1][b^1] * min(A[j],...,A[i]) と遷移する。 i,jを総当たりするとO(N^2)かかるが、min(A[j],...,A[i])が同じ区間をスタックの要領でまとめて…

…合わせは、 となる。包除原理を考えると、d日ちょうどで全員から教わる組み合わせは となる。ユニークなC(i)の数は高々O(√N)通りしかないので、fは各dについて求めるのはO(N√N)で済む。 あとはNTTを使いf(d)からg(d)を求めよう。 int M,N,A[202020]; const ll mo=998244353; int C[101010]; map<int,int> D; ll P[101010]; const int NUM_=400001; static …

…は何通りか。 解法 包除原理で解く。 各頂点に子頂点がC個あるとき、親と子の1個が条件に違反するケースを考えると、各頂点における(1+Cx)の積をNTTで求めよう。 x^kの係数がaの時、少なくともk箇所で条件に違反する親子関係がある。 その場合の色の塗り分け方は(N-k)!通りである。 あとは包除原理でkの偶奇に応じてそれらの結果を加減算すればよい。 int N; vector<int> E[252525]; const ll mo=998244353; ll modpow…

…える。 解法 まず、包除原理の要領で、指定されたL色内における組み合わせを求められれば「最低1回」の条件は解決できる。あとはポリアの数え上げ定理の要領で、ラベルの並べ替え方Pに対し、同形となるグラフの数を数え、その平均を取ればよい。 PがM個のサイクル(要素数C1,C2,C3,....)で表現される場合、サイクル内は同じ色でなければならないので、色の組み合わせはL^M通り。 あとはサイクル内およびサイクル間の辺の有無を考えていこう。サイクル内に距離1～(|Ci|/2)の範囲の…

…数が奇数ならよい。 包除原理の要領で考える。 f(i) := N要素中i要素が平方数であり、残りi要素は平方数かどうかわからない とすると、求める値は である。 だが、右辺の無限級数の部分は と書ける。1/(1-x)^Nは、結局累積和をN回取ること、(1+x)^jは、符号を正負入れ替えながら累積和をj回取ること、と考えると、max(E)+1要素の数列を2N回累積和取れば、この分数の部分を計算できる。 int N,K; int E[101010]; const ll mo=10…

…M-j通りあるので、包除原理も考えると解はとなる。Editorialでは畳み込みを使うと書いてあるが、dを動かしたときのC(d+1,j)の総和はC(M+1,j+1)になることを使うと畳み込みを回避できる。 const ll mo=998244353; int N,M; ll comb(ll N_, ll C_) { const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact…

…組み合わせ とすると包除原理の要領で、 となる。第1種スターリング数s(n,i)を各iに対し一気に求めるのは、下記問題で既出である。 AtCoder ABC #247 : Ex - Rearranging Problem - kmjp's blog あとはG(i)を求められれば良い。 これはEditorialに従い、q-階乗を用いて、以下を計算しよう。右の総和の部分はNTTで計算できる。 ll N,B; const ll mo=998244353; const int NUM…

…'を列挙したうえで、包除原理と高速ゼータ変換で(mask & mask'')=mask'となるようなf(r,mask)とmask''を構成する確率の積和を求められる。 int N; int A[21]; const int mo=31607; int modpow(int a, int n = mo-2) { int r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } int C[1<<23];…

…となる。 ここから、包除原理の要領で、1つ目と2つ目の条件に違反するケースを足し引きしよう。 ll L,R,A,B,C; const ll mo=998244353; void solve() { int i,j,k,l,r,x,y; string s; cin>>L>>R; cin>>A>>B>>C; R-=L; if(R<C) { cout<<0<<endl; return; } __int128 w; if(C<=A+B) { C=A+B; R-=C; __int128…

…は何通りか。 解法 包除原理で解く。 f(n) := "RG"を確定でn個以上含む組み合わせ とすると、となる。g(n) := "RG"をちょうどn個含む組み合わせ とすると、これは包除原理で なのでg(K)を答えればよい。 int R,G,B,K; const ll mo=998244353; const int NUM_=4400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; ll comb(ll N_, ll…

…めるのは難しいので、包除原理で解く。 P(n) := 同じ色のボールの隣接箇所がちょうどn個あるボールの並び順 G(n) := 同じ色のボールの隣接箇所がn個以上あるボールの並び順隣接箇所をどの色から何個選ぶかを考えると多項係数を含む式が出てくる。 色毎に選ぶ個数に対する母関数を考え、FFTでそれらの積を取るとG(n)が求められる。 また、さらにFFTでG(n)に対し包除原理を適用するとP(n)が求められ、P(n)からA(n)が求められる。次にA(n)からf(k)を求めること…

… あとはこのB_Kに包除原理を施せば、Editorialにある「|P[i]-P[i+1]|=MとなるiがちょうどK個あるようなPの組み合わせ」を得られる。この包除原理は、NTTを使いO(NlogN)で行うことができる。 (コード中コメントアウトしてる部分は、愚直にO(N^2)掛けているケースである) int N,M; const ll mo=998244353; const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+…

…)、g(K+2)…を包除原理の要領で足し引きしてf(x)を求めよう。 g(1)、g(2)、…g(x)はEditorialの公式でまとめてO(x)で求められるし、x個の辺の選び方もまとめてO(x)で求められる。 ll M,K; const ll mo=1000000007; ll from[53][53]; ll to[53][53]; ll G[505050]; const int NUM_=1400001; static ll fact[NUM_+1],factr[NUM_…

…上げとなる。 これは包除原理の要領で2^(N+1)通り、条件に違反する国が確定されているケースを数え上げよう。 ここでは任意modにおける重複組み合わせBinom(p,q)を求める必要があるが、qが高々(N+1)個なので、p～(p-N)を並べて、1～(N+1)それぞれで割った後にp～(p-N)の積を取れば、任意modにおける除算を避けることができる。 ll mo; ll comb(ll N, ll C) { if(N-C<C) C=N-C; vector<int> V; in…

…る回数の偶奇をもとに包除原理を適用する。1以上K以下の降下列で、要素毎に2以上減少するような数列Aを数え上げよう。 f(L,R,mask) := 多項式で、n次の係数は以下を満たすn要素の数列の個数に相当する L以上R未満の降下列で、要素毎に2以上減少する maskは、数列中にLを含むかどうか、および(R-1)を含むかどうかの2*2通り まず分割統治法の要領で、f(1,K+1,*)を求める。 次に以下の多項式を考える。これらはf(1,K+1,*)から求められる。偶数次数の符号…

…の6次元配列を考え、包除原理の要領で累積和を取る。 高速ゼータ変換の要領で累積和を取る 以下のコードは前者。 前者の方がO(2^|n|)程度重いが一応間に合う。 int N; int A[1010101],B[1000000][6]; int C[1010101]; int S[10][10][10][10][10][10]; void solve() { int i,j,k,l,x,y; string s; cin>>N; ll ret=0; FOR(i,N) { cin>…

…。 解法 行について包除原理を行う。 H行中i行はすべて0であったとする。各列が非0である条件は、残り(H-i)行のどこかに1が1個以上あればよい。 よってiを総当たりし、Comb(H,i) * (-1)^i * (2^(H-i)-1)^W の和を取ればよい。 int H,W; const ll mo=1000000007; ll comb(ll N_, ll C_) { const int NUM_=2400001; static ll fact[NUM_+1],factr…

…期待値+1とすると、包除原理より解はsum*1となる。 f(S)の状態が崩れるのは、S中で初期位置より時計回りまたは反時計回りの最寄のマスが黒く塗られる時である。逆に、|S|が3以上の時、その最寄りの1または2マス以外の有無は、f(S)の値に影響しない しかし、それらの最寄りの1または2マス以外に、間にもともと塗られていないマスがあったとしても、その有無は、包除原理の過程で(-1)の偶奇に対応するため、そのようなマスが存在すると互いに相殺して最終的な解に寄与しない。 Sのうち…