Bài giải các bài thi đấu NOIP 2024

Vòng #9 - 2024.9.23

A. [P10849] Level

Đề bài

Cho một số lượng người và ghế trống, với cấp độ từ \(1\sim n\). Số lượng người và ghế trống ở cấp độ \(i\) lần lượt là \(b_i,a_i\). Phân mỗi người vào một ghế, nếu một người cấp độ \(i\) ngồi vào ghế cấp độ \(j\), sẽ tạo ra lợi ích \(\mathrm{sgn}(i-j)\). Hãy tối đa hóa tổng lợi ích.

Phạm vi: \(n\le 10^6\).

Phân tích

Cân nhắc tham lam, rõ ràng nên ưu tiên tối đa hóa số lượng ghép với \(j<i\). Có thể chứng minh điều này không tệ hơn bằng phương pháp điều chỉnh.

Sau đó, cố gắng giữ lại càng nhiều ghép với \(j=i\) càng tốt. Quét từ nhỏ đến lớn \(i\), mỗi \(i\) cố gắng ghép nhiều nhất có thể trong phạm vi \(j\in[1,i)\), ưu tiên ghép các cấp độ lớn hơn. Theo tư tưởng tham lam đơn giản, ghép các cấp độ lớn hơn chắc chắn tối ưu hơn, có thể sử dụng ngăn xếp để quản lý.

Độ phức tạp thời gian: \(\mathcal O(n)\).

Code mẫu

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
int n,soGhe[MAXN],soNguoi[MAXN],nganXep[MAXN];
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&soGhe[i]);
	for(int i=1;i<=n;++i) scanf("%d",&soNguoi[i]);
	int tongThuong=0;
	for(int i=1,j=0;i<=n;++i) {
		while(soNguoi[i]&&j) {
			int x=min(soNguoi[i],soGhe[nganXep[j]]);
			tongThuong+=x,soNguoi[i]-=x,soGhe[nganXep[j]]-=x;
			if(!soGhe[nganXep[j]]) --j;
		}
		nganXep[++j]=i;
	}
	for(int i=1;i<=n;++i) tongThuong-=max(0,soNguoi[i]-soGhe[i]);
	printf("%d\n",tongThuong);
	return 0;
}

B. [P10538] Route

Đề bài

Một thành phố có \(n\) điểm và \(m\) tuyến đường, mỗi tuyến có điểm bắt đầu, điểm kết thúc, thời gian bắt đầu, thời gian kết thúc và chi phí. Có \(q\) ràng buộc: trong khoảng thời gian \([l,r]\), có thể ăn miễn phí trên một tuyến đường nhất định, hoặc ăn tại một thành phố \(u\) với chi phí \(w_u\). Tìm đường đi ngắn nhất từ \(1\to n\) (phải thỏa mãn tất cả ràng buộc).

Phạm vi: \(n,m,q\le10^5\).

Phân tích

Xây dựng đồ thị trực tiếp để tìm đường đi ngắn nhất khá khó. Cân nhắc dp, với \(f_e\) là chi phí ngắn nhất để đi đến \(e\).

Sắp xếp mỗi tuyến đường theo thời gian bắt đầu hoặc kết thúc, thì quá trình chuyển chắc chắn là từ trước đến sau. Với mỗi cạnh \(i\), đặt điểm bắt đầu là \(x\), thời gian bắt đầu là \(s\).

Chúng ta cần tìm trong tất cả các cạnh \(j\) kết thúc tại \(x\), đặt thời gian kết thúc là \(t\), thì hệ số chuyển từ \(j\to i\) là \(f_j\) cộng với \(w_x\) lần số lượng ràng buộc trong khoảng \((s,t)\).

Chuyển đổi trực tiếp có độ phức tạp bình phương, cần tối ưu.

Chúng ta thấy hàm chi phí của việc chuyển đổi là số lượng ràng buộc trong khoảng thời gian, điều này rõ ràng thỏa mãn bất đẳng thức tứ giác, do đó có tính đơn điệu của quyết định.

Cân nhắc tối ưu hóa bằng nhị phân, mỗi khi tính toán \(f_i\) cho một cạnh mới \(i\), chèn \(f_i\) (làm quyết định) vào cấu trúc dữ liệu tại điểm kết của \(i\), và nhị phân trên miền giá trị để tìm \(x\) nhỏ nhất sao cho \(i\) là quyết định tối ưu cho \(x\), điều này khá đơn giản.

Khi truy vấn \(f_i\) của một cạnh, nhị phân trên cấu trúc dữ liệu tại điểm bắt đầu để tìm ra quyết định thuộc khoảng thời gian bắt đầu.

Khi nhị phân, cần thực hiện một số điểm hai chiều tĩnh, có thể sử dụng cây chủ tịch để duy trì.

Độ phức tạp thời gian \(\mathcal O(m\log^2 V)\).

Code mẫu

#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef vector<int> vi;
const int MAXN=1e5+5,V=1e9+5;
const ll inf=1e18;
struct CayPhanDoan {
	int tong,sum[MAXN*32],trai[MAXN*32],phai[MAXN*32];
	void chen(int u,int l,int r,int q,int &p) {
		sum[p=++tong]=sum[q]+1;
		if(l==r) return ;
		int mid=(l+r)>>1;
		if(u<=mid) chen(u,l,mid,trai[q],trai[p]),phai[p]=phai[q];
		else chen(u,mid+1,r,phai[q],phai[p]),trai[p]=trai[q];
	}
	int truyVan(int u,int l,int r,int p) {
		if(!p||u<=l) return sum[p];
		int mid=(l+r)>>1,s=0;
		if(u<=mid) s=truyVan(u,l,mid,trai[p]);
		return s+truyVan(u,mid+1,r,phai[p]);
	}
}	TR;
int n,m,q,canh[MAXN*2];
struct Doan {
	int l,r;
	bool operator <(const Doan &oth) const { return r<oth.r; }
}	khoang[MAXN];
struct Cung {
	int u,v,a,b,w;
}	canhDuong[MAXN];
int truyVan(int l,int r) {
	if(l>r) return 0;
	int i=upper_bound(khoang+1,khoang+q+1,Doan{l,r})-khoang-1;
	return TR.truyVan(l,1,V,canh[i]);
}
struct ds {
	int w;
	struct thongTin {
		int l,r,x; ll d;
	};
	vector <thongTin> q;
	ll f(const thongTin&p,int x) {
		if(p.x>x) return inf;
		return p.d+1ll*w*truyVan(p.x+1,x-1);
	}
	#define tl (q.back())
	void chen(int x,ll d) {
		thongTin z={0,0,x,d};
		while(q.size()&&f(tl,tl.l)>=f(z,tl.l)) q.pop_back();
		if(q.empty()) return q.push_back({x,V,x,d});
		int l=tl.l,r=tl.r,s=r+1;
		while(l<=r) {
			int mid=(l+r)>>1;
			if(f(tl,mid)>=f(z,mid)) s=mid,r=mid-1;
			else l=mid+1;
		}
		if(s<=V) q.back().r=s-1,q.push_back({s,V,x,d});
	}
	#undef tl
	ll tinh(int x) {
		if(q.empty()) return -1;
		int l=0,r=q.size()-1,i=r;
		while(l<=r) {
			int mid=(l+r)>>1;
			if(x<=q[mid].r) i=mid,r=mid-1;
			else l=mid+1;
		}
		if(x<q[i].x) return -1;
		return f(q[i],x);
	}
}	dp[MAXN];
ll giai() {
	sort(khoang+1,khoang+q+1);
	for(int i=1;i<=q;++i) TR.chen(khoang[i].l,1,V,canh[i-1],canh[i]);
	sort(canhDuong+1,canhDuong+m+1,[&](auto s,auto t){ return t.b<s.b; });
	dp[1].chen(0,0);
	for(int i=1;i<=m;++i) {
		ll f=dp[canhDuong[i].u].tinh(canhDuong[i].a);
		if(~f) dp[canhDuong[i].v].chen(canhDuong[i].b,f+canhDuong[i].w);
	}
	return dp[n].tinh(V);
}
ll giaiBaiToan(int N,int M,int W,vi T,vi X,vi Y,vi A,vi B,vi C,vi L,vi R) {
	n=N,m=M,q=W;
	for(int i=1;i<=n;++i) dp[i].w=T[i-1];
	for(int i=0;i<m;++i) canhDuong[i+1]={X[i]+1,Y[i]+1,A[i],B[i],C[i]};
	for(int i=0;i<q;++i) khoang[i+1]={L[i],R[i]};
	return giai();
}

C. [P10833] Permutation

Đề bài

Cho một dãy độ dài \(n\) là \(a_1\sim a_n\), đếm số lượng khoảng \([l,r]\) sao cho \(a_l\sim a_r\) là một hoán vị của \(1\sim r-l+1\).

Phạm vi: \(n\le 10^6\).

Phân tích

Cân nhắc CDQ chia trị, dùng hai điều kiện để mô tả một khoảng tốt:

• Giá trị lớn nhất trong khoảng bằng độ dài khoảng.
• Không có phần tử trùng lặp trong khoảng.

Đặt khoảng hiện tại là \([l,mid]\), độ dài \(i\) của hậu tố có giá trị lớn nhất là \(L_i\), khoảng \([mid+1,r]\), độ dài \(i\) của tiền tố có giá trị lớn nhất là \(R_i\).

Điều đầu tiên tương đương với \(i+j=\max(L_i,R_j)\), liệt kê \(j\) và chỉ định \(R_j\ge L_i\), ngược lại thì xử lý tương tự, lúc này \(i\) nằm trong một đoạn hậu缀 của \([l,mid]\), có thể tìm bằng con trỏ đôi.

Chỉ cần kiểm tra khi \(i=R_j-j\) có hợp lệ không, trước tiên kiểm tra \(R_j\ge L_i\), sau đó yêu cầu không có phần tử trùng lặp trong khoảng.

Nếu hai phần tử trùng lặp đều nằm trong \([l,mid]\), tìm cặp có vị trí phải nhất tương đương với việc giới hạn dưới của \(i\), tương tự nếu cả hai đều nằm trong \([mid+1,r]\] thì giới hạn trên của \(j\).

Sau đó xét phạm vi \([mid-i+1,mid]\) không được xuất hiện số giống trong phạm vi \([mid+1,mid+j]\].

Liệt kê \(j\) từ nhỏ đến lớn, tìm lần xuất hiện đầu tiên của mỗi \(a_{mid+j}\} ở bên trái, lại chuyển thành giới hạn dưới của \(i\), cuối cùng có thể kiểm tra trong \(\mathcal O(1)\).

Độ phức tạp thời gian \(\mathcal O(n\log n)\).

Code mẫu

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n,ans=0,a[MAXN],mx[MAXN],trai[MAXN],phai[MAXN];
void cdq(int l,int r) {
	if(l==r) return ans+=(a[l]==1),void();
	int mid=(l+r)>>1;
	cdq(l,mid),cdq(mid+1,r);
	mx[mid]=a[mid],mx[mid+1]=a[mid+1];
	for(int i=mid-1;i>=l;--i) mx[i]=max(mx[i+1],a[i]);
	for(int i=mid+2;i<=r;++i) mx[i]=max(mx[i-1],a[i]);
	int L=l,R=r;
	for(int i=mid;i>=l;--i) {
		if(trai[a[i]]) { L=i+1; break; }
		trai[a[i]]=i;
	}
	for(int i=mid+1;i<=r;++i) {
		if(phai[a[i]]) { R=i-1; break; }
		phai[a[i]]=i;
	}
	for(int i=mid+1,j=mid+1,p=L;i<=R;++i) {
		while(j>L&&mx[j-1]<=mx[i]) --j;
		if(trai[a[i]]) p=max(p,trai[a[i]]+1);
		if(1<=mx[i]-(i-mid)&&mx[i]-(i-mid)<=mid-max(j,p)+1) ++ans;
	}
	for(int i=mid,j=mid,p=R;i>=L;--i) {
		while(j<R&&mx[j+1]<mx[i]) ++j;
		if(phai[a[i]]) p=min(p,phai[a[i]]-1);
		if(1<=mx[i]-(mid+1-i)&&mx[i]-(mid+1-i)<=min(j,p)-mid) ++ans;
	}
	for(int i=l;i<=mid;++i) trai[a[i]]=0;
	for(int i=mid+1;i<=r;++i) phai[a[i]]=0;
}
signed main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	cdq(1,n),printf("%d\n",ans);
	return 0;
}

*D. [P10004] Inverse

Đề bài

Cho \(n\), đếm số lượng hoán vị \(n\) cấp sao cho với mọi \(x,y\in[0,n)\), thỏa mãn \(\sum[p_i<p_{i+1}]=x,\sum[p^{-1}_i<p^{-1}_{i+1}]=y\).

Phạm vi: \(n\le 500\).

Phân tích

Trước hết xét trường hợp chỉ có hạn chế \(x\), đây là số Euler, có thể dùng nghịch đảo nhị thức để chỉ định \(i\) vị trí đặt dấu \(<\), dãy ban đầu sẽ được chia thành \(n-i\) đoạn liên tiếp, mỗi đoạn tăng nghiêm ngặt.

Quay lại bài này, cân nhắc nghịch đảo nhị thức hai chiều, chỉ định \(i\) đoạn tăng liên tiếp trên \(p\), \(j\) đoạn tăng liên tiếp trên \(p^{-1}\), sau đó nghịch đảo nhị thức hai chiều để quay về.

Sau đó chỉ cần đếm số lượng hoán vị \(p\) có \(i\) đoạn tăng liên tiếp trên \(p\), \(j\) đoạn tăng liên tiếp trên \(p^{-1}\).

Quan sát hình thái của một đoạn tăng liên tiếp trên \(p^{-1}\), nếu đoạn này có chỉ số khoảng là \([l,r]\), thì trên \(p\) các phần tử có giá trị trong \([l,r]\) sẽ tăng theo chỉ số.

Do đó, với một đoạn tăng liên tiếp trên \(p^{-1}\), ta lần lượt chèn các khoảng \([l,r]\} tương ứng vào \(i\) đoạn tăng liên tiếp trên \(p\), chỉ quan tâm mỗi đoạn chèn bao nhiêu phần tử, dễ thấy mỗi cách phân bổ tương ứng với một hoán vị \(p\).

Vậy chúng ta cần đếm số lượng ma trận \(i\times j\) \(A\) mỗi hàng mỗi cột khác 0, và tổng số phần tử là \(n\).

