…組み合わせ とすると包除原理の要領で、 となる。第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のうち…

…組み合わせとする。 包除原理より、解は全Sにおけるf(S)*(-1)^|S|となる。LCM(mask) := {1,...,N}の部分集合に対応するbitmask値のmaskに対し、それらの要素番号iに対するA[i]のLCMを g(mask) := {1,...,N}の部分集合に対応するbitmask値のmaskに対し、floor(M/LCM(mask)) とする。h(n) := n頂点の完全グラフの部分グラフにおいて、n頂点が連結であるとき、(-1)^(辺の数)の総和 とす…

…てもよい とすると、包除原理の要領で sum(g(m)*binom(N,m)*(-1)^(N-m) が解となる。f(m,l) := m個の庭に、l番目の種類の苗を植える植え方。余った苗があってもよい。 とすると、g(m)=f(m,1)*f(m,2)*f(m,3)となる。 あとはf(m,l)を植える植え方を考えよう。 mが苗の個数以下なら、各庭にその苗を植えても植えなくても良いのでf(m,l) = 2^mである。 mが苗の個数より多い場合、例えばその苗の個数をPとするとf(m,…

…7通りを総当たりし、包除原理の要領でf(y)を加減算していこう。 ll mo=1000000007; ll H,W; ll A[3030303]; vector<int> P[3030303]; void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W; ll ret=0; // 横と縦 ret=((W-1)*H+(H-1)*W)%mo; for(y=1;y<=H-1;y++) A[y]=H-y; for(y=1;y<=300…

…は、Mが小さいので、包除原理で解こう。 すなわち、M個の条件のうち違反することが確定する条件を列挙したとき、その条件を満たす組み合わせを計算できればよい。 これは上述のg(x,y)を使えばO(1)で求めることができる。 int N,M; int L[303030],R[303030]; int A[21],B[21]; int S[303030]; int T[303030]; int sel[303030]; ll num[303030][41]; const ll mo=…

…当たりする。 ただし包除原理の要領で、 bを素因数分解したとき、次数が2以上の素因数があるようなbは無視する。 bを素因数分解したとき、素因数の数の偶奇によって、(floor(vのb乗根)-1)をf(v)に加減算する。 int T; ll K; ll num(ll v) { ll sum=1; for(int i=2;i<=60;i++) { int num=1; int x=i; for(int j=2;j<=i;j++) if(x%j==0) { num*=-1; if(…

…通りあると考えると、包除原理の要領で解は である。あとはf(x)を求めることを考えよう。N頂点からなるグラフで、P[i]-Q[i]間に辺を張ったものを考える。 R[i]=P[i]またはR[i]=Q[i]となるR[i]を選択するということは、辺の両端の点のいずれかを選択するということである（2つの辺で1つの点を共に選択することはできない)。 この考えをもとに、x個選択することを考える。このグラフの各連結成分は、単一の点で自己ループを成すであるか閉路を成すものである。 単一の点に…

…塗り分け方 とすると包除原理の要領でと計算できる。あとはxを総当たりしながら、g(x)を考えよう。 適当な頂点を根として考えたとき、 dp(v) := vのsubtree及び(根頂点以外では)親方向の辺において、条件を満たす塗り方の組み合わせを考えると、vの子頂点cに対し、dp(v) = prod(dp(c))から過半数条件に違反するケースを引けばよい。 違反するケースは、辺の色が何本一致するかを総当たりし、過半数かつ全数でないケースを処理すればよい。 int N,C,M; …

…あとはf(1,*)を包除原理の要領で加減算していく。 int N; int P[2020]; vector<int> E[2020]; int C[2020],D[2020]; const ll mo=998244353; ll dp[2020][2020]; const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; ll pat[2020][2020]; ll comb(ll N_, l…

…をf(n)とすると、包除原理より解はsum*1である。 あとはf(n)を考えよう。g(r,c,n,br,bc) := 今(0,0)から(r,c)まで移動してきて、ここまで最低n回通行不可マスを経由しており、最後の通行不可マスと同じ行(br)及び同じ列(bc)かどうかのbool値に対応する。Aの組み合わせ及び経路の総和とする。Pの条件より同じ行または同じ列で2回以上通行不可マスを持つことはないので、brとbcがfalseで、他にr行目やc列目に通行不可マスがない場合、今いるマス…

…大18と小さいので、包除原理で解く。 Mの部分集合に対し、それらの辺に対応する頂点間に対応する要素同士はすべて和がZとなるケースを数え上げよう。連結成分毎に見て、 1要素だけの連結成分は、1～Kのどれでもよい 奇数長の閉路を持つ連結成分は、Zが偶数なら全要素Z/2しか条件を満たさない。奇数ならそもそも条件を満たさない。 2要素以上で二部グラフの場合、片方のグループをa、もう片方をZ-aとするケースを考えると、aの取りえる値がわかる。 あとは部分集合の要素数に応じて、組み合わせ…

…は何通りか。 解法 包除原理で解く。 そのような直線がK本以上あるケースを数え上げる。 M個の点を置き得るY軸に平行な線がP本、X軸に平行な線がQ本あるとする。 その組み合わせはComb(P*Q,M)*Comb(N,P)*Comb(N,Q)通りある。また、まだ残りの直線の配置は、Comb(2N-P-Q,K)通りある。 あとは、これらの積を、(K+P+Q)の偶奇に応じて足し引きする。 int N,M,K; const ll mo=998244353; ll dp[3030][3…

…が許可されないため、包除原理の要領でA[i]=0となるiの個数を総当たりしながら、上記を満たすA[x+1]～A[y]の組み合わせを数え上げよう。 int N; int B[101010]; const ll mo=1000000007; 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]…

…要素数を求めるには、包除原理の要領でf(i,1)-f(i,p1)-f(i,p2)-....+f(i,p1*p2)+f(i,p1*p3)+...を求めればよい。 const int prime_max = 1000001; vector<int> prime; int NP,divp[prime_max]; int N,Q; int A[101010]; vector<int> C[1010101]; int L[101010],R[101010],K[101010]; vec…

…る選び方 とすると、包除原理の要領でf(1)-f(2)+f(3)-f(4)....で求めることができる。f(i)の求め方だが、N要素の中から、(選ばない1要素)+(選ぶK要素)という(K+1)要素をi個選び、あとは残り(N-(K+1)i)要素から(M-(K+1)i)要素を選ぶケースを考えればよい。 ただし、先頭K要素を選ぶ場合のみ(選ばない1要素)は不要。 int N,M,K; const ll mo=998244353; const int NUM_=11400001; s…

…こを横断するケースを包除原理の要領で引いていく。 同じラインを複数回連続で横断するケースは考えなくてよいが2本のラインを交互に横断するケースは、その分包除原理の要領で足し引きする。 Kが大きいと交互に横断するケースはO(max(H,W)/K)程度なので全体でO(max(H,W)^2/K)で解ける。 const ll mo=998244353; ll comb(ll N_, ll C_) { const int NUM_=400001; static ll fact[NUM_+…

…箇所ある すると解は包除原理の要領でsum*1となる。dp(n,k)に対し、B[n+1]～B[m]を同じ値にすることで、dp(m,k+(m-(n+1))+=min(B[(n+1)...m])*dp(n,k)という遷移をすることができる。 ただこれを愚直に行うとO(N^2)かかる。 実質kは偶奇しか考慮しなくてよい。 あとはmin(B[(n+1)...m])*dp(n,k)の部分をスタックなど使いmin(B[(n+1)...m])を更新しながら累積和を計算していくとよい。 in…

…は何通りか。 解法 包除原理で解く。f(c) := K色中、c個以下を含むような組み合わせ とする。ボールの選択肢は、以下のM+c通りとなる。 選ばれないので、M色のどれでもよい。 選ばれるので、c色のどれかである。 とすると、f(c) = Comb(K,c)*(M+c)^Nとなる。f(c)がComb(M,K)回ずつカウントされると考えると、が解となる。 int N,M,K; const ll mo=998244353; ll comb(ll N_, ll C_) { con…

…列以下である置き方 包除原理の要領でf(x)を求められる。g(x)は、用いる列x個の選び方C(N,x)と、各行でどの列を選ぶかx^Nの積。 int N; ll 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; } ll comb(ll N_, ll C_) { const int…