…組み合わせとする。 包除原理より、解は全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…

…るケースを足して…と包除原理の要領で考えていくと、解は となる。あとはE[i]を求めよう。iの各ビットを含まない値が出る確率をP[i]とすると、E[i]＝1/(1-P[i])である。 P[i]は高速ゼータ変換で求められる。 int N; int A[1<<18]; ll SA[1<<18],E[1<<18]; ll S; const ll mo=998244353; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r…

…は何通りか。 解法 包除原理で解く。 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)の積なので、いわゆるマージテクの要領で小さい順…

…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; } まとめ 組み合わせや包除原理にとらわれすぎた。

…必要がある。そこで、包除原理の要領で、それぞれの条件を満たす組み合わせを求めよう。 片方の条件を満たすには、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…

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

…めることを考えよう。包除原理を考えると、となる。 ただこれだと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; …

…しない) とする。 包除原理の要領で、上記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_…

…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; } まとめ 途中包除原理とか考えてしまったけど必要なかったね。

…値を求めよ。 解法 包除原理を考えると、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乗になる…

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

…>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; } まとめ 包除原理よりこっちのほうが楽な気はする。

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