Ở đây lại dùng bao hai chiều, tức là chỉ định \(a\) hàng \(b\) cột bằng 0, các hàng và cột còn lại không giới hạn, tương đương với việc chia trực tiếp, sau đó bao hai chiều mỗi chiều là được.

Độ phức tạp thời gian \(\mathcal O(n^3)\).

Code mẫu

#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace FastMod {
typedef unsigned long long ull;
typedef __uint128_t uLL;
ull b,m;
inline void init(ull B) { b=B,m=ull((uLL(1)<<64)/B); }
inline ull mod(ull a) {
	ull q=((uLL(m)*a)>>64),r=a-q*b;
	return r>=b?r-b:r;
}
};
#define o(x) FastMod::mod(x)
const int MAXN=505,MAXV=2.6e5+5;
int n,MOD;
ll C[MAXN][MAXN],giaiThua[MAXV],nhanGiaiThua[MAXV];
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
signed main() {
	scanf("%d%d",&n,&MOD),FastMod::init(MOD);
	for(int i=giaiThua[0]=1;i<MAXV;++i) giaiThua[i]=giaiThua[i-1]*i%MOD;
	nhanGiaiThua[MAXV-1]=ksm(giaiThua[MAXV-1]);
	for(int i=MAXV-1;i;--i) nhanGiaiThua[i-1]=nhanGiaiThua[i]*i%MOD;
	for(int i=0;i<=n;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {
		ll val=giaiThua[i*j+n-1]%MOD*nhanGiaiThua[i*j-1]%MOD*nhanGiaiThua[n]%MOD;
		for(int k=1;k<=i;++k) {
			if((i-k)&1) val=(val+MOD-C[i][k]*val%MOD)%MOD;
			else val=(val+C[i][k]*val%MOD)%MOD;
		}
		for(int k=1;k<=j;++k) {
			if((j-k)&1) val=(val+MOD-C[j][k]*val%MOD)%MOD;
			else val=(val+C[j][k]*val%MOD)%MOD;
		}
	}
	for(int i=0;i<n;++i) for(int j=0;j<n;++j) printf("%lld ",f[i][j]);
	puts("");
	return 0;
}

*E. [P10005] Prefix

Đề bài

Định nghĩa giá trị của một dãy độ dài \(n\) \(a\) là \(\prod_{i=k}^n s_i^{-1}\), với \(s_i\) là tổng tiền tố của \(a_i\).

Cho \(n,m,k\), tính tổng giá trị của tất cả các dãy độ dài \(n\), giá trị nằm trong \([1,m]\) và đôi một khác nhau.

Phạm vi: \(n,m\le 100,k\in\{1,2\}\).

Phân tích

Bắt đầu với \(k=1\), hàm chi phí là \(\prod s_i^{-1}\), trực tiếp duy trì không thể thực hiện được, cân nhắc thiết kế ý nghĩa tổ hợp và chuyển đổi.

Có thể thiết kế vấn đề như sau:

Với \(i\in[1,n]\), có \(a_i\) quả bóng màu \(i\), sắp xếp ngẫu nhiên chúng, yêu cầu lần xuất hiện cuối cùng của quả bóng màu \(i\) sớm hơn lần xuất hiện cuối cùng của quả bóng màu \(i+1\).

Cân nhắc chèn từng màu, xác suất tổng thu được chính là \(\prod_{i=1}^n \dfrac{a_i}{s_i}\).

Giả sử chúng ta đã xác định tập hợp không thứ tự của tất cả \(a_i\), thì với một sắp xếp của các quả bóng, chắc chắn có một hoán vị của \(a_i\) tương ứng thỏa mãn điều kiện (sắp xếp theo lần xuất hiện cuối cùng của mỗi màu).

Do đó, sau khi xác định tập hợp không thứ tự của tất cả \(a_i\), \(\sum\prod_{i=1}^n\dfrac{a_i}{s_i}=1\), do đó giá trị \(\prod s_i^{-1}=\prod a_i^{-1}\) trong trường hợp này.

Vậy chúng ta dp để tính tổng giá trị khi chọn \(n\) phần tử từ \(1\sim m\), chọn \(k\) phần tử có giá trị \(\dfrac 1k\).

Sau đó xét trường hợp \(k=2\).

Lúc này tương đương với việc nhân \(a_1\) vào đáp án.

Giả sử chúng ta chỉ định một tập \(a_1\sim a_n\), thì đáp án là xác suất sắp xếp hợp lệ nhân với \(a_1\), trước hết tính xác suất sắp xếp hợp lệ.

Lúc này \(a_1\) chắc chắn là màu có lần xuất hiện cuối cùng sớm nhất, điều này khó xử lý, cân nhắc bao trùm, tức là chỉ định một tập hợp \(B\) trong đó các phần tử có lần xuất hiện cuối cùng sớm hơn \(a_1\), đặt số quả bóng tương ứng là \(b_1\sim b_t\).

Tính số lượng phương án tương ứng, trước hết sắp xếp \(b_1\sim b_t\), sau đó chèn \(a_1\), cuối cùng chèn các phần tử khác, đặt \(S_B=\sum b_i\) thu được:

[\binom{S_B}{b_1,\dots,b_k}\binom{S_B+a_1-1}{S_B}\dfrac{A!}{(S_B+a_1)!\prod_{i\not\in B}a_i!} ]rút gọn thành:

[\binom{A}{a_1,a_2,\dots,a_n}\dfrac{a_1}{S_B+a_1} ]Lưu ý rằng chúng ta đang tính xác suất, do đó biểu thức phía trước biểu thị số lượng phương án cần chia.

Do đó, đóng góp của một tập \(B\) vào đáp án là \((-1)^{|B|}\dfrac{a_1}{S_B+a_1}\), đáp án là:

[\sum_a a_1\times \prod_{i\ne 1}\dfrac 1{a_i}\sum_B (-1)^B\dfrac{a_1}{S_B+a_1} ]Cân nhắc dp trực tiếp, đặt \(f_{i,j,s,0/1}\) là xét giá trị miền \([1,i]\), chọn \(j\) phần tử vào \(a\), \(S_B=s\), đã chỉ định \(a_1\) hay chưa.

Chuyển đổi bằng cách liệt kê \(i+1\) là không chọn, làm \(a_1\), đưa vào \(B\), đưa vào \(\overline B\) để chuyển.

Độ phức tạp thời gian \(\mathcal O(m^4)\).

Code mẫu

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=105,MAXS=1e4+5;
int n,m,k,MOD;
namespace k1 {
ll f[MAXN];
void giai() {
	f[0]=1;
	for(int i=1;i<=m;++i) for(int j=n;j;--j) f[j]=(f[j]+f[j-1]*nhanGiaiThua[i])%MOD;
	printf("%lld\n",f[n]);
}
}
namespace k2 {
int up[MAXN];
ll f[MAXN][MAXS][2],g[MAXN][MAXS][2];
void add(ll &x,ll y) { x=(x+y)%MOD; }
void giai() {
	for(int i=1;i<=m;++i) up[i]=(i<=n)?i*(i+1)/2:up[i-1]+n;
	f[0][0][0]=1;
	for(int i=1;i<=m;++i) {
		memcpy(g,f,sizeof(g));
		for(int j=0;j<n;++j) for(int s=0;s<=up[i-1];++s) for(int o:{0,1}) {
			ll &w=f[j][s][o]; if(!w) continue;
			add(g[j+1][s][o],nhanGiaiThua[i]*w); //chọn vào A
			add(g[j+1][s+i][o],(MOD-nhanGiaiThua[i])*w); //chọn vào B
			if(!o) add(g[j][s+i][1],i*w); //làm a[1]
		}
		memcpy(f,g,sizeof(f));
	}
	ll ans=0;
	for(int s=0;s<=up[m];++s) ans=(ans+f[n-1][s][1]*nhanGiaiThua[s])%MOD;
	printf("%lld\n",ans);
}
}
signed main() {
	scanf("%d%d%d%d",&n,&m,&k,&MOD);
	for(int i=1;i<MAXS;++i) nhanGiaiThua[i]=ksm(i);
	k==1?(k1::giai()):(k2::giai());
	return 0;
}

Vòng #10 - 2024.9.24

A. [P10524] Shift

Đề bài

Cho dãy độ dài \(2^n\) là \(a\), tìm một dịch vòng để tối đa hóa \(\sum a_i\operatorname{AND}i,\sum a_i\operatorname{OR}i,\sum a_i\oplus i\).

Phạm vi: \(n\le 20\).

Phân tích

Cân nhắc liệt kê brute-force kích thước dịch vòng, tức là mỗi lần dịch trái tất cả các phần tử một vị trí, duy trì ba đáp án.

Dùng Trie hỗ trợ toàn bộ \(+1\), từ cao đến thấp để duy trì, mỗi dịch vòng tương đương với việc trao đổi \(\mathcal O(n)\) cặp anh em trái/phải.

Chúng ta duy trì đóng góp tại tầng \(d\) của nút, khi push up chỉ cần đếm có bao nhiêu \(a_i\) bit thứ \(d\) là \(1\) ở cây con trái/phải, điều này đơn giản.

Độ phức tạp thời gian \(\mathcal O(n2^n)\).

Code mẫu

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1<<21;
int n,a[MAXN],chieuSau[MAXN],danhDau[MAXN],f[MAXN];
ll X[MAXN],Y[MAXN],Z[MAXN];
void chen(int p,int u,int x) {
	if(p>1) f[p]+=x>>(chieuSau[p]-1)&1;
	if(chieuSau[p]==n) return ;
	int c=u>>chieuSau[p]&1;
	chen(p<<1|c,u,x);
}
void capNhat(int p) {
	int k=chieuSau[p],s=1<<(n-k-1),ls=p<<1|danhDau[p],rs=ls^1;
	X[p]=X[ls]+X[rs]+((ll)(f[ls]+s-f[rs])<<k);
	Y[p]=Y[ls]+Y[rs]+((ll)f[rs]<<k);
	Z[p]=Z[ls]+Z[rs]+((ll)(f[ls]+s)<<k);
}
void quay(int p) {
	if(chieuSau[p]==n) return ;
	quay(p<<1|danhDau[p]),danhDau[p]^=1,capNhat(p);
}
signed main() {
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=2;i<(2<<n);++i) chieuSau[i]=chieuSau[i>>1]+1;
	for(int i=0;i<(1<<n);++i) cin>>a[i],chen(1,i,a[i]);
	for(int i=(1<<n)-1;i;--i) capNhat(i);
	ll sx=X[1],sy=Y[1],sz=Z[1];
	for(int i=1;i<(1<<n);++i) quay(1),sx=max(sx,X[1]),sy=max(sy,Y[1]),sz=max(sz,Z[1]);
	cout<<sx<<" "<<sy<<" "<<sz<<"\n";
	return 0;
}

B. [P10332] Order

Đề bài

Cho một cây \(n\) đỉnh, mỗi lần có thể thêm một đỉnh \(u\) kề với tập đã chọn (ban đầu phải thêm gốc), có xác suất \(1-p_u\) kết thúc ngay, ngược lại thu được lợi ích \(w_u\) và tiếp tục. Tối đa hóa kỳ vọng lợi ích.

Phạm vi: \(n\le 10^5\).

Phân tích

Nhân mỗi \(w\) với \(p\), kỳ vọng lợi ích là \(\sum_{i=1}^nw_j\prod_{j<i}p_j\).

Nếu không có hạn chế thứ tự tô pô, đây là vấn đề kinh nghiệm Exchange Argument, sắp xếp theo \(\dfrac{p_i-1}{w_i}<\dfrac{p_j-1}{w_j}\).

Trên cây chính là Exchange Argument trên cây, mỗi lần tìm đỉnh \(x\) có \(\dfrac{p_i-1}{w_i}\) nhỏ nhất và hợp nhất với cha \(y\), thu được \((p_x\times p_y,w_y+p_yw_x)\), dùng hàng đợi ưu tiên.

Do sử dụng xóa lười, cần duy trì số lần hợp nhất hiện tại của mỗi đỉnh để xác định có phải phiên bản mới nhất không.

Độ phức tạp thời gian \(\mathcal O(n\log n)\).

Code mẫu

#include<bits/stdc++.h>
#define ld long double
using namespace std;
const int MAXN=1e5+5;
struct thongTin {
	ld p,w; int id,s;
	friend bool operator <(const thongTin &u,const thongTin &v) {
		return u.w+u.p*v.w<v.w+v.p*u.w;
	}
}	a[MAXN];
int n,cha[MAXN],dsu[MAXN];
int tim(int x) { return x^dsu[x]?dsu[x]=tim(dsu[x]):x; }
signed main() {
	scanf("%d",&n);
	priority_queue <thongTin> Q;
	for(int i=1;i<=n;++i) cin>>a[i].w,a[i].id=i,a[i].s=1;
	for(int i=1;i<=n;++i) cin>>a[i].p,a[i].w*=a[i].p;
	for(int i=2;i<=n;++i) scanf("%d",&cha[i]),Q.push(a[i]);
	iota(dsu+1,dsu+n+1,1);
	while(Q.size()) {
		auto z=Q.top(); int u=z.id; Q.pop();
		if(z.s!=a[u].s||dsu[u]!=u) continue;
		int x=tim(cha[u]);
		a[x].w+=a[x].p*a[u].w,dsu[u]=x;
		a[x].p*=a[u].p,a[x].s+=a[u].s;
		if(x>1) Q.push(a[x]);
	}
	printf("%.18Lf\n",a[1].w);
	return 0;
}

*C. [P10042] Iterate

Đề bài

Cho lưới \(n\times m\), mỗi ô chứa \(0\sim 2\), một số ô chưa điền, cần điền vào \(0\sim 2\).

Một lưới sẽ trải qua nhiều vòng lặp, với ô chứa \(x\), nếu có ô kề 4 hướng chứa \(x-1\), thì sau vòng lặp ô này cũng sẽ thành \(x-1\), xét theo \(\bmod 3\).

Một lưới tốt khi và chỉ khi nó không lặp vô hạn, giá trị của nó là số lần lặp cuối cùng tại \((0,0)\).

Phạm vi: \(n\le 5,m\le 50\).

Phân tích

Cân nhắc bỏ \(\bmod 3\), đặt ma trận ban đầu là \(a_{i,j}\), tìm \(b_{i,j}\equiv a_{i,j}\pmod 3\) và hiệu các ô kề thuộc \[-1,1\]\).

