…～M番の点を含む。 包除原理の要領で、この２つに違反するケースを数え上げて行く。 このままだとO(N^2)かかるが、うまく式変形するとO(N)に持ち込める。 int T,N,M; 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; } ll comb(ll N_, ll C_) { co…

…率を求めよ。 解法 包除原理で解く。 色ごとに、G[i]と同じボールを選んでしまう個数とその組み合わせを母関数の形式で書き下そう。 あとはFFTでそれらをたたみこむと得られる多項式は、x^n次の項は少なくともn箇所G[i]と一致する色のボールを選んだ組み合わせとなる。 この係数を加減算すれば、１回もG[i]と一致しないケースを数えられる。 int N; int C[202020],G[202020]; const ll mo=998244353; const int gg=5…

…の個数を総当たりし、包除原理で数え上げる。 int N,M,K,L; const ll mo=998244353; ll comb(ll N_, ll C_) { const int NUM_=3030*4030; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==0) { inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = in…

…k個ある場合を考え、包除原理の要領で、kの偶奇によって組み合わせを加減算 f(n)(m+1),f(n)(m+2),....を引く int N; string S; const ll mo=998244353; ll p2[202020]; ll comb(ll N_, ll C_) { const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==0) { inv[1…

…は何通りか。 解法 包除原理で解く。 隣接させてはならない対をいくつか定め、それらの対がいずれも隣接するような並べ方を考える。 N点のグラフに対し、隣接させてはならない対となるアクリルスタンドに対応する頂点間に辺を引こう。 その際、閉路ができたり、次数が３以上の辺がある場合、条件を満たす並び方は存在しない。 そうでない場合、(連結成分数)!×2^(2要素以上からなる連結成分)の数だけ並べ方がある。 int N,M; int A[16],B[16]; const int NUM…

…値が何回倍化するか、包除原理をしながら数え上げて行けばよい。 ここから、倍化した回数を個別に数えず、数えるべき組み合わせの数をその分倍化することで、計算のオーダーを下げることができる。 int T,N,M,K; int R[5050],B[5050]; const ll mo=998244353; ll dp[5050]; ll pat[5050][5050]; ll W[5050]; ll comb(ll N_, ll C_) { const int NUM_=140000…

…は何通りか。 解法 包除原理で解く。 点i→点(i+1)点で切れ目があるとは、(i+1)番以降の白点のうち、i番以下の黒点につながる辺がない状態とする。 包除原理で、そのような切れ目の個数の偶奇に応じて組み合わせを加減算していく。 prefix n 点の白点数をW_n、黒点数をB_nとすると、以下の式のdp(2N)が解となる。 となる。 これは分割統治+FFTで計算できる。 int N; string S; const ll mo=998244353; int B[40404…

…s)(2m+s)) 包除原理の要領で、mとsが互いに素である場合を考えると、 f(N)=N/(2(m+s)(2m+s))の和 (ただしmとsは互いに素で、sは奇数) g(N)=N/(2(m+s)(2m+s))の和 (ただしmとsは互いに素で) G(N)=N/(2(m+s)(2m+s))の和とするとg(N)-f(N)=f(N/2)から、f(N)=g(N)-g(N/2)+g(N/4)+....であり、さらに となる。 あとはG(N)を高速に求められれば良い。これは平方分割風に行う…

…^3)となる。これを包除原理で状態を減らす。 先頭から要素を決めるのは同じだが、状態として末尾の値と、違反した箇所の個数の偶奇をもって計算していく。 int T,N,K; ll mo; ll dp[4040][4040][2]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N>>K>>mo; FOR(x,N+3) FOR(y,K+1) dp[x][y][0]=dp[x][y][1]…

…2+2)を考える。 包除原理の要領で、これらのマスを偶数回通りながら右下に行く回数から、奇数回通って右下に行く回数を考える。N個のマスに関していえば、分割統治法でFFTを使いながら各マスから各マスへの移動パターンを数え上げることができる。 その過程で、残りM個の各マスと他の(M+N-1)の移動パターンを数え上げて行こう。 int N,M; const ll mo=998244353; const int NUM_=1400001; static ll fact[NUM_+1]…

…うどmであるケースは包除原理などで求められる。 int T; ll N,M; const ll mo=998244353; ll P[122]; 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; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { c…

…は何通りか。 解法 包除原理で解く。 f(n) := n桁が一致している整数対の数(他の桁は一致してもしなくても良い) g(n) := ちょうどn桁が一致している整数対の数とすると、 g(n) = f(n) - C(6,n+1)*g(n+1) - C(6,n+2)*g(n+2) - .... - C(6,6)*f(6) で求めることができる。 ll A[202020]; ll C[11*11*11*11*11*11]; ll p10[7],p11[7]; ll ret[7];…

…エーションについて、包除原理により、同じ領域を占める場合の木の配置パターンを数え上げる。 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…