Nếu xác định \(b_{1,1}\} thì \(a\) và \(b\) tạo thành song ánh.

Hoạt động trên \(a\) cũng sẽ diễn ra trên \(b\), và tình hình hoạt động trên \(a,b\) hoàn toàn giống nhau.

Do đó một ma trận \(b\) chắc chắn sẽ dừng lại, và tất cả các ô có giá trị nhỏ nhất sẽ không lặp lại, mỗi lần hoạt động sẽ biến các ô xung quanh thành giá trị đó.

Do đó đáp án là khoảng cách Manhattan nhỏ nhất từ các ô có giá trị nhỏ nhất đến \((0,0)\).

Vậy một ma trận \(a\) có thể tìm được \(b\) tương ứng thì chắc chắn là ma trận tốt, chúng ta lại thấy rằng ma trận \(a\) không tìm được \(b\) chắc chắn chứa một ma trận con dạng \(\begin{bmatrix}x&x\\y&z\end{bmatrix}\) sẽ giảm vô hạn, do đó chúng ta chứng minh được ma trận tốt và ma trận tồn tại \(b\) tương ứng là một một.

Với mỗi ma trận \(2\times 2\) kiểm tra tính hợp lệ là được.

Do đó câu hỏi đầu tiên có thể dp đơn giản, \(f_{i,s}\) là số lượng phương án với \(i\) cột trước có trạng thái \(s\), chuyển đổi bằng cách liệt kê đường viền cột thứ \(i+1\), độ phức tạp \(\mathcal O(m6^n)\).

Sau đó xét câu hỏi thứ hai, đặt \(b_{1,1}=0\), cần duy trì giá trị nhỏ nhất của \(b\), và khoảng cách nhỏ nhất từ tất cả các vị trí có giá trị nhỏ nhất đến \((0,0)\).

Nếu ghi nhận trạng thái còn phải duy trì \(b_{0,i}\), điều này không thể chấp nhận được, nhưng chúng ta chỉ quan hệ tương đối giữa giá trị \(b_{0,i}\) và giá trị nhỏ nhất, do đó có thể ghi nhận \(b_{0,i}-b_{\min}\).

Sau đó cần duy trì khoảng cách nhỏ nhất đến \((0,0)\), nếu ghi nhận trạng thái cần \(\mathcal O(n+m)\) thông tin là không thể chấp nhận được.

Cân nhắc kỹ thuật tương tự như trên, đặt khoảng cách nhỏ nhất là \(d\), chúng ta chỉ quan tâm mối quan hệ giữa \(d\) và một số \(j+i\), do đó có thể ghi nhận \(d-i\).

Và \(d\le i\) có nghĩa là các cột \(>i\) không thể trở thành điểm có khoảng cách Manhattan nhỏ nhất, do đó chỉ cần ghi nhận \(\max(0,d-i)\) là được, thông tin này chỉ có \(\mathcal O(n)\).

Do đó thiết kế trạng thái \(f_{i,j,k,s}\), \(j\) là \(b_{0,i}-b_{\min}\), \(k\) là \(\max(0,d-i)\) của số phương án, đồng thời ghi nhận \(g_{i,j,k,s}\} là tổng giá trị tương ứng.

Độ phức tạp thời gian \(\mathcal O(nm(n+m)6^n)\).

Code mẫu

#include<bits/stdc++.h>
using namespace std;
const int MAXN=60,MAXS=255,MOD=998244353;
const int pw[6]={1,3,9,27,81,243},d[3][3]={{0,1,-1},{-1,0,1},{1,-1,0}};
int n,m,Q,a[MAXN][5];
bool ok[55][MAXS],chuyen[MAXS][MAXS];
int v[MAXS],p[MAXS]; //tiền缀 nhỏ nhất, vị trí
int f1[MAXS][MAXN][5],f2[MAXS][MAXN][5];
//(màu cuối cùng, hiện tại min-a[i,0],mindis-i) {wys ans}
int g1[MAXS][MAXN][5],g2[MAXS][MAXN][5];
int laySo(int s,int i) { return s/pw[i]%3; }
void cong(int &x,int y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
void cong(int &x,long long y) { x=(x+y)%MOD; }
signed main() {
	ios::sync_with_stdio(false);
	cin>>n>>m,Q=pw[n];
	for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin>>a[j][i];
	for(int i=0;i<m;++i) for(int s=0;s<Q;++s) {
		ok[i][s]=true;
		for(int j=0;j<n;++j) ok[i][s]&=(a[i][j]==3||a[i][j]==laySo(s,j));
	}
	for(int s=0;s<Q;++s) {
		v[s]=p[s]=0;
		for(int i=1,k=0;i<n;++i) {
			k+=d[laySo(s,i-1)][laySo(s,i)];
			if(k<v[s]) v[s]=k,p[s]=i;
		}
		for(int t=0;t<Q;++t) {
			chuyen[s][t]=true;
			for(int i=1;i<n;++i) {
				int x=laySo(s,i-1),y=laySo(t,i-1),z=laySo(t,i),w=laySo(s,i);
				chuyen[s][t]&=!(d[x][y]+d[y][z]+d[z][w]+d[w][x]);
			}
		}
	}
	for(int s=0;s<Q;++s) if(ok[0][s]) f1[s][-v[s]][p[s]]=1,f2[s][-v[s]][p[s]]=p[s];
	for(int i=1;i<m;++i) {
		memset(g1,0,sizeof(g1)),memset(g2,0,sizeof(g2));
		for(int s=0;s<Q;++s) for(int j=0;j<=i+n;++j) for(int k=0;k<n;++k) for(int t=0;t<Q;++t) {
			if(!ok[i][t]||!chuyen[s][t]) continue;
			int w=(d[t%3][s%3]-j)-v[t],z=f1[s][j][k];
			if(!z) continue;
			if(w<0||(w==0&&k-1<=p[t])) { //giữ nguyên min
				cong(g1[t][j-d[t%3][s%3]][max(k-1,0)],z);
				cong(g2[t][j-d[t%3][s%3]][max(k-1,0)],f2[s][j][k]);
			} else { //min là hiện tại
				cong(g1[t][-v[t]][p[t]],z);
				cong(g2[t][-v[t]][p[t]],1ll*z*(i+p[t]));
			}
		}
		memcpy(f1,g1,sizeof(f1)),memcpy(f2,g2,sizeof(f2));
	}
	int s1=0,s2=0;
	for(int s=0;s<Q;++s) for(int j=0;j<=m+n;++j) for(int k=0;k<n;++k) {
		cong(s1,f1[s][j][k]),cong(s2,f2[s][j][k]);
	}
	printf("%d %d\n",s1,s2);
	return 0;
}

D. [P10010] Optimize

Đề bài

Cho \(a_1\sim a_n,b_1\sim b_n\), chọn một tập con \(S\) để tối đa hóa \(\sum_{i\in S}a_i\times \sum_{i\not \in S}b_i\).

Phạm vi: \(n\le 3000\), dữ liệu ngẫu nhiên.

Phân tích

Do dữ liệu ngẫu nhiên, cân nhắc một số thuật toán ngẫu nhiên, bắt đầu từ một trạng thái ngẫu nhiên và leo đồi, mỗi lần lật trạng thái của một điểm, nếu tốt hơn thì chuyển.

Nhưng rõ ràng như vậy không thể qua được, lợi dụng tính chất ngẫu nhiên của dữ liệu, chúng ta thấy rằng lúc này \(|S\) nên rất gần \(\dfrac n2\), do đó bắt đầu leo đồi từ một tập \(|S|=\dfrac n2\) là được.

Code mẫu

#include<bits/stdc++.h>
#define ll long long
#define LL __int128
using namespace std;
const int MAXN=3005;
mt19937 rnd(998244353);
int n,id[MAXN];
ll a[MAXN],b[MAXN];
bool s[MAXN];
void giai() {
	for(int i=1;i<=n;++i) cin>>a[i]>>b[i],id[i]=i;
	LL Z=0;
	for(int o=32;o;--o) {
		shuffle(id+1,id+n+1,rnd);
		LL A=0,B=0;
		for(int i=1;i<=n/2;++i) s[i]=0,A+=a[i];
		for(int i=n;i>n/2;--i) s[i]=1,B+=b[i];
		LL X=A*B;
		for(int q=62500;q;--q) {
			int x=rnd()%n+1;
			if(s[x]) {
				if(X<=(A+a[x])*(B-b[x])) s[x]^=1,A+=a[x],B-=b[x],X=A*B;
			} else {
				if(X<=(A-a[x])*(B+b[x])) s[x]^=1,A-=a[x],B+=b[x],X=A*B;
			}
		}
		Z=max(Z,X);
	}
	string z;
	while(Z) z+=Z%10+'0',Z/=10;
	reverse(z.begin(),z.end());
	cout<<z<<"\n";
}
signed main() {
	ios::sync_with_stdio(false);
	int T; ll A,B; cin>>T>>n>>A>>B;
	while(T--) giai();
	return 0;
}

*E. [P10001] Coupon

Đề bài

Cho \(n\) món hàng, mua theo thứ tự từng món, ban đầu có \(m\) phiếu.

Với món hàng thứ \(i\), cần tổng cộng \(a_i\) xu hoặc phiếu, trong đó phiếu tối đa dùng \(b_i\) cái, và mỗi lần trả \(c\) xu sẽ nhận được một phiếu (làm tròn xuống).

Tối thiểu hóa tổng số xu chi tiêu.

Phạm vi: \(n\le 10^6\).

Phân tích

Giả sử khi mua lần thứ \(i\) dùng \(x_i\) phiếu, thì số phiếu còn lại sau lần thứ \(i\} là \(s_i=m+\sum\limits_{j=1}^i \left\lfloor\dfrac{a_j-x_j}c\right\rfloor-x_j\), hạn chế duy nhất là \(\forall i\in[1,n+1]:x_i\le s_{i-1}\).

Cân nhắc giải quyết vấn đề này bằng tham lam.

Phân tích quá trình tăng số phiếu từ \(0\):

• Dùng \(a_i\bmod c\) phiếu đầu tiên: dùng bất kỳ số lượng nào cũng không làm giảm số phiếu nhận được, do đó tham lam dùng càng nhiều càng tốt.
• Tiếp theo mỗi lần dùng \(c\) phiếu, sẽ làm giảm số phiếu còn lại sau đó thêm \(-1\).
• Với số phiếu cuối cùng \(<c\), cũng sẽ làm giảm số phiếu còn lại sau đó thêm \(-1\).

Dễ thấy tất cả hoạt động đầu tiên rõ ràng tối ưu, sau đó là hoạt động thứ hai và thứ ba.

Vậy chúng ta trước hết thực hiện tất cả hoạt động đầu tiên, dễ thấy vị trí thực hiện chỉ tương đương với việc thay đổi \(m\), không có tính sau, do đó có thể thực hiện tùy ý, không妨 từ trước đến sau lần lượt lấy, tức là \(x_i=\min(a_i\bmod c,b_i,s_{i-1})\).

Sau đó chúng ta cần thực hiện một số hoạt động thứ hai, tức là tại một vị trí liên tục dùng \(c\) phiếu.

Chúng ta thấy rằng trong trường hợp này lợi ích giống nhau, vị trí sử dụng rõ ràng càng靠后 thì tính sau càng nhỏ, do đó từ sau đến trước tham lam lấy càng nhiều \(x_i\) càng tốt.

Lúc này tại vị trí thứ \(i\) số lần dùng \(c\) phiếu tối đa là \(\min\left(\left\lfloor\dfrac{b_i-x_i}c\right\rfloor,\left\lfloor\dfrac{s_{i-1}-x_i}c\right\rfloor,\min\limits_{i<j\le n+1}\left\lfloor\dfrac{s_{j-1}-x_j}{c+1}\right\rfloor\right)\).

Cuối cùng là tình huống thứ ba, chỉ cần xét số lượng phiếu còn có thể dùng tại mỗi vị trí \(\in[0,c)\).

Theo tham lam, chúng ta vẫn nên ưu tiên hoạt động có thể dùng nhiều phiếu nhất.

Đặt \(t_i=s_{i-1}-x_i\), số lượng phiếu tối đa có thể dùng tại vị trí thứ \(i\) là \(\min(b_i-x_i,t_i,\min_{i<j\le n+1}t_j-1)\).

Quan sát tính chất của cấu trúc này, chúng ta thấy rằng \(d_i=\min(t_i,\min _{i<j\le n+1} t_j-1)\) có tính đơn điệu, tăng theo \(i\), và trong suốt quá trình tham gia tính đơn điệu này luôn tồn tại.

Do đó cân nhắc mô phỏng quá trình này, từ lớn đến nhỏ liệt kê \(w=c-1\sim 0\), tìm tất cả vị trí có \(\min(d_i,b_i-x_i)=w\) và hoạt động.

Cân nhắc cách duy trì các vị trí này, trước hết các vị trí này rõ ràng thỏa mãn \(b_i-x_i\ge w\), và \(b_i-x_i\) là hằng số, do đó có thể offline, tại \(w=b_i-x_i\) chèn hoạt động \(i\), do đó chúng ta chỉ cần lấy tất cả các vị trí có \(d_i\ge w\) là được.

Và \(d_i\) giảm từ sau đến trước, do đó các \(i\) có \(d_i\ge w\) chắc chắn là một hậu tố của \(1\sim n\), dùng heap để duy trì tất cả các vị trí được chèn \(i\) của giá trị lớn nhất, có thể xác định có \(d_i\ge w\) hay không.

Dễ thấy chúng ta chỉ cần xử lý tất cả \(w\) bằng một số \(b_i-x_i\), các \(w\) ở giữa không cần quan tâm, chỉ cần tất cả \(d_i\) lớn hơn \(b_i-x_i\) tiếp theo đều hoạt động là được.

Chúng ta có thể dùng cây phân đoạn để duy trì động \(d_i\), chỉ cần cộng khoảng cộng khoảng nhỏ nhất là được.

Độ phức tạp thời gian \(\mathcal O(n\log n)\).

Code mẫu

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5;
int n,id[MAXN];
ll c,a[MAXN],b[MAXN],s[MAXN],x[MAXN],up[MAXN];
struct CayPhanDoan {
	ll tr[MAXN<<2],tg[MAXN<<2];
	void capNhat(int p,int k) { tr[p]+=k,tg[p]+=k; }
	void day(int p) { capNhat(p<<1,tg[p]),capNhat(p<<1|1,tg[p]),tg[p]=0; }
	void khoiTao(int l=1,int r=n+1,int p=1) {
		tr[p]=tg[p]=0;
		if(l==r) return tr[p]=s[l-1]-x[l],void();
		int mid=(l+r)>>1;
		khoiTao(l,mid,p<<1),khoiTao(mid+1,r,p<<1|1);
	}
	void cong(int ul,int ur,int k,int l=1,int r=n+1,int p=1) {
		if(ul<=l&&r<=ur) return capNhat(p,k);
		int mid=(l+r)>>1; day(p);
		if(ul<=mid) cong(ul,ur,k,l,mid,p<<1);
		if(mid<ur) cong(ul,ur,k,mid+1,r,p<<1|1);
	}
	ll truyVan(int ul,int ur,int l=1,int r=n+1,int p=1) {
		if(ul<=l&&r<=ur) return tr[p];
		int mid=(l+r)>>1; day(p);
		if(ur<=mid) return truyVan(ul,ur,l,mid,p<<1);
		if(mid<ul) return truyVan(ul,ur,mid+1,r,p<<1|1);
		return min(truyVan(ul,ur,l,mid,p<<1),truyVan(ul,ur,mid+1,r,p<<1|1));
	}
}	T;
void giai() {
	scanf("%d%lld%lld",&n,&s[0],&c);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for(int i=1;i<=n;++i) scanf("%lld",&b[i]);
	for(int i=1;i<=n;++i) {
		ll w=min({a[i]%c,b[i],s[i-1]});
		x[i]=w,s[i]=s[i-1]-x[i]+(a[i]-x[i])/c;
	}
	ll lim=s[n];
	for(int i=n;i>=1;--i) {
		ll w=min({(b[i]-x[i])/c,(s[i-1]-x[i])/c,lim/(c+1)});
		x[i]+=c*w,lim=min(lim-(c+1)*w,s[i-1]-x[i]);
	}
	for(int i=1;i<=n;++i) s[i]=s[i-1]-x[i]+(a[i]-x[i])/c;
	x[n+1]=id[n+1]=0,T.khoiTao();
	for(int i=1;i<=n;++i) id[i]=i,up[i]=min(c-1,b[i]-x[i]);
	sort(id+1,id+n+1,[&](int i,int j){ return up[i]>up[j]; });
	priority_queue <int> Q;
	for(int i=1,j;i<=n;i=j) {
		for(j=i;j<=n&&up[id[j]]==up[id[i]];++j) Q.push(id[j]);
		while(Q.size()) {
			int u=Q.top();
			ll z=min({up[u],T.truyVan(u,u),T.truyVan(u+1,n+1)-1});
			if(z>up[id[j]]) {
				Q.pop(),x[u]+=z,T.cong(u,u,-z),T.cong(u+1,n+1,-z-1);
			} else break;
		}
	}
	ll ans=0;
	for(int i=1;i<=n;++i) ans+=a[i]-x[i];
	printf("%lld\n",ans);
}
signed main() {
	int o; scanf("%d",&o);
	while(o--) giai();
	return 0;
}

*F. [P10062] Latin

Đề bài

Cho ma trận \(n\times n\), các phần tử của \(n\) hàng đầu tiên và \(C\) cột đầu tiên đã được cho, xây dựng một ma trận hoàn chỉnh sao cho mỗi hàng mỗi cột đều là hoán vị của \(1\sim n\).

Phạm vi: \(n\le 500\).

Phân tích

Trước hết xét trường hợp \(C=n\), lúc này tương đương với việc đã biết một số hàng hoàn chỉnh.

Lúc này chắc chắn có lời giải, có thể xây dựng từng hàng, xây dựng đồ thị hai phía, điểm bên trái là tất cả vị trí của hàng này, điểm bên phải là giá trị \(1\sim n\), nếu một vị trí có thể điền một giá trị thì nối cạnh.

Lúc này bậc của tất cả các điểm đều là \(n-R\), do đó đây là đồ thị hai phía chính quy, theo định lý Hall chứng minh luôn có ghép hoàn chỉnh, chứng minh luôn tồn tại ma trận.

Cân nhắc cách xây dựng, nếu không tìm ghép hoàn chỉnh cho từng hàng riêng lẻ, thì chúng ta cần phân tách đồ thị hai phía này thành \(n-R\) ghép hoàn chỉnh.

Thực tế đây là染色 cạnh nhỏ nhất của đồ thị hai phía, dưới đây đưa ra cách làm:

Định nghĩa染色 cạnh nhỏ nhất của đồ thị hai phía là dùng ít màu nhất để cho mỗi cạnh một màu, và các cạnh xuất phát từ một điểm hai hai khác màu.

Thực tế kích thước của nó là bậc lớn nhất của tất cả các đỉnh, đây rõ ràng là cận dưới, giờ đưa ra chứng minh xây dựng.

Cân nhắc lần lượt thêm cạnh \((u,v)\), nếu tập các màu chưa sử dụng của \(u,v\) có chung phần tử, trực tiếp đặt màu đó.

Ngược lại tùy chọn một màu \(x\) chưa sử dụng trong các cạnh xuất phát từ \(u\), và một màu \(y\) chưa sử dụng trong các cạnh xuất phát từ \(v\).

Tìm điểm \(w\) mà cạnh \((v,w)\) có màu \(x\), sau đó đặt cạnh \((v,w)\) thành màu \(y\), và đặt \((u,v)\) thành màu \(x\).

Lúc này có thể xuất hiện hai cạnh màu \(y\) tại \(w\), đặt cạnh kia thành màu \(x\), có thể chứng minh quá trình điều chỉnh như vậy trên đồ thị hai phía chắc chắn sẽ dừng lại.

Chứng minh về tính đúng và độ phức tạp thời gian của cấu trúc này:

Quá trình cấu trúc này chỉ thay đổi các cạnh màu \(x\) hoặc \(y\), nên tạm thời không xét các cạnh khác trên đồ thị.

Lúc này, bậc của mỗi điểm không vượt quá \(2\), do đó đồ thị lúc này gồm若干 chuỗi và vòng, và các cạnh trên chuỗi có màu \(x\),\(y\) xen kẽ.

Lại do \(u\) ban đầu không có cạnh màu \(x\), \(v\) ban đầu không có cạnh màu \(y\), do đó \(u,v\) đều là điểm cô lập hoặc một đầu của chuỗi.

Giả sử \(u,v\) là hai đầu của cùng một chuỗi, thì đầu của chuỗi này có màu \(y\), đầu kia có màu \(x\), do đó độ dài (số cạnh) của chuỗi này là chẵn; đồng thời do \(u,v\) nằm ở hai phía đồ thị hai phía, nên độ dài của chuỗi này là lẻ. Mâu thuẫn, do đó \(u,v\) là hai đầu của hai chuỗi khác nhau.

Dễ thấy cấu trúc này chỉ quét chuỗi của \(u\), do đó cấu trúc chắc chắn sẽ kết thúc, và chỉ quét \(O(n)\) cạnh.

Sau đó xét trường hợp \(C<n\), tương tự xây dựng đồ thị hai phía cho \(C\) cột đầu tiên, điểm bên trái bậc đều là \(n-C\).

Nếu điểm bên phải có bậc \(>n-C\), thì chứng minh rằng yếu tố này sẽ xuất hiện trong vùng \(R\times(n-C)\) nhiều hơn \(n-C\) lần, rõ ràng không có lời giải.

Ngược lại tương tự tìm một染色 cạnh là được.

Độ phức tạp thời gian \(\mathcal O(n^3)\).

Code mẫu

#include<bits/stdc++.h>
using namespace std;
const int MAXN=505;
struct haiPhia {
	int X,Y,g[MAXN<<1][MAXN];
	void khoiTao(int x,int y) {
		X=x,Y=y;
		for(int i=1;i<=X+Y;++i) memset(g[i],0,sizeof(g[i]));
	}
	void them(int u,int v) {
		v+=X;
		int x=1,y=1;
		while(g[u][x]) ++x;
		while(g[v][y]) ++y;
		g[u][x]=v,g[v][y]=u;
		if(x==y) return ;
		for(int w=v,z=y;w;w=g[w][z],z^=x^y) swap(g[w][x],g[w][y]);
	}
}	G;
int d[MAXN],a[MAXN][MAXN];
bool vis[MAXN];
void giai() {
	int n,R,C;
	cin>>n>>R>>C;
	for(int i=1;i<=n;++i) d[i]=R;
	for(int i=1;i<=R;++i) for(int j=1;j<=C;++j) cin>>a[i][j],--d[a[i][j]];
	for(int i=1;i<=n;++i) if(d[i]>n-C) return cout<<"No\n",void();
	G.khoiTao(R,n);
	for(int i=1;i<=R;++i) {
		memset(vis,false,sizeof(vis));
		for(int j=1;j<=C;++j) vis[a[i][j]]=true;
		for(int j=1;j<=n;++j) if(!vis[j]) G.them(i,j);
	}
	for(int i=1;i<=R;++i) {
		for(int j=1;j<=n-C;++j) a[i][j+C]=G.g[i][j]-R;
	}
	G.khoiTao(n,n);
	for(int i=1;i<=n;++i) {
		memset(vis,false,sizeof(vis));
		for(int j=1;j<=R;++j) vis[a[j][i]]=true;
		for(int j=1;j<=n;++j) if(!vis[j]) G.them(i,j);
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n-R;++j) a[j+R][i]=G.g[i][j]-n;
	}
	cout<<"Yes\n";
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) cout<<a[i][j]<<" \n"[j==n];
}
signed main() {
	ios::sync_with_stdio(false);
	int T; cin>>T;
	while(T--) giai();
	return 0;
}

*G. [P10433] Stop

Đề bài

Cho một đồ thị vô hướng \(n\) đỉnh \(m\) cạnh, một số đỉnh là "đỉnh dừng". Có \(k\) quân cờ ban đầu đặt tại \(a_1\sim a_k\).

Trò chơi sẽ diễn ra nhiều vòng, mỗi lần lần lượt xem xét quân cờ thứ \(1\sim k\), di chuyển nó đến một "đỉnh dừng" và dừng lại (không được đứng yên).

Với mỗi \(u\in[1,n]\), tìm di chuyển quân cờ thứ \(1\} đến \(u\), tổng khoảng cách di chuyển của tất cả quân cờ nhỏ nhất.

Phạm vi: \(n,m,k\le 5\times 10^5\).

Phân tích

Chúng ta thấy quân cờ thứ \(2\sim k\) ảnh hưởng đến đáp án không lớn, và chúng độc lập với nhau, các quân cờ này chỉ cần tối thiể hóa khoảng cách di chuyển riêng.

Giả sử chúng ta chỉ định tiến hành \(x\) vòng di chuyển, chúng ta cần tìm hàm \(f(x)\) của mỗi quân cờ, biểu thị khoảng cách di chuyển nhỏ nhất.

Chú ý rằng quân cờ này vòng đầu tiên di chuyển đến một "đỉnh dừng" ít nhất \(d\) bước, sau đó mỗi vòng có thể đi đến một đỉnh kề rồi quay lại, do đó mỗi vòng tối đa đi \(2\) bước.

Nếu muốn tốt hơn, thì phải đảm bảo mỗi vòng chỉ đi một bước, tức là đi đến hai "đỉnh dừng" kề nhau.

Đối với tất cả các đường đi đến "đỉnh dừng" kề, chúng ta quan tâm đến độ dài \(w\) và số vòng \(t\), lúc này \(x\ge t\) tồn tại một đường đi có giá trị \(x-t+w\).

Chúng ta thấy rằng \(x<t\) thì \(x-t+w\) không thể nhỏ hơn \(2x+d-2\), do đó chúng ta chỉ quan tâm đường đi có \(w-t\) nhỏ nhất nhất.

Chứng minh: chỉ cần chứng minh \(w-1\ge 2t+d-4\), tức là \(w-2t\ge d-3\).

Cân nhắc đường đi \((w,t)\) tương ứng, do là cặp "đỉnh dừng" đầu tiên kề nhau, do đó mỗi "đỉnh dừng" trên đường đi trước đó không có "đỉnh dừng" trong lân cận.

Do đó trên đường đi này có \(t\) "đỉnh dừng", điểm tiếp theo trên đường đi chắc chắn không phải "đỉnh dừng", do đó có thể lấy \(2t\) điểm ra.

Và đặt \(d'\) là độ dài từ điểm đầu tiên đến "đỉnh dừng" trên đường đi này, thì chúng ta có thể bỏ đi đóng góp của \(2t\) điểm trên đường đi dài \(w\), không ảnh hưởng đến đóng góp của \(d'\).

Do đó chúng ta biết \(d'\le w-2t\), và \(d'\) cũng tương ứng một đường đi đến "đỉnh dừng", do đó \(d'\ge d\), do đó \(w-2t\ge d\).

Tìm đường đi có \(w-t\) nhỏ nhất, có thể coi là đặt giá trị tại đỉnh kết thúc là \(0\), các điểm khác đặt giá trị \(1\), có thể 01bfs.

Dễ thấy các trường hợp khác chắc chắn không tối ưu, lúc này chúng ta biểu thị \(f(x)=\min(2x+d-2,x-t+w)\), có thể coi là một vỏ lồi trên hai đoạn.

Do đó với mỗi \(x\), đóng góp tổng của tất cả quân cờ là một hàm đoạn \(F(x)\), và số đoạn của nó \(\le k\), và là vỏ lồi trên.

Một ý nghĩ đơn giản là với mỗi \(u,x\), tìm đường đi ngắn nhất từ \(a_1\) đến \(u\) chính xác đi qua \(x\) vòng, dùng \(d_{u,x}+F(x)\) cập nhật đáp án.

Nhưng độ phức tạp này không thể chấp nhận được, theo tư duy tham lam, chúng ta tự nhiên nghĩ đến tìm đường đi có số vòng nhỏ nhất, nhưng điều này không đúng, vì chúng ta có thể tăng số vòng đi qua một chút, nhưng làm cho độ dài đường đi giảm đi.

Nhưng độ dài đường đi giảm chắc chắn \(\le n\), vì độ dài đường đi ban đầu chắc chắn không vượt quá \(n\).

Do đó chúng ta thấy rằng số vòng lớn không tối ưu, vì mỗi tăng một vòng, \(k-1\) quân cờ khác ít nhất phải di chuyển một bước, do đó mỗi tăng một vòng, \(F(x)\) ít nhất tăng \(k-1\).

Do đó sau \(\dfrac{n}{k-1}\) vòng, chúng ta không thể có quyết định tốt hơn đường đi có số vòng nhỏ nhất.

Do đó chúng ta có thể đồ thị bfs phân tầng, độ phức tạp \(\mathcal O\left(\dfrac{nm}k\right)\).

Vậy trường hợp \(k\) lớn đã được giải quyết, chúng ta chỉ cần xét trường hợp \(k\) nhỏ.

Chúng ta liệt kê mỗi cạnh trên vỏ lồi, đặt nó trong khoảng \(x\in[l,r]\} thì \(F(x)=px+b\), thì hệ số \(p\) tương đương: nếu số vòng thuộc khoảng này, thì coi chi phí di chuyển \(x\) vòng là \(p\times x\).

Chúng ta liệt kê \(p\), thêm một vòng (quân cờ qua "đỉnh dừng"}) cộng thêm \(p\), trong trường hợp này tìm đường đi ngắn nhất \(d_u\).

Quan sát số vòng của đường đi ngắn nhất lúc này, nếu số vòng này thuộc \([l,r]\}, thì rõ ràng đây là đáp án, dùng \(d_u+b\) cập nhật đáp án của \(u\).

Nếu số vòng này thuộc ngoài \([l,r]\}, thì rõ ràng \(d_u+b\) không thể là đáp án, vì lúc này \(px+b>F(x)\), do đó lấy quyết định tương ứng với \(F(x)\) chắc chắn tốt hơn.

Do đó chúng ta biết đáp án là tất cả \(d_u+b\) nhỏ nhất tương ứng với mỗi \(p\).

Do vỏ lồi chỉ có \(\mathcal O(k)\) đoạn, chạy Dijkstra cho mỗi đoạn, có thể đạt \(\mathcal O(km\log m)\) độ phức tạp.

Cân nhắc căn bằng bằng căn bậc hai cho \(k\) là được.

Độ phức tạp thời gian \(\mathcal O(m\sqrt{n\log m})\).

Code mẫu

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e4+5,inf=1e9,LIM=225;
int n,m,st[MAXN],cl[MAXN];
vector <int> G[MAXN];
int w1[MAXN],w2[MAXN];
ll ans[MAXN];
void bfs1() { //ans from x[1] without stop
	memset(ans,0x3f,sizeof(ans));
	queue <int> q; q.push(st[1]),ans[st[1]]=0;
	while(q.size()) {
		int u=q.front(); q.pop();
		if(u!=st[1]&&cl[u]) continue;
		for(int v:G[u]) if(ans[v]>n) ans[v]=ans[u]+1,q.push(v);
	}
}
void bfs2() { //min dis to first stop
	fill(w2+1,w2+n+1,inf);
	queue <int> q;
	for(int i=1;i<=n;++i) if(cl[i]) {
		for(int j:G[i]) if(w2[j]==inf) w2[j]=1,q.push(j);
	}
	while(q.size()) {
		int u=q.front(); q.pop();
		for(int v:G[u]) if(w2[v]==inf) w2[v]=w2[u]+1,q.push(v);
	}
}
void bfs3() { //min dis to 2 connected stops
	deque <int> q;
	fill(w1+1,w1+n+1,inf);
	for(int i=1;i<=n;++i) if(cl[i]&&w2[i]==1) w1[i]=0,q.push_back(i);
	static bool vis[MAXN];
	fill(vis+1,vis+n+1,false);
	while(q.size()) {
		int u=q.front(); q.pop_front();
		if(vis[u]) continue; vis[u]=true;
		int d=w1[u]+1-cl[u];
		for(int v:G[u]) if(w1[v]>d) {
			w1[v]=d;
			if(cl[u]) q.push_front(v);
			else q.push_back(v);
		}
	}
}
namespace A {
int lim,rd[MAXN],d[MAXN][MAXN/LIM+5];
ll f[MAXN],sum=0;
void bfs4() { //min rounds to every vertex
	fill(rd+1,rd+n+1,inf);
	deque <int> q;
	q.push_back(st[1]),rd[st[1]]=0;
	static bool vis[MAXN];
	fill(vis+1,vis+n+1,false);
	while(q.size()) {
		int u=q.front(); q.pop_front();
		if(vis[u]) continue; vis[u]=true;
		int z=cl[u]&&u!=st[1];
		for(int v:G[u]) if(rd[v]>rd[u]+z) {
			rd[v]=rd[u]+z;
			z?q.push_back(v):q.push_front(v);
		}
	}
}
void bfs5() { //shortest path to vertex at round d0[u]+i
	for(int i=1;i<=n;++i) fill(d[i],d[i]+lim+5,inf);
	queue <array<int,2>> q;
	q.push({st[1],0}),d[st[1]][0]=0;
	while(q.size()) {
		int u=q.front()[0],i=q.front()[1]; q.pop();
		int z=cl[u]&&d[u][i]>0;
		for(int v:G[u]) {
			int j=i+rd[u]+z-rd[v];
			if(j<=lim&&d[v][j]==inf) d[v][j]=d[u][i]+1,q.push({v,j});
		}
	}
}
void giai() {
	lim=n/(m-1),f[1]=2*m-2;
	for(int i=2;i<=m;++i) {
		ll s=w1[st[i]],t=w2[st[i]]-2; //x+s or 2x+t
		if(s!=inf) --f[s-t+1];
		sum+=t;
	}
	for(int i=1;i<=n;++i) f[i]+=f[i-1];
	for(int i=1;i<=n;++i) f[i]+=f[i-1];
	bfs4(),bfs5(),f[0]=-sum;
	for(int i=1;i<=n;++i) for(int j=0;j<=lim;++j) if(d[i][j]!=inf&&j+rd[i]<=n) {
		ans[i]=min(ans[i],d[i][j]+f[j+rd[i]]+sum);
	}
}
}
namespace B {
int x[MAXN]; //change slope
bool vis[MAXN],chk[MAXN]; //round>1
ll dis[MAXN];
void dijk(int k) {
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	memset(chk,false,sizeof(chk));
	priority_queue <array<ll,2>,vector<array<ll,2>>,greater<array<ll,2>>> q;
	q.push({dis[st[1]]=0,st[1]});
	while(q.size()) {
		int u=q.top()[1]; q.pop();
		if(vis[u]) continue; vis[u]=true;
		int z=(cl[u]&&u!=st[1])?k+1:1;
		for(int v:G[u]) if(dis[v]>dis[u]+z) {
			q.push({dis[v]=dis[u]+z,v});
			chk[v]=chk[u]|(z>1);
		}
	}
}
void giai() {
	ll sum=0;
	for(int i=2;i<=m;++i) {
		int s=w1[st[i]],t=w2[st[i]]-2;
		x[i-1]=s-t+1,sum+=t;
	}
	x[0]=0,x[m]=n,sort(x,x+m+1);
	for(int i=0;i<m&&x[i]<n;++i) {
		if(i) sum+=x[i]-1;
		if(x[i+1]==x[i]) continue;
		dijk(2*m-2-i);
		for(int u=1;u<=n;++u) if(vis[u]&&chk[u]) ans[u]=min(ans[u],dis[u]+sum);
	}
}
}
signed main() {
	int E;
	scanf("%d%d%d",&n,&E,&m);
	for(int u,v;E--;) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
	for(int i=1;i<=n;++i) scanf("%1d",&cl[i]);
	for(int i=1;i<=m;++i) scanf("%d",&st[i]);
	bfs1(),bfs2(),bfs3();
	if(m>LIM) A::giai();
	else B::giai();
	for(int i=1;i<=n;++i) printf("%lld\n",ans[i]);
	return 0;
}

*H. [P10591] Connect

Đề bài

Cho \(m\) đồ thị vô hướng \(n\) đỉnh, đếm số lượng tập con \(1\sim m\) sao cho tập hợp các cạnh của đồ thị có chỉ số trong tập hợp này, khi lấy XOR, đồ thị thu được liên thông.

Phạm vi: \(n\le10,m\le 60\).

Phân tích

Cân nhắc bao trùm, chỉ định đồ thị thu được có thể chia thành \(i\) thành phần liên thông, đặt số lượng phương án như vậy là \(g_i\), đặt số lượng phương án đồ thị thu được chính xác có \(j\) thành phần liên thông là \(f_j\).

Chúng ta có:

[g_i=\sum_{j\ge i}\begin{Bmatrix}j\i\end{Bmatrix}f_j ]trong đó \(\begin{Bmatrix}j\\i\end{Bmatrix}\) là số Stirling loại hai, theo nghịch đảo Stirling thu được:

[f_j=\sum_{i\ge j}(-1)^{i-j}\begin{bmatrix}j\i\end{Bmatrix}g_i ]do đó đáp án của chúng ta là \(f_1\), thay \(j=1\) thu được đáp án là \(\sum_{i}(-1)^{i-1}(i-1)!g_i\).

Do đó chúng ta chỉ cần tính \(g_i\), cân nhắc liệt kê hình thái thành phần liên thông cuối cùng, tức là liệt kê tất cả cách chia \(1\sim n\) thành \(i\) tập hợp, với mỗi phương án, cần chỉ định mỗi cạnh giữa các tập hợp xuất hiện số chẵn lần trong đồ thị, có thể giải quyết bằng cơ sở tuyến tính.

Độ phức tạp thời gian \(\mathcal O(\mathrm{Bell}(n)n^2m)\).

Code mẫu

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,a[10],g[65][10][10];
ll X[65],giaiThua[65],mu[65],ans=0;
struct coSoTuyenTinh {
	int cnt;
	ll b[65];
	void khoiTao() { cnt=0,memset(b,0,sizeof(b)); }
	void chen(ll x) {
		for(int i=45;~i;--i) if(x>>i&1) {
			if(!b[i]) return b[i]=x,++cnt,void();
			x^=b[i];
		}
	}
}	B;
void tinh(int k) {
	B.khoiTao(),memset(X,0,sizeof(X));
	for(int i=0;i<n;++i) for(int j=i+1;j<n;++j) if(a[i]!=a[j]) {
		for(int o=0;o<m;++o) X[o]=X[o]<<1|g[o][i][j];
	}
	for(int o=0;o<m;++o) B.chen(X[o]);
	ans+=(k&1?1:-1)*giaiThua[k-1]*mu[m-B.cnt];
}
void dfs(int i,int c) {
	if(i==n) return tinh(c);
	for(a[i]=1;a[i]<=c+1;++a[i]) dfs(i+1,max(a[i],c));
}
signed main() {
	for(int i=giaiThua[0]=mu[0]=1;i<64;++i) giaiThua[i]=giaiThua[i-1]*i,mu[i]=mu[i-1]*2;
	ios::sync_with_stdio(false);
	cin>>m;
	for(int o=0;o<m;++o) {
		string s; cin>>s;
		while(n*(n-1)/2!=(int)s.size()) ++n;
		for(int i=0,k=0;i<n;++i) for(int j=i+1;j<n;++j) g[o][i][j]=s[k++]-'0';
	}
	dfs(0,0);
	cout<<ans<<"\n";
	return 0;
}

*I. [P10064] Path

Đề bài

Cho một cây \(n\) đỉnh, chọn một số đường đi đơn giản trên cây, yêu cầu bất kỳ hai điểm nào trên cây, đường đi giữa chúng đều có \(\le 2\) đường đi được chọn bao phủ, đếm số lượng phương án.

Phạm vi: \(n\le 3000\).

Phân tích

Rõ ràng nếu tồn tại một đường đi không hợp lệ, chắc chắn tồn tại một đường đi từ lá đến lá không hợp lệ.

Do đó chỉ cần tất cả đường đi từ lá đến lá đều hợp lệ.

Chúng ta lấy tất cả các điểm lá \(u\) có thể đến bằng một đường đi được chọn, đặt là \(S_u\), chúng ta yêu cầu giao của tất cả \(S_u\) không rỗng.

Chú ý rằng nếu giao của \(S_u\) không rỗng, chắc chắn là một thành phần liên thông, do đó chúng ta có thể dùng điểm trừ cạnh bao trùm, tức là tính toán mỗi điểm thuộc giao của \(S_u\) và mỗi cạnh (hai điểm) thuộc giao của \(S_u\) số phương án.

Trước hết tính toán số phương án cạnh \(u\to fa(u)\) thuộc giao của \(S_u\), thấy khó duy trì, không妨 bao trùm, chỉ định có bao nhiêu lá trong cây con \(u\) không thuộc cạnh này, có thể tính số phương án lá ngoài cây con \(S\) chắc chắn đi qua \(u\):

[\mathrm{Ans} =\sum_{i=0}^{l_u}(-1)^i\binom {l_u}i2^{(s_o-l_o)(s_u-i)}\times 2^{s_u(s_u-1)/2}\times 2^{s_i(s_o-1)/2}\times (2^{s_u-i}-1)^{l_o} ]trong đó \(s_u/s_o\) là số lượng trong cây con \(u\)/ngoài \(u\), \(l_u,l_o\) là số lượng lá trong cây con \(u\)/ngoài \(u\), cụ thể là phân loại các cạnh.

Sau đó tính toán số phương án điểm \(u\) thuộc giao của \(S_u\), lúc này không thể trực tiếp bao trùm, vì sau khi xóa \(u\) có \(\mathrm{deg}(u)\) thành phần liên thông, chúng ta chỉ có thể chỉ định một thành phần liên thông trong đó tất cả các lá của \(S\) đi qua \(u\).

Do đó chúng ta có thể túi động duy trì hệ số bao trùm, \(f_i\) là chỉ định \(i\) lá trong cây con \(u\) không đi qua \(u\), cộng thêm cây con \(v\) chuyển là:

[f'_{i+j}\gets f_i\times (-1)^j\binom{l_v}j\times 2^{(S_u-i)(S_v-j)} ]\(u\) cây con ngoài các lá trực tiếp chỉ định \(S_u\) chắc chắn đi qua \(u\), công thức tính toán giống như trên, do khi tính toán đáp án là bottleneck ở lũy thừa nhanh, có thể tối ưu bằng cách xử lý trước.

Độ phức tạp thời gian \(\mathcal O(n^2\log P)\).

Code mẫu

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3005,MAXV=5e6+5,MOD=998244353;
ll ksm(ll a,ll b) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
ll giaiThua[MAXN],nhanGiaiThua[MAXN];
ll C(int x,int y) {
	if(x<0||y<0||y>x) return 0;
	return giaiThua[x]*nhanGiaiThua[y]%MOD*nhanGiaiThua[x-y]%MOD;
}
int n,sz[MAXN],sf[MAXN],soLa=0;
vector <int> G[MAXN];
void dfs(int u,int fz) {
	if(G[u].size()==1) return sz[u]=sf[u]=1,void();
	for(int v:G[u]) if(v^fz) dfs(v,u);
	memset(f,0,sizeof(f)),sz[u]=1,f[0]=1;
	int trong=0;
	for(int v:G[u]) if(v^fz) {
		memset(g,0,sizeof(g));
		for(int i=0;i<=sf[v];++i) {
			ll w=i&1?MOD-C[sf[v]][i]:C[sf[v]][i];
			for(int j=0;j<=sf[u];++j) {
				g[i+j]=(g[i+j]+w*f[j]%MOD*mu[(sz[v]-i)*(sz[u]-j)])%MOD;
			}
		}
		memcpy(f,g,sizeof(f));
		trong+=sz[v]*(sz[v]-1)/2;
	}
	int ngoai=n-sz[u],ngoaiLa=soLa-sf[u];
	trong+=ngoai*(ngoai-1)/2;
	for(int i=0;i<=sf[u];++i) {
		ans=(ans+f[i]*mu[trong+(ngoaiLa-ngoai)*(sz[u]-i)]%MOD*ksm(mu[sz[u]-i]-1,ngoaiLa))%MOD;
	}
	if(!fz) return ;
	trong=ngoai*(ngoai-1)/2+sz[u]*(sz[u]-1)/2;
	for(int i=0;i<=sf[u];++i) {
		ll z=i&1?C[sf[u]][i]:MOD-C[sf[u]][i];
		ans=(ans+z*mu[trong+(ngoaiLa-ngoai)*(sz[u]-i)]%MOD*ksm(mu[sz[u]-i]-1,ngoaiLa))%MOD;
	}
}
signed main() {
	scanf("%d",&n);
	for(int i=nhanGiaiThua[0]=giaiThua[0]=1;i<=n;++i) nhanGiaiThua[i]=ksm(giaiThua[i]=giaiThua[i-1]*i%MOD);
	for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
	if(n==2) return puts("1"),0;
	int dinh=0;
	for(int i=1;i<=n;++i) {
		if(G[i].size()==1) ++soLa;
		else if(!dinh) dinh=i;
	}
	dfs(dinh,0);
	printf("%lld\n",ans);
	return 0;
}

Vòng #11 - 2024.9.26

A. [P9923] Button

Đề bài

Cho lưới \(n\times n\), có \(m\) điểm, chọn một số điểm (ít nhất một) tô đen, sao cho mỗi hàng mỗi cột số ô đen có cùng tính chẵn lẻ.

Phạm vi: \(n\le 10^5,m\le 5\times 10^5\).

Phân tích

Cân nhắc tách điểm xây đồ thị, mỗi điểm có thể coi là một cạnh giữa hai điểm, lúc này chúng ta cần chọn một tập cạnh không rỗng sao cho trong tập cạnh này, bậc của mỗi điểm có cùng tính chẵn lẻ.

Trước hết xét trường hợp mỗi điểm bậc đều chẵn, lúc này tập cạnh chắc chắn sẽ hình thành若干 chu trình Euler, do bậc 0 cũng hợp lệ, chỉ cần một thành phần liên thông nào đó có thể chọn một vòng là được.

Còn lại chắc chắn là rừng, lúc này chúng ta yêu cầu mỗi điểm bậc đều chẵn, tự dưới trên xây dựng, dùng mỗi cạnh đến cha để điều chỉnh, có thể có duy nhất phương án (hoặc không có phương án).

Độ phức tạp thời gian \(\mathcal O(n+m)\).

Code mẫu

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m,cha[MAXN*2];
int dinh[MAXN*2],ec=1,den[MAXN*10];
bool vis[MAXN*2];
void themCung(int u,int v) { den[++ec]=v,den[ec]=dinh[u],dinh[u]=ec; }
void dfs1(int u) {
	vis[u]=true;
	for(int i=dinh[u];i;i=den[i]) if(i!=cha[u]){
		int v=den[i];
		if(!vis[v]) cha[v]=i^1,dfs1(v);
		else {
			vector <int> wys{i};
			for(int x=u;x!=v;x=den[cha[x]]) wys.push_back(cha[x]);
			cout<<"TAK\n"<<wys.size()<<"\n";
			for(int z:wys) cout<<z/2<<" ";
			cout<<"\n";
			exit(0);
		}
	}
}
bool bac[MAXN*2];
vector <int> wys;
void dfs2(int u) {
	vis[u]=true;
	for(int i=dinh[u];i;i=den[i]) if(i^cha[u]) dfs2(den[i]);
	if(cha[u]&&!bac[u]) {
		bac[den[cha[u]]]^=1,wys.push_back(cha[u]),bac[u]^=1;
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;++i) {
		cin>>u>>v,themCung(u,v+n),themCung(v+n,u);
	}
	for(int i=1;i<=2*n;++i) if(!vis[i]) dfs1(i);
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=2*n;++i) if(!vis[i]) {
		dfs2(i);
		if(!bac[i]) return cout<<"NIE\n",0;
	}
	cout<<"TAK\n"<<wys.size()<<"\n";
	for(int z:wys) cout<<z/2<<" ";
	cout<<"\n";
	return 0;
}

B. [P10360] Swap

Đề bài

Cho dãy độ dài \(n\) là \(x_1\sim x_n\), \(m\) thao tác \((a_i,b_i)\), nếu \(x_{a_i}=1,x_{b_i}=0\) thì hoán vị \(x_{a_i}x_{b_i}\).

Một dãy tốt khi và chỉ khi dãy \(x\) thu được cuối cùng, các \(1\) chính xác tạo thành một khoảng.

Với mỗi \(k\) đếm số lượng dãy 01 có đúng \(k\) cái \(1\) là tốt, đáp án lấy mod \(2\).

Phạm vi: \(n\le 35,m\le 1000\).

Phân tích

Brute-force đơn giản là với mỗi \(x\), duy trì dãy từ trước đến sau, nhưng rõ ràng không thể qua được.

Cân nhắc giảm số lượng liệt kê, với một \(x_i\) không bị bất kỳ thao tác nào bao phủ, chúng ta không liệt kê giá trị của nó, chỉ xét khi có \(a_j=i\).

Với một thao tác \(a_i,b_i\), phân loại hai phần tử hiện tại có xác định giá trị không:

• Nếu \(x_{a_i},x_{b_i}\} đều được xác định, trực tiếp mô phỏng thao tác tiếp theo.
• Nếu \(x_{a_i},x_{b_i}\} đều chưa được xác định, chúng ta thấy rằng nếu \(x_{a_i}\ne x_{b_i}\), khi chuyển sang thao tác tiếp theo hai dãy sẽ thu được kết quả giống nhau, do đó đóng góp của dãy này chắc chắn chẵn, có thể bỏ qua.

Do đó chỉ cần liệt kê \(x_{a_i}=x_{b_i}=0/1\) hai trường hợp.

• Nếu chỉ có \(x_{a_i}\} được xác định (trường hợp đối xứng), nếu \(x_{a_i}=0\), chứng tỏ thao tác này vô hiệu, có thể bỏ qua, ngược lại chúng ta thấy rằng:

• Nếu \(x_{b_i}=1\), sau khi hoán vị \(x'_{a_i}=x'_{b_i}=1\).

• Nếu \(x_{b_i}=0\), sau khi hoán vị \(x'_{a_i}=0,x'_{b_i}=1\).

Do đó lúc này \(x_{b_i}\} chắc chắn là \(1\), \(x_{a_i}\} tùy chọn \(0/1\), do đó trực tiếp đặt \(x_{b_i}\} là đã biết và giá trị là \(1\), \(x_{a_i}\} là chưa biết là được.

Dễ thấy chỉ có trường hợp thứ hai khi số trạng thái nhân đôi, và lúc này chắc chắn tiêu thụ hai phần tử chưa biết, do đó tổng số trạng thái là \(\mathcal O(2^{n/2})\).

Độ phức tạp thời gian \(\mathcal O(2^{n/2}(m+n^2))\).

Nếu \(x_{b_i}=0\), sau khi hoán vị \(x'_{a_i}=x'_{b_i}=0\).

Code mẫu

#include<bits/stdc++.h>
#define ll long long
#define q(s,i) (s>>i&1)
#define d(i) (1ll<<i)
using namespace std;
const int MAXN=1005;
int n,m,a[MAXN],b[MAXN];
bool ans[40];
void dfs(int i,ll vis,ll col) {
	if(i==m+1) {
		for(int l=0;l<n;++l) {
			int p=n;
			for(int r=l;r<n;++r) if(q(vis,r)&&!q(col,r)) {
				p=r; break;
			}
			for(int r=n-1;r>=l;--r) {
				if(r<p) ans[r-l+1]^=1;
				if(q(vis,r)&&q(col,r)) break;
			}
			if(q(vis,l)&&q(col,l)) break;
		}
		return ;
	}
	if(q(vis,a[i])&&q(vis,b[i])) {
		if(q(col,a[i])&&!q(col,b[i])) col^=d(a[i])^d(b[i]);
		dfs(i+1,vis,col);
	} else if(q(vis,a[i])) {
		if(!q(col,a[i])) dfs(i+1,vis,col); 
		else {
			vis^=d(a[i])^d(b[i]);
			col&=~d(a[i]);
			dfs(i+1,vis,col|d(b[i]));
		}
	} else if(q(vis,b[i])) {
		if(q(col,b[i])) dfs(i+1,vis,col);
		else {
			vis^=d(a[i])^d(b[i]);
			col&=~d(b[i]);
			dfs(i+1,vis,col&(~d(a[i])));
		}
	} else {
		vis|=d(a[i])^d(b[i]);
		dfs(i+1,vis,col);
		dfs(i+1,vis,col|d(a[i])|d(b[i]));
	}
}
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) scanf("%d%d",&a[i],&b[i]),--a[i],--b[i]);
	dfs(1,0,0);
	for(int i=1;i<=n;++i) printf("%d ",ans[i]); puts("");
	return 0;
}

C. [P10367] Flip

Đề bài

Cho đồ thị vô hướng \(n\) đỉnh \(m\) cạnh, mỗi đỉnh ban đầu có màu đen hoặc trắng, với một cạnh hai điểm cùng màu, có thể đồng thời lật màu hai điểm, xét theo \(\bmod 3\).

Tính số lượng kết hợp màu nút khác nhau có thể thu được.

Phạm vi: \(n\le 2\times 10^5,m\le 4\times 10^5\).

Phân tích

Từ trường hợp chuỗi vào tay, chúng ta thấy rằng nếu \(a_{i-1}\ne a_{i+1}\), không妨 đặt \(a_i=a_{i-1}\), thì thao tác \((i-1,i),(i,i+1)\) có thể hoán vị \(a_{i-1},a_{i+1}\).

Do đó chúng ta có thể sắp xếp tùy ý các điểm ở vị trí lẻ và chẵn, và đồng thời tăng hoặc giảm số điểm đen ở hai vị trí.

Do đó chỉ cần đảm bảo chênh lệch số điểm đen ở hai vị trí bằng nhau, mỗi dãy màu đều có thể thu được.

Dễ dàng khái quát hóa kết luận này đến đồ thị hai phía liên thông.

Với một vòng lẻ, chúng ta thấy rằng theo quá trình trên, có thể sắp xếp tùy ý toàn bộ vòng màu, do đó对于一个 có vòng lẻ thành phần liên thông, chúng ta chỉ yêu cầu số điểm đen không đổi tính chẵn lẻ.

Đáp án là tích của đáp án mỗi thành phần liên thông.

Độ phức tạp thời gian \(\mathcal O(n+m)\).

Code mẫu

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5,MOD=1e9+7;
ll ksm(ll a,ll b) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
ll giaiThua[MAXN],nhanGiaiThua[MAXN];
ll C(int x,int y) {
	if(x<0||y<0||y>x) return 0;
	return giaiThua[x]*nhanGiaiThua[y]%MOD*nhanGiaiThua[x-y]%MOD;
}
int n,m;
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=nhanGiaiThua[0]=giaiThua[0]=1;i<=n;++i) nhanGiaiThua[i]=ksm(giaiThua[i]=giaiThua[i-1]*i%MOD);
	for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v);
	ll ans=1;
	for(int u=1;u<=n;++u) {
		int s=C(n,0)+C(n,1);
		ans=ans*s%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}

D. [P10879] Modify

Đề bài

Cho cây \(n\) đỉnh, cha của đỉnh thứ \(i\) nằm trong \([l_i,r_i]\) ngẫu nhiên, \(m\) thao tác cho cạnh \(u\to v\) cộng \(w\), tính kỳ vọng cạnh \(u\to fa(u)\} của mỗi đỉnh.

Phạm vi: \(n,m\le 5000\).

Phân tích

Cân nhắc cách mô tả trọng số cạnh, cân nhắc một quy trình LCA đơn giản, nếu \(u>v\), thì cạnh \(u\to fa(u)\} chắc chắn được bao phủ.

Do đó có thể thiết kế dp đơn giản, \(f_{i,j}\) là xác suất bắt đầu từ \((u,v)\) nhảy đến \((i,j)\).

Chuyển đổi là \(\dfrac{f_{u,v}}{r_u-l_u+1}\to f_{l_u\sim r_u,v}\), nhưng phải đảm bảo \(u>v\), do đó có thể coi là cộng khoảng trên \(f\), duy trì bằng cách phân biệt.

Tính đáp án就是把 mỗi \(w\times f_{i,j}\) cộng vào đáp án của \(i\), với mỗi đường đi dp độ phức tạp \(\mathcal O(n^2m)\).

Ghép điểm đầu, tức là mỗi đường đi coi là ban đầu \(f_{u,v}\} cộng \(w\), một lần dp có thể tính đáp án.

Độ phức tạp thời gian \(\mathcal O(n^2+m)\).

Code mẫu

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005,MOD=998244353;
int n,m,l[MAXN],r[MAXN],f[MAXN][MAXN],inv[MAXN],g[MAXN];
int a[MAXN][MAXN],b[MAXN][MAXN];
void cong(int &x,int y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
void tru(int &x,int y) { x=(x>=y)?x-y:x+MOD-y; }
signed main() {
	scanf("%d",&n),inv[1]=1;
	for(int i=2;i<=n;++i) scanf("%d%d",&l[i],&r[i]),inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
	scanf("%d",&m);
	for(int i=1,u,v,w;i<=m;++i) {
		scanf("%d%d%d",&u,&v,&w);
		cong(f[max(u,v)][min(u,v)],w%MOD);
	}
	for(int j=n;j>=1;--j) {
		for(int i=n;i>j;--i) {
			cong(a[i][j],a[i+1][j]),cong(f[i][j],a[i][j]);
			cong(b[i][j],b[i][j+1]),cong(f[i][j],b[i][j]);
			cong(g[i],f[i][j]);
			int z=1ll*f[i][j]*inv[r[i]-l[i]+1]%MOD;
			if(j<l[i]) cong(a[r[i]][j],z),tru(a[l[i]-1][j],z);
			else if(r[i]<j) cong(b[j][r[i]],z),tru(b[j][l[i]-1],z);
			else {
				cong(a[r[i]][j],z),tru(a[j][j],z);
				cong(b[j][j-1],z),tru(b[j][l[i]-1],z);
			}
		}
	}
	for(int i=2;i<=n;++i) printf("%d ",g[i]); puts("");
	return 0;
}

*E. [P9850] Subgraph

Đề bài

Cho đồ thị hai phía trái phải mỗi bên \(n\) đỉnh, \(m\) cạnh, cho mỗi điểm xây dựng chuỗi độ dài \(n+1\) (ký tự tập \(\texttt{A,B,C}\)), sao cho:

• Hai chuỗi có ít nhất một vị trí bằng nhau khi và chỉ khi hai điểm tương ứng cùng phía đồ thị hai phía, hoặc có cạnh nối.
• Các chuỗi đôi một khác nhau.

Phạm vi: \(n\le 1000,m\le n^2\).

Phân tích

Một cách làm đơn giản là với điểm trái \(1\sim n\), cho chuỗi thứ \(i\} vị trí thứ \(i\) điền \(\texttt C\), các vị trí khác điền \(\texttt A\}.

Với mỗi điểm phải, nếu nó nối với điểm trái thứ \(i\}, điền \(\texttt{C}\), ngược lại điền \(\texttt B\).

Vị trí thứ \(0\) điểm trái điền \(\texttt A\}, điểm phải điền \(\texttt B\}, một chuỗi độ dài \(n+1\} như vậy có thể thu được đáp án.

Nhưng lúc này chúng ta không thể đảm bảo mỗi chuỗi của điểm phải đôi một khác nhau, chúng ta có thể dùng thêm \(\lceil\log_2 n\rceil\) vị trí để biểu diễn nhị phân của thứ tự \(i\) của điểm phải (dùng \(\texttt{B,C}\} thay cho \(0,1\)), và các vị trí này của điểm trái điền \(\texttt A\}.

Độ dài chuỗi lúc này là \(n+1+\lceil\log_2n\rceil\), không thể qua được.

Cân nhắc điểm phải nào sẽ thu được chuỗi giống nhau, chỉ khi và chỉ khi chúng có cùng lân vực, gọi các điểm này là "tương đương".

Chú ý rằng chỉ có các điểm trong cùng một lớp tương đương mới cần phân biệt, do đó chúng ta có thể trực tiếp truyền biểu diễn nhị phân của thứ hạng trong lớp tương đương, thay vì biểu diễn nhị phân của \(i\).

Giả sử kích thước lớn nhất của lớp tương đương điểm phải là \(R_s\), thì chúng ta chỉ cần \(n+1+\lceil\log_2 R_s\rceil\) vị trí, nhưng không đủ, cần tiếp tục tối ưu.

Cân nhắc chia lớp tương đương của điểm trái, dễ thấy một lớp tương đương có thể dùng chung một vị trí điền \(\texttt C\), nhưng chúng ta cần khử trùng trong lớp tương đương trái.

Vậy đặt số lượng lớp tương đương trái phải là \(L_c,R_c\), kích thước lớn nhất là \(L_s,R_s\).

Khi đó số vị trí tiêu thụ là \(L_c+\lceil \log_2L_s\rceil+\lceil\log_2 R_s\rceil\), khi \(R_c<L_c\) có thể đổi trái phải để có số lần tốt hơn.

Tổng hợp chúng ta thu được số vị tiêu thụ là \(\min(L_c,R_c)+\lceil \log_2L_s\rceil+\lceil\log_2 R_s\rceil\).

Phân tích quy mô của nó, chú ý rằng \(L_s\le n-L_C+1\le n-\min(L_c,R_c)+1\).

Do đó đặt \(x=n-\min(L_c,R_c)+1\), lúc này số vị tiêu thụ không vượt quá \(n-x+1+2\lceil \log_2x\rceil\).

Khi \(x\ge 2\lceil\log_2x\rceil\) thì số vị tiêu thụ \(\le n+1\).

Chúng ta chỉ cần xét trường hợp \(x<2\lceil\log_2x\rceil\), thấy lúc này chắc chắn có \(x=3/x=5\).

Không妨 đặt \(x=3\), lúc này hai phía đều có \(n-3\) lớp tương đương kích thước \(1\) và một lớp tương đương kích thước \(3\).

Cân nhắc lớp tương đương kích thước \(3\) của trái \(\{x,y,z\}\), chúng ta cần \(1\) vị trí truyền thông tin kết nối, và cần \(2\) vị trí để phân biệt thứ tự.

Nếu mỗi điểm truyền thông tin kết nối riêng, thì không cần phân biệt thứ tự, nhưng cần \(3\) vị trí truyền thông tin.

Kết hợp hai cách làm, vị trí thứ nhất truyền thông tin kết nối của \(x,y\}, vị trí thứ hai truyền thông tin kết nối của \(y,z\}, lúc này hai lần truyền có thể khiến tất cả chuỗi khác nhau.

Trường hợp \(x=5\) tương tự, với lớp tương đương năm phần tử \(\{a,b,c,d,e\}\}, vị trí thứ nhất truyền thông tin của \(a,b,c\}, vị trí thứ hai truyền thông tin của \(c,d,e\}, vị trí thứ ba truyền thông tin của \(b,d\} là được.

Tóm lại, chúng ta thu được cấu trúc có độ dài chuỗi \(\le n+1\) hoàn chỉnh.

Độ phức tạp thời gian \(\mathcal O(n^2+m)\).

Code mẫu

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=2005;
int n,m;
ull hs[MAXN],hv[MAXN];
bool vis[MAXN];
int lg(int x) { return __lg(x)+!!(x&(x-1)); }
void giai() {
	for(int i=0;i<2*n;++i) {
		//clear
	}
	for(int i=1,u,v;i<=m;++i) {
		scanf("%d%d",&u,&v),--u,--v;
		hs[u]^=hv[v];
		hs[v]^=hv[u];
	}
	cout<<lim<<"\n";
	for(int i=0;i<2*n;++i) {
		//build strings
	}
}
signed main() {
	int Q; scanf("%d",&Q);
	while(Q--) giai();
	return 0;
}

*G. [P9924] Signal

Đề bài

Cho tập hợp \(S\), định nghĩa \(f(S)\) là tổng giá trị của tất cả các dãy thu được bằng cách XOR tất cả số trong \(S\) với \(\mathrm{mex}(S)-1\).

\(q\) yêu cầu cho \(n,k,p\), đếm số lượng \(S\) thỏa mãn:

• \(S\subseteq[0,2^k)\) và \(0\in S,|S|=n\).
• Dãy \(S,f(S),f(f(S)),\dots\) hội tụ về \(S_0\), và \(\mathrm{mex}(S_0)=p\).

Phạm vi: \(k\le 17,n,p\le 2^k,q\le 2\times 10^5\).

Phân tích

Đặt \(|S|<2^k\), cân nhắc mô tả \(p\) khi hội tụ:

• Nếu \([0,2^{k-1})\) không toàn bộ thuộc \(S\), thì giới hạn của \(S\) bằng giới hạn của \(S\) trong \([0,2^{k-1})\).
• Ngược lại \(\mathrm{mex}(S)-1\) ít nhất là \(2^{k-1}-1\):
• Nếu \(2^{k-1}\) thuộc \(S\), thì \(\mathrm{mex}(S)-1\) ít nhất là \(2^{k-1}\), lật một lần thành giới hạn của \(S\) trong \([2^{k-1},2^k)\).
• Ngược lại \(\mathrm{mex}(S)-1=2^{k-1}-1\):
• Nếu \(2^k-1\not\in S\), sau khi lật \([0,2^{k-1})\) vẫn toàn bộ, \(2^{k-1}\) vẫn không thuộc \(S\), lúc này giới hạn chính là \(2^{k-1}\).
• Ngược lại sau khi lật thành \(2^{k-1}\in S\), vấn đề là giới hạn của \(S\) trong \([2^{k-1},2^k)\) sau khi lật thấp \(k-1\) vị trí.

Dễ thấy lúc này \(p\) chắc chắn là lũy thừa của \(2\).

Cân nhắc dp mô tả, \(f_{i,j,c}\) là xét giá trị miền \([0,2^i)\), giới hạn \(p=2^j\), hiện tại \(|S|=c\}.

Nhưng chúng ta không thể xử lý tình huống sau khi lật, chú ý rằng sau khi lật chúng ta cần xử lý vấn đề con chỉ định \(2^k-1\not\in S\), các hạn chế khác giống nguyên vấn đề, đặt số phương án tương ứng là \(g_{i,j,c}\).

Điều kiện biên là \(j=i-1\), lúc này với tất cả \(2^{i-1}\le c\le 2^i-2\):

[f_{i,i-1,c}=g_{i,i-1,c}=\binom{2^{i-1}-2}{c-2^{i-1}} ]Xét trường hợp tổng quát, trước hết xử lý trường hợp đầu tiên, tức là \([0,2^{i-1})\) giới hạn là \(2^j\), \([2^{i-1},2^i)\) có thể tùy chọn:

[\begin{aligned} f_{i,j,c_0+c_1}&\gets \binom{2^{i-1}}{c_1}f_{i-1,j,c_0}\ g_{i,j,c_0+c_1}&\gets \binom{2^{i-1}-1}{c_1}f_{i-1,j,c_0} \end{aligned} ] có thể dùng NTT tối ưu, dễ bỏ qua tích chập trên \(f\).

Sau đó xử lý các trường hợp còn lại, chú ý tình huống lật chỉ xuất hiện trong \(f\):

[\begin{aligned} f_{i,j,k+2^{i-1}}&\gets f_{i-1,j,k}\ g_{i,j,k+2^{i-1}}&\gets g_{i-1,j,k}\ f_{i,j,k+2^{i-1}}&\gets g_{i-1,j,k} \end{aligned} ] trả lời khi đặc biệt \(n=2^k\} thì đáp án là \(f_{k,\log_2p,n}\).

Độ phức tạp thời gian \(\mathcal O(k^32^k+q)\).

Code mẫu

#include<bits/stdc++.h>
using namespace std;
const int N=1<<18;
namespace FastMod {
typedef unsigned long long ull;
typedef __uint128_t uLL;
ull b,m;
inline void init(ull B) { b=B,m=ull((uLL(1)<<64)/B); }
inline ull mod(ull a) {
	ull q=((uLL(m)*a)>>64),r=a-q*b;
	return r>=b?r-b:r;
}
};
#define o(x) FastMod::mod(x)
int MOD,G;
int rev[N],inv[N],giaiThua[N],nhanGiaiThua[N],w[N<<1];
int ksm(int a,int b=MOD-2) {
	int ret=1;
	for(;b;a=1ll*a*a%MOD,b=b>>1) if(b&1) ret=1ll*ret*a%MOD;
	return ret;
}
void poly_init() {
	vector <int> fr;
	for(int i=2,z=MOD-1;i*i<=z;++i) if(z%i==0) fr.push_back(i),fr.push_back(z/i);
	for(G=2;;++G) {
		bool ok=true;
		for(int z:fr) if(ksm(G,z)==1) { ok=false; break; }
		if(ok) break;
	}
	inv[1]=1;
	for(int i=2;i<N;++i) inv[i]=o(1ll*(MOD-MOD/i)*inv[MOD%i]);
	giaiThua[0]=nhanGiaiThua[0]=1;
	for(int i=1;i<N;++i) giaiThua[i]=o(1ll*giaiThua[i-1]*i),nhanGiaiThua[i]=o(1ll*nhanGiaiThua[i-1]*inv[i]);
	for(int k=1;k<=N;k<<=1) {
		int x=ksm(G,(MOD-1)/k); w[k]=1;
		for(int i=1;i<k;++i) w[i+k]=o(1ll*x*w[i+k-1]);
	}
}
int laySo(int x) { int y=1; for(;y<x;y<<=1); return y;  }
void ntt(int *f,bool idft,int n) {
	for(int i=0;i<n;++i) {
		rev[i]=(rev[i>>1]>>1);
		if(i&1) rev[i]|=n>>1;
	}
	for(int i=0;i<n;++i) if(rev[i]<i) swap(f[i],f[rev[i]]);
	for(int k=2,x,y;k<=n;k<<=1) {
		for(int i=0;i<n;i+=k) {
			for(int j=i;j<i+k/2;++j) {
				x=f[j],y=o(1ll*f[j+k/2]*w[k+j-i]);
				f[j]=(x+y>=MOD)?x+y-MOD:x+y,f[j+k/2]=(x>=y)?x-y:x+MOD-y;
			}
		}
	}
	if(idft) {
		reverse(f+1,f+n);
		for(int i=0,x=ksm(n);i<n;++i) f[i]=o(1ll*f[i]*x);
	}
}
int f[18][18][N],g[18][18][N],a[N],b[N];
int C(int x,int y) { return 1ll*giaiThua[x]*nhanGiaiThua[y]%MOD*nhanGiaiThua[x-y]%MOD; }
inline void cong(int &x,const int &y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
signed main() {
	ios::sync_with_stdio(false);
	cin>>MOD,FastMod::init(MOD),poly_init();
	for(int i=1;i<18;++i) {
		int s=1<<(i-1),len=s<<1;
		memset(a,0,sizeof(int)*len);
		for(int k=0;k<s;++k) a[k]=C(s-1,k);
		ntt(a,0,len);
		for(int j=0;j<i-1;++j) {
			int *F=f[i][j],*G=g[i][j];
			memset(b,0,sizeof(int)*len);
			for(int k=0;k<s;++k) b[k]=f[i-1][j][k];
			ntt(b,0,len);
			for(int k=0;k<len;++k) b[k]=o(1ll*a[k]*b[k]);
			ntt(b,1,len);
			for(int k=0;k<len;++k) cong(G[k],b[k]),cong(F[k],b[k]),cong(F[k+1],b[k]);
			for(int k=0;k<s;++k) {
				cong(F[k+s],f[i-1][j][k]),cong(F[k+s],g[i-1][j][k]);
				cong(G[k+s],g[i-1][j][k]);
			}
		}
		if(i==1) f[1][0][1]=g[1][0][1]=1;
		else for(int k=0;k<s-1;++k) f[i][i-1][k+s]=g[i][i-1][k+s]=C(s-2,k);
	}
	int T; cin>>T;
	for(int k,n,p;T--;) {
		cin>>k>>n>>p;
		if(n==(1<<k)) cout<<(p==n)<<"\n";
		else cout<<(p==(p&-p)?f[k][__lg(p)][n]:0)<<"\n";
	}
	return 0;
}

*H. [P11107] Mex

Đề bài

Cho tập hợp \(S\), định nghĩa \(f(S)\) là tập hợp thu được bằng cách XOR tất cả số trong \(S\) với \(\mathrm{mex}(S)-1\).

\(q\) yêu cầu cho \(n,k,p\), đếm số lượng \(S\) thỏa mãn:

• \(S\subseteq[0,2^k)\) và \(0\in S,|S|=n\).
• Dãy \(S,f(S),f(f(S)),\dots\) hội tụ về \(S_0\), và \(\mathrm{mex}(S_0)=p\).

Phạm vi: \(k\le 17,n,p\le 2^k,q\le 2\times 10^5\).

Phân tích

Đặt \(|S|<2^k\), cân nhắc mô tả \(p\) khi hội tụ:

• Nếu \([0,2^{k-1})\) không toàn bộ thuộc \(S\), thì giới hạn của \(S\) bằng giới hạn của \(S\) trong \([0,2^{k-1})\).
• Ngược lại \(\mathrm{mex}(S)-1\) ít nhất là \(2^{k-1}-1\):
• Nếu \(2^{k-1}\) thuộc \(S\), thì \(\mathrm{mex}(S)-1\) ít nhất là \(2^{k-1}\), lật một lần thành giới hạn của \(S\) trong \([2^{k-1},2^k)\).
• Ngược lại \(\mathrm{mex}(S)-1=2^{k-1}-1\):
• Nếu \(2^k-1\not\in S\), sau khi lật \([0,2^{k-1})\) vẫn toàn bộ, \(2^{k-1}\) vẫn không thuộc \(S\), lúc này giới hạn chính là \(2^{k-1}\).
• Ngược lại sau khi lật thành \(2^{k-1}\in S\), vấn đề là giới hạn của \(S\) trong \([2^{k-1},2^k)\) sau khi lật thấp \(k-1\) vị trí.

Dễ thấy lúc này \(p\) chắc chắn là lũy thừa của \(2\).

Cân nhắc dp mô tả, \(f_{i,j,c}\) là xét giá trị miền \([0,2^i)\), giới hạn \(p=2^j\), hiện tại \(|S|=c\}.

Nhưng chúng ta không thể xử lý tình huống sau khi lật, chú ý rằng sau khi lật chúng ta cần xử lý vấn đề con chỉ định \(2^k-1\not\in S\), các hạn chế khác giống nguyên vấn đề, đặt số phương án tương ứng là \(g_{i,j,c}\.

Điều kiện biên là \(j=i-1\), lúc này với tất cả \(2^{i-1}\le c\le 2^i-2\):

[f_{i,i-1,c}=g_{i,i-1,c}=\binom{2^{i-1}-2}{c-2^{i-1}} ]Xét trường hợp tổng quát, trước hết xử lý trường hợp đầu tiên, tức là \([0,2^{i-1})\) giới hạn là \(2^j\), \([2^{i-1},2^i)\) có thể tùy chọn:

[\begin{aligned} f_{i,j,c_0+c_1}&\gets \binom{2^{i-1}}{c_1}f_{i-1,j,c_0}\ g_{i,j,c_0+c_1}&\gets \binom{2^{i-1}-1}{c_1}f_{i-1,j,c_0} \end{aligned} ] có thể dùng NTT tối ưu, dễ bỏ qua tích chập trên \(f\).

Sau đó xử lý các trường hợp còn lại, chú ý tình huống lật chỉ xuất hiện trong \(f\):

[\begin{aligned} f_{i,j,k+2^{i-1}}&\gets f_{i-1,j,k}\ g_{i,j,k+2^{i-1}}&\gets g_{i-1,j,k}\ f_{i,j,k+2^{i-1}}&\gets g_{i-1,j,k} \end{aligned} ] trả lời khi đặc biệt \(n=2^k\} thì đáp án là \(f_{k,\log_2p,n}\).

Độ phức tạp thời gian \(\mathcal O(k^32^k+q)\).

Code mẫu

#include<bits/stdc++.h>
using namespace std;
const int N=1<<18;
namespace FastMod {
typedef unsigned long long ull;
typedef __uint128_t uLL;
ull b,m;
inline void init(ull B) { b=B,m=ull((uLL(1)<<64)/B); }
inline ull mod(ull a) {
	ull q=((uLL(m)*a)>>64),r=a-q*b;
	return r>=b?r-b:r;
}
};
#define o(x) FastMod::mod(x)
int MOD,G;
int rev[N],inv[N],giaiThua[N],nhanGiaiThua[N],w[N<<1];
int ksm(int a,int b=MOD-2) {
	int ret=1;
	for(;b;a=1ll*a*a%MOD,b=b>>1) if(b&1) ret=1ll*ret*a%MOD;
	return ret;
}
void poly_init() {
	vector <int> fr;
	for(int i=2,z=MOD-1;i*i<=z;++i) if(z%i==0) fr.push_back(i),fr.push_back(z/i);
	for(G=2;;++G) {
		bool ok=true;
		for(int z:fr) if(ksm(G,z)==1) { ok=false; break; }
		if(ok) break;
	}
	inv[1]=1;
	for(int i=2;i<N;++i) inv[i]=o(1ll*(MOD-MOD/i)*inv[MOD%i]);
	giaiThua[0]=nhanGiaiThua[0]=1;
	for(int i=1;i<N;++i) giaiThua[i]=o(1ll*giaiThua[i-1]*i),nhanGiaiThua[i]=o(1ll*nhanGiaiThua[i-1]*inv[i]);
	for(int k=1;k<=N;k<<=1) {
		int x=ksm(G,(MOD-1)/k); w[k]=1;
		for(int i=1;i<k;++i) w[i+k]=o(1ll*x*w[i+k-1]);
	}
}
int laySo(int x) { int y=1; for(;y<x;y<<=1); return y;  }
void ntt(int *f,bool idft,int n) {
	for(int i=0;i<n;++i) {
		rev[i]=(rev[i>>1]>>1);
		if(i&1) rev[i]|=n>>1;
	}
	for(int i=0;i<n;++i) if(rev[i]<i) swap(f[i],f[rev[i]]);
	for(int k=2,x,y;k<=n;k<<=1) {
		for(int i=0;i<n;i+=k) {
			for(int j=i;j<i+k/2;++j) {
				x=f[j],y=o(1ll*f[j+k/2]*w[k+j-i]);
				f[j]=(x+y>=MOD)?x+y-MOD:x+y,f[j+k/2]=(x>=y)?x-y:x+MOD-y;
			}
		}
	}
	if(idft) {
		reverse(f+1,f+n);
		for(int i=0,x=ksm(n);i<n;++i) f[i]=o(1ll*f[i]*x);
	}
}
int f[18][18][N],g[18][18][N],a[N],b[N];
int C(int x,int y) { return 1ll*giaiThua[x]*nhanGiaiThua[y]%MOD*nhanGiaiThua[x-y]%MOD; }
inline void cong(int &x,const int &y) { x=(x+y>=MOD)?x+y-MOD:x+y; }
signed main() {
	ios::sync_with_stdio(false);
	cin>>MOD,FastMod::init(MOD),poly_init();
	for(int i=1;i<18;++i) {
		int s=1<<(i-1),len=s<<1;
		memset(a,0,sizeof(int)*len);
		for(int k=0;k<s;++k) a[k]=C(s-1,k);
		ntt(a,0,len);
		for(int j=0;j<i-1;++j) {
			int *F=f[i][j],*G=g[i][j];
			memset(b,0,sizeof(int)*len);
			for(int k=0;k<s;++k) b[k]=f[i-1][j][k];
			ntt(b,0,len);
			for(int k=0;k<len;++k) b[k]=o(1ll*a[k]*b[k]);
			ntt(b,1,len);
			for(int k=0;k<len;++k) cong(G[k],b[k]),cong(F[k],b[k]),cong(F[k+1],b[k]);
			for(int k=0;k<s;++k) {
				cong(F[k+s],f[i-1][j][k]),cong(F[k+s],g[i-1][j][k]);
				cong(G[k+s],g[i-1][j][k]);
			}
		}
		if(i==1) f[1][0][1]=g[1][0][1]=1;
		else for(int k=0;k<s-1;++k) f[i][i-1][k+s]=g[i][i-1][k+s]=C(s-2,k);
	}
	int T; cin>>T;
	for(int k,n,p;T--;) {
		cin>>k>>n>>p;
		if(n==(1<<k)) cout<<(p==n)<<"\n";
		else cout<<(p==(p&-p)?f[k][__lg(p)][n]:0)<<"\n";
	}
	return 0;
}

*I. [P9884] Ant

Đề bài

Cho \(n\) lỗ, mỗi lỗ mỗi giây tối đa vào hoặc ra một con kiến.

Con kiến xuất phát từ lỗ thứ \(t\} giây thứ \(t\} sẽ đến tủ lạnh giây thứ \(a_i+t+1\), con kiến vào lỗ thứ \(t\} ít nhất phải đến tủ lạnh trước \(t-a_i-1\) giây. Tính ít nhất bao nhiêu giây sau \(m\) con kiến mỗi con qua tủ lạnh một lần.

Phạm vi: \(n\le 10^5,m\le 10^{14}\).

Phân tích

Cân nhắc nhị phân thời gian \(T\), với mỗi con kiến từ giây \(s\} xuất phát từ lỗ \(i\}, giây \(t\} đến lỗ \(j\}, hợp lệ khi và chỉ khi \(s+a_i+1\le t-a_j-1\).

Nếu chúng ta biết mỗi lỗ mỗi giây là vào kiến hay ra kiến, thì một cặp điểm bắt đầu kết thúc hợp lệ có thể coi là một cạnh, số lượng kiến hoàn thành nhiều nhất là ghép hoàn tối đa trên đồ thị hai phía.

Vì mỗi điểm bên trái nối đều là một đoạn hậu tố nghiêm ngặt giảm, do đó có thể tham lam ghép mỗi điểm bên phải.

Chúng ta chỉ cần giải quyết vấn đề mỗi lỗ là vào kiến hay ra kiến.

Chú ý rằng chúng ta có thể đảo ngược thời gian để sự kiện vào, ra kiến đổi chỗ, theo tính đối xứng không khó đoán rằng chắc chắn là một nửa thời gian đầu ra kiến, một nửa thời gian sau vào kiến.

Vậy điểm trái phải lần lượt là \(\mathcal O(n)\) khoảng, sau khi tìm ra đoạn liên tục nhỏ nhất có thể nhanh chóng duy trì quá trình ghép tối đa trên đó.

Chi tiết duy nhất là khi \(T\bmod 2=1\}, giây giữa cùng là vào kiến hay ra kiến, không妨 giả định giây này vào, ra kiến mỗi nửa, nhân tất cả trọng lượng \(\times 2\) rồi xử lý.

Chú ý rằng tất cả mảng phân biệt đều là \(a_i\) cộng trừ một hằng số, trước khi sắp xếp \(a_i\) chỉ cần hợp nhất \(\mathcal O(1)\) mảng có thứ tự.

Độ phức tạp thời gian \(\mathcal O(n\log m)\).

Code mẫu

#include<bits/stdc++.h> 
#define ll long long
using namespace std;
const int MAXN=1e5+5;
const ll inf=2.5e14;
int n,a[MAXN];
ll m;
struct thaoTac {
	ll x; int c,op;
	friend bool operator <(const thaoTac &x,const thaoTac &y) { return x.x<y.x; }
}	s[MAXN*6];
bool kiemTra(ll T) {
	int p=0;
	if(T&1) {
		for(int i=1;i<=n;++i) s[++p]={a[i]+1,2,0};
		for(int i=1;i<=n;++i) s[++p]={a[i]+T/2+1,-1,0};
		for(int i=1;i<=n;++i) s[++p]={a[i]+T/2+2,-1,0};
		for(int i=n;i>=1;--i) s[++p]={T/2-a[i],1,1};
		for(int i=n;i>=1;--i) s[++p]={T/2-a[i]+1,1,1};
		for(int i=n;i>=1;--i) s[++p]={T-a[i],-2,1};
		for(int o=1;o<6;++o) inplace_merge(s+1,s+o*n+1,s+(o+1)*n+1);
	} else {
		for(int i=1;i<=n;++i) s[++p]={a[i]+1,2,0};
		for(int i=1;i<=n;++i) s[++p]={a[i]+T/2+1,-2,0};
		for(int i=n;i>=1;--i) s[++p]={T/2-a[i],2,1};
		for(int i=n;i>=1;--i) s[++p]={T-a[i],-2,1};
		for(int o=1;o<4;++o) inplace_merge(s+1,s+o*n+1,s+(o+1)*n+1);
	}
	ll ans=0,tong=0,lt=0,rt=0;
	for(int i=1;i<p;++i) {
		(s[i].op?rt:lt)+=s[i].c;
		ll d=s[i+1].x-s[i].x;
		if(lt>=rt) ans+=rt*d,tong+=(lt-rt)*d;
		else {
			ans+=lt*d;
			ll w=min((rt-lt)*d,tong);
			tong-=w,ans+=w;
		}
	}
	return ans>=2*m;
}
void giai() {
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	ll l=0,r=inf,z=inf;
	while(l<=r) {
		ll mid=(l+r)>>1;
		if(kiemTra(mid)) z=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld\n",z);
}
signed main() {
	int T; scanf("%d",&T);
	while(T--) giai();
	return 0;
}