Giải pháp cho Vòng 6 Cuộc thi Đa trường HDU 2023
A. Đếm
Liên kết đề bài
Tóm tắt đề bài
Đếm số lượng chuỗi có độ dài \(n\), bảng ký tự kích thước \(m\) có chu kỳ độ dài \(n-k\).
Phạm dữ liệu: \(n,m,k\le 10^{18}\).
Phân tích giải pháp
Khi \(k=n\) đáp án là \(m^n\), ngược lại chuyển sang có Border độ dài \(k\), đáp án là \(m^{n-k}\).
Độ phức tạp thời gian \(\mathcal O(\log n)\).
Mã nguồn
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=998244353;
inline int luythua(int a,int b,int p=MOD) {
a%=MOD,b%=MOD-1;
int kq=1;
while(b) kq=(b&1?kq*a%p:kq),a=a*a%p,b=b>>1;
return kq;
}
inline void giai() {
int n,m,k;
scanf("%lld%lld%lld",&n,&m,&k);
printf("%lld\n",luythua(m,k==n?n:n-k));
}
signed main() {
int T; scanf("%lld",&T);
while(T--) giai();
return 0;
}
B. Tổng Cặp và Số Chính Phương
Liên kết đề bài
Tóm tắt đề bài
Cho một hoán vị \(a\) của \(1\sim n\), \(q\) truy vấn hỏi có bao nhiêu cặp \(a_i,a_j\) trong đoạn \(a_l\sim a_r\) có tổng là số chính phương.
Phạm dữ liệu: \(n,q\le 10^5\).
Phân tích giải pháp
Xử lý brute-force tất cả các \((i,j)\), vấn đề trở thành truy vấn 2D, chú ý số lần sửa \(\mathcal O(n\sqrt n)\), số lần truy vấn \(\mathcal O(q)\), do đó đổi cây BIT thành cấu trúc chia khối có \(\mathcal O(1)\) sửa \(\mathcal O(\sqrt n)\) truy vấn để cân bằng độ phức tạp.
Độ phức tạp thời gian \(\mathcal O((n+q)\sqrt n)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int a[MAXN],vi_tri[MAXN],kq[MAXN];
struct TruyVan { int l,r,id; };
vector <TruyVan> TV[MAXN];
int m,k,lv[MAXN],rv[MAXN],thuoc[MAXN],tong[MAXN],gt[MAXN];
inline int tongkh(int l,int r) {
int kq=0;
if(thuoc[l]==thuoc[r]) {
for(int i=l;i<=r;++i) kq+=gt[i];
return kq;
}
for(int i=l;i<=rv[thuoc[l]];++i) kq+=gt[i];
for(int i=thuoc[l]+1;i<=thuoc[r]-1;++i) kq+=tong[i];
for(int i=lv[thuoc[r]];i<=r;++i) kq+=gt[i];
return kq;
}
inline void giai() {
int n,q;
scanf("%d",&n);
memset(tong,0,sizeof(tong)),memset(gt,0,sizeof(gt));
k=sqrt(n),m=(n+k-1)/k;
for(int i=1;i<=m;++i) lv[i]=(i-1)*k+1,rv[i]=min(i*k,n),fill(thuoc+lv[i],thuoc+rv[i]+1,i);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),vi_tri[a[i]]=i,TV[i].clear();
scanf("%d",&q);
for(int i=1,l,r;i<=q;++i) scanf("%d%d",&l,&r),TV[r].push_back({l,r,i});
for(int i=1;i<=n;++i) {
for(int t=1;t*t<=2*n;++t) if(1<=t*t-a[i]&&t*t-a[i]<=n) {
int j=vi_tri[t*t-a[i]];
if(j<i) ++tong[thuoc[j]],++gt[j];
}
for(auto o:TV[i]) kq[o.id]=tongkh(o.l,o.r);
}
for(int i=1;i<=q;++i) printf("%d\n",kq[i]);
}
signed main() {
int T;
scanf("%d",&T);
while(T--) giai();
return 0;
}
C. Vector
Liên kết đề bài
Tóm tắt đề bài
Cho bốn vector 3 chiều \(a_1,a_2,a_3,a_4\), xác định có tồn tại bộ nghiệm thực dương \((x,y,z)\) thỏa mãn \(a_1x+a_2y+a_3z=a_4\).
Phạm dữ liệu: Tọa độ cho trước đều là số nguyên không âm.
Phân tích giải pháp
Rõ ràng cần xét phương pháp Gauss, sau đó dựa vào \(\mathrm{span}(a_1,a_2,a_3)\) thảo luận một số trường hợp đặc biệt:
- \(\mathrm{span}(a_1,a_2,a_3)\) là không gian toàn bộ: trực tiếp dùng phương pháp Gauss.
- \(\mathrm{span}(a_1,a_2,a_3)\) là một mặt phẳng: xác định \(a_4\) có nằm trên mặt phẳng không, sau đó xác định \(a_4\) có nằm trong góc giữa một cặp vector nào đó trên mặt phẳng.
- \(\mathrm{span}(a_1,a_2,a_3)\) là một đường thẳng / một điểm: xác định \(a_4\) có cùng hướng với đường thẳng / là vector không.
Độ phức tạp thời gian \(\mathcal O(1)\).
Mã nguồn
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Vector{
int x,y,z;
Vector(int xx=0,int yy=0,int zz=0):x(xx),y(yy),z(zz){};
inline void nhap() {
scanf("%lld%lld%lld",&x,&y,&z);
}
inline friend Vector operator+(Vector ls,Vector rs) {
return Vector(ls.x+rs.x,ls.y+rs.y,ls.z+rs.z);
}
inline friend Vector operator-(Vector ls,Vector rs) {
return Vector(ls.x-rs.x,ls.y-rs.y,ls.z-rs.z);
}
inline friend Vector operator*(Vector ls,int k) { return Vector(ls.x*k,ls.y*k,ls.z*k); }
inline friend int nhanvoi(Vector ls,Vector rs) { return ls.x*rs.x+ls.y*rs.y+ls.z*rs.z; }
inline friend bool operator==(Vector ls,Vector rs) {
return ls.x==rs.x&&ls.y==rs.y&&ls.z==rs.z;
}
inline friend bool operator!=(Vector ls,Vector rs) {
return ls.x!=rs.x||ls.y!=rs.y||ls.z!=rs.z;
}
inline friend Vector tichhvh(Vector ls,Vector rs) {
return Vector(ls.y*rs.z-ls.z*rs.y,ls.z*rs.x-ls.x*rs.z,ls.x*rs.y-ls.y*rs.x);
}
};
bool cunghuong(Vector u,Vector v){
Vector c=tichhvh(u,v);
if(c.x||c.y||c.z) return false;
if(u.x*v.x<0||u.y*v.y<0||u.z*v.z<0) return false;
return true;
}
const long double eps=1e-8;
const Vector v0={0,0,0};
void giai(){
Vector a,b,c,d;
a.nhap(),b.nhap(),c.nhap(),d.nhap();
// ba vector không.
if(a==v0&&b==v0&&c==v0) return puts(d==v0?"YES":"NO"),void();
// hai vector không / đồng tuyến
if(cunghuong(a,b)&&cunghuong(b,c)&&cunghuong(c,a)) {
return puts(cunghuong(d,a)&&cunghuong(d,b)&&cunghuong(d,c)?"YES":"NO"),void();
}
// một vector không, không đồng tuyến
if(a==v0||b==v0||c==v0){
if(a==v0) swap(a,c);
if(b==v0) swap(b,c);
if(nhanvoi(tichhvh(a,b),d)) return puts("NO"),void();
if(cunghuong(d,a)||cunghuong(d,b)) return puts("YES"),void();
return puts(!cunghuong(tichhvh(d,a),tichhvh(d,b))?"YES":"NO"),void();
}
// không có vector không, một cặp đồng tuyến và vector khác
if(cunghuong(a,b)||cunghuong(b,c)||cunghuong(a,c)) {
if(cunghuong(a,b)) swap(a,c);
if(cunghuong(a,c)) swap(a,b);
if(nhanvoi(tichhvh(a,b),d)) return puts("NO"),void();
if(cunghuong(d,a)||cunghuong(d,b)) return puts("YES"),void();
return puts(!cunghuong(tichhvh(d,a),tichhvh(d,b))?"YES":"NO"),void();
}
// a,b,c cùng mặt phẳng
if(!nhanvoi(tichhvh(a,b),c)) {
auto kiemtra=[&](Vector a,Vector b,Vector d) {
if(nhanvoi(tichhvh(a,b),d)) return false;
if(cunghuong(d,a)||cunghuong(d,b)) return true;
return !cunghuong(tichhvh(d,a),tichhvh(d,b));
};
if(kiemtra(a,b,d)||kiemtra(b,c,d)||kiemtra(c,a,d)) return puts("YES"),void();
return puts("NO"),void();
}
// không có vector không, không có cặp đồng tuyến.
long double e[3][4];
e[0][0]=a.x,e[0][1]=b.x,e[0][2]=c.x,e[0][3]=d.x;
e[1][0]=a.y,e[1][1]=b.y,e[1][2]=c.y,e[1][3]=d.y;
e[2][0]=a.z,e[2][1]=b.z,e[2][2]=c.z,e[2][3]=d.z;
for(int i=0;i<3;++i) {
for(int j=i;j<3;++j) {
if(fabs(e[j][i])>eps) { swap(e[i],e[j]); break; }
}
assert(fabs(e[i][i])>eps);
for(int j=3;j>=i;--j) e[i][j]/=e[i][i];
for(int k=i+1;k<3;++k) {
for(int j=3;j>=i;--j) e[k][j]-=e[k][i]*e[i][j];
}
}
long double x[3];
x[0]=e[0][3],x[1]=e[1][3],x[2]=e[2][3];
for(int i=2;~i;--i) {
for(int j=i-1;~j;--j) x[j]-=x[i]*e[j][i];
}
if(x[0]<-eps||x[1]<-eps||x[2]<-eps) puts("NO");
else puts("YES");
}
signed main(){
int T; scanf("%lld",&T);
while(T--) giai();
return 0;
}
D. Cây
Liên kết đề bài
Tóm tắt đề bài
Cho một cây \(n\) đỉnh, mỗi đỉnh trên đường đi có màu trong \(\{1,2,3\}\), đếm số đường đi mà số lượng các đỉnh mỗi màu bằng nhau.
Phạm dữ liệu: \(n\le 10^5\).
Phân tích giải pháp
Sử dụng trực tiếp chia trị trên cây, ghi nhận hiệu số lượng đỉnh màu \(1/2\) và \(2/3\) trên đường đi.
Độ phức tạp thời gian \(\mathcal O(n\log n)\).
Mã nguồn
#include<bits/stdc++.h>
#define ll int long long
using namespace std;
const int MAXN=1e5+5;
int n,cur[MAXN],siz[MAXN],mau[MAXN]; ll ans=0;
bool vis[MAXN];
vector <int> G[MAXN];
inline void giai(int u) {
auto Hash=[&](array<int,2> arr) -> ll { return arr[0]*100000ll+arr[1]; };
unordered_map <array<int,2>,int,decltype(Hash)> cnt(0,Hash);
// cnt.push_back({rt[0]-rt[1],rt[1]-rt[2]});
if(mau[u]==0) ++cnt[{1,0}];
if(mau[u]==1) ++cnt[{-1,1}];
if(mau[u]==2) ++cnt[{0,-1}];
for(int v:G[u]) if(!vis[v]) {
vector <array<int,3>> thongtin;
auto dfs=[&](auto self,int u,int fa,array<int,3> pa) -> void {
++pa[mau[u]],thongtin.push_back(pa);
for(int v:G[u]) if(v!=fa&&!vis[v]) self(self,v,u,pa);
};
dfs(dfs,v,u,{0,0,0});
for(auto I:thongtin) ans+=cnt[{I[1]-I[0],I[2]-I[1]}];
for(auto I:thongtin) ++I[mau[u]],++cnt[{I[0]-I[1],I[1]-I[2]}];
}
}
inline void dfs(int u) {
vis[u]=true,giai(u);
for(int v:G[u]) if(!vis[v]) {
int goc=0,tong=siz[v];
auto tim=[&](auto self,int u,int fa) -> void {
siz[u]=1,cur[u]=0;
for(int v:G[u]) if(!vis[v]&&v!=fa) {
self(self,v,u);
cur[u]=max(cur[u],siz[v]);
siz[u]+=siz[v];
}
cur[u]=max(cur[u],tong-siz[u]);
if(!goc||cur[u]<cur[goc]) goc=u;
};
tim(tim,v,u);
dfs(goc);
}
}
char str[MAXN];
signed main() {
scanf("%d%s",&n,str+1);
for(int i=1;i<=n;++i) mau[i]=str[i]-'a';
for(int i=1,u,v;i<n;++i) {
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
E. Cánh Đồng
Liên kết đề bài
Tóm tắt đề bài
Cho một lưới \(n\times m\), mỗi ô có màu \(c_{i,j}\) và giá trị \(v_{i,j}\), với một ma trận con vuông toàn đen \([i,i+k-1]\times[j,j+k-1]\), giá trị của nó được định nghĩa là tổng giá trị trong ma trận con nhân với \(k\).
Tính tổng giá trị của tất cả ma trận con vuông trong lưới.
Phạm dữ liệu: \(n,m\le 1000\).
Phân tích giải pháp
Xét góc trên trái \((i,j)\), tìm nhị phân giá trị lớn nhất \(k\) sao cho \([i\sim i+k]\times [j\sim j+k]\) là ma trận toàn đen.
Gọi \(S_{i,j}\) là tổng tiền二维 của \(v_{i,j}\), thì đáp án cho ma trận con góc trên trái tại \(i,j\) là:
[\sum_{t=0}^k (t+1)\times (S_{i+t,j+t}-S_{i+t,j-1}-S_{i-1,j+t}+S_{i-1,j-1}) ]Mở rộng và xử lý riêng biệt, phát hiện chúng ta chỉ cần xử lý hàng, cột, đường chéo của \(S_{i,j}\), và cũng như \(i\times S_{i,j}\) của cột và đường chéo, sử dụng tiền xử lý là đủ.
Độ phức tạp thời gian \(\mathcal O(nm\log n)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005,MOD=1e9+7,i2=(MOD+1)/2;
int den[MAXN][MAXN];
struct mint {
int v;
mint(int w=0) { v=(0<=w&&w<MOD)?w:(MOD+w%MOD)%MOD; }
inline friend mint operator +(mint a,mint b) { return a.v+b.v>=MOD?a.v+b.v-MOD:a.v+b.v; }
inline void operator +=(mint o) { v=v+o.v>=MOD?v+o.v-MOD:v+o.v; }
inline void operator +=(int o) { v=v+o>=MOD?v+o-MOD:v+o; }
inline friend mint operator -(mint a,mint b) { return a.v>=b.v?a.v-b.v:a.v+MOD-b.v; }
inline void operator -=(mint o) { v=v>=o.v?v-o.v:v+MOD-o.v; }
inline friend mint operator *(mint a,mint b) { return 1ll*a.v*b.v%MOD; }
inline void operator *=(mint o) { v=1ll*v*o.v%MOD; }
};
mint gt[MAXN][MAXN],cot[MAXN][MAXN][2],hang[MAXN][MAXN][2],cheo[MAXN][MAXN][2];
inline void giai() {
int n,m; cin>>n>>m;
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
cin>>den[i][j],den[i][j]^=1;
den[i][j]+=den[i][j-1]+den[i-1][j]-den[i-1][j-1];
}
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
int x; cin>>x;
gt[i][j]=x+gt[i][j-1]+gt[i-1][j]-gt[i-1][j-1];
}
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
hang[i][j][0]=hang[i][j-1][0]+gt[i][j];
hang[i][j][1]=hang[i][j-1][1]+gt[i][j]*j;
cot[i][j][0]=cot[i-1][j][0]+gt[i][j];
cot[i][j][1]=cot[i-1][j][1]+gt[i][j]*i;
cheo[i][j][0]=cheo[i-1][j-1][0]+gt[i][j];
cheo[i][j][1]=cheo[i-1][j-1][1]+gt[i][j]*i;
}
}
mint ans=0;
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
int L=0,R=min(n-i,m-j),T=-1;
while(L<=R) {
int mid=(L+R)>>1;
if(den[i+mid][j+mid]+den[i-1][j-1]==den[i+mid][j-1]+den[i-1][j+mid]) {
T=mid,L=mid+1;
} else R=mid-1;
}
if(T==-1) continue;
ans+=cheo[i+T][j+T][1]-cheo[i-1][j-1][1];
ans-=(i-1)*(cheo[i+T][j+T][0]-cheo[i-1][j-1][0]);
ans-=hang[i-1][j+T][1]-hang[i-1][j-1][1];
ans+=(j-1)*(hang[i-1][j+T][0]-hang[i-1][j-1][0]);
ans-=cot[i+T][j-1][1]-cot[i-1][j-1][1];
ans+=(i-1)*(cot[i+T][j-1][0]-cot[i-1][j-1][0]);
ans+=gt[i-1][j-1]*(T+1)*(T+2)*i2;
}
}
cout<<ans.v<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int T; cin>>T;
while(T--) giai();
return 0;
}
F. Số Chính Phương Hoàn Hảo
Liên kết đề bài
Tóm tắt đề bài
Cho một dãy \(a_1\sim a_n\) có giá trị trong \([1,V]\) với \(V=300\), định nghĩa \(f(a)\) là số lượng cặp \((l,r)\) sao cho \(\sum_{i=l}^ra_i\) là số chính phương.
Thay đổi một \(a_i\) thành giá trị bất kỳ trong \([1,V]\), tìm giá trị lớn nhất có thể của \(f(a')\).
Phạm dữ liệu: \(n\le 300\).
Phân tích giải pháp
Chú ý rằng chúng ta chỉ cần duy trì \(f_{i,x}\) - đáp án khi thay \(a_i\) thành \(x\), xét một đoạn \(a_l\sim a_r\), xét làm cho tổng đoạn từ \(S\) thành \(k^2\), tương đương với việc tăng thêm 1 cho mỗi \(f_{i,k^2-S}\), sử dụng hiệu để duy trì.
Xử lý riêng biệt các đoạn bị giảm đi.
Độ phức tạp thời gian \(\mathcal O(n^2V)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=305,V=300;
int a[MAXN];
inline void giai() {
int n,tong=0;
scanf("%d",&n);
unordered_map <int,vector<int>> cnt;
for(int i=-V;i<=V;++i) cnt[i].resize(n+2,0);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int l=1;l<=n;++l) {
for(int r=l,s=0;r<=n;++r) {
s+=a[r];
for(int v=1;v<=V;++v) {
int k=v*v-s;
tong+=(k==0);
if(-V<=k&&k<=V) ++cnt[k][l],--cnt[k][r+1];
}
}
}
int ans=tong;
for(int k=-V;k<=V;++k) {
for(int i=1;i<=n;++i) {
cnt[k][i]+=cnt[k][i-1];
}
}
for(int k=-V;k<=V;++k) {
for(int i=1;i<=n;++i) {
if(1<=a[i]+k&&a[i]+k<=V) {
ans=max(ans,tong+cnt[k][i]-cnt[0][i]);
}
}
}
printf("%d\n",ans);
}
signed main() {
int T; scanf("%d",&T);
while(T--) giai();
return 0;
}
G. Cuộc Thi
Liên kết đề bài
Tóm tắt đề bài
Bạn đang chơi một trò chơi, ban đầu có hai số \(x=1,y=0\), trò chơi có \(n\) vòng, mỗi vòng có hai trường hợp:
- Nếu thắng: \(y\gets y+2,x\gets x\times y\), trước cộng sau nhân.
- Nếu thua: \(y\gets y-1\).
Biết bạn thua đúng \(k\) vòng, tìm tổng của \(x\) trên tất cả các quá trình trò chơi có thể.
Phạm dữ liệu: \(n\le 1.5\times10^5,k\le 10^5\).
Phân tích giải pháp
Ghi nhận \(f_{n,k}\) là đáp án khi \(n\) vòng thua \(k\) vòng, dễ có công thức chuyển: \(f_{n,k}=f_{n-1,k-1}+(2n-3k)f_{n-1,k}\).
Xét hàm sinh, đặt \(F_n(x)=\sum x^kf_{n,k}\), có: \(F_n(x)=xF_{n-1}(x)+2nF_{n-1}(x)-3xF_{n-1}'(x)\).
Gộp \(xF_{n-1}(x)-3xF'_{n-1}(x)\) thành một hạng, chú ý \((e^{-x/3}f(x))'=e^{-x/3}f'(x)-\dfrac 13e^{-x/3} f(x)\).
Do đó đặt \(G_{n}(x)=e^{-x/3}F_n(x)\), có \(G_n'(x)=\dfrac 13(3e^{-x/3}F_{n-1}(x)-e^{-x/3}F_{n-1}(x))\).
Nhận được công thức chuyển mới: \(G_n(x)=-3xG_{n-1}'(x)+2nG_{n-1}(x)\), mở rộng có: \(g_{n,k}=2n\times g_{n-1,k}-3k\times g_{n-1,k}\).
Do đó \(g_{n,k}=g_{0,k}\prod_{i=1}^n(2i-3k)\), trong đó \(g_{0,k}=[x^k]e^{-x/3}\), đáp án cuối cùng nhân với hệ số thứ \(k\) của \(e^{x/3}\) chính là đáp án.
Xét cách tính \(c_k=\prod_{i=1}^n(2i-3k)\), tính trực tiếp \(c_0,c_1\), sau đó phát hiện \(c_k=c_{k-2}\times\dfrac{2-3k}{2+2n-3k}\times \dfrac{4-3k}{4+2n-3k}\times \dfrac{6-3k}{6+2n-3k}\), từ đó có thể đệ quy.
Theo khai triển Taylor có \(e^{x/3}=\sum_{k=0}^\infty \dfrac{x^k}{3^k\times k!}, e^{-x/3}=\sum_{k=0}^\infty \dfrac{(-1)^k\times x^k}{3^k\times k!}\), tính trực tiếp là được.
Độ phức tạp thời gian \(\mathcal O(n\log P)\), cài đặt tỉ mỉ có thể đạt \(\mathcal O(n)\).
Mã nguồn
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+5,MOD=998244353,i3=(MOD+1)/3;
int giaithua[MAXN],igiaithua[MAXN],f[MAXN],g[MAXN];
inline int luythua(int a,int b=MOD-2,int p=MOD) {
int kq=1;
while(b) kq=(b&1?kq*a%p:kq),a=a*a%p,b=b>>1;
return kq;
}
signed main() {
int n,k;
scanf("%lld%lld",&n,&k),n+=k;
for(int i=giaithua[0]=igiaithua[0]=1;i<=n;++i) igiaithua[i]=luythua(giaithua[i]=i*giaithua[i-1]%MOD);
for(int i=0;i<=k;++i) { //e^{-x/3}
f[i]=luythua(i3,i)*igiaithua[i]%MOD;
if(i&1) f[i]=(MOD-f[i])%MOD;
}
for(int j:{0,1}) {
g[j]=1;
for(int i=1;i<=n;++i) g[j]=(2*i+3*(MOD-j))%MOD*g[j]%MOD;
}
for(int j=2;j<=k;++j) {
//g[j] = prod_{i=1~n}(2i-3j)
int t=3*(MOD-j)%MOD;
g[j]=g[j-2]*luythua((2*n+t+6)%MOD)%MOD*luythua((2*n+t+4)%MOD)%MOD*luythua((2*n+t+2)%MOD)%MOD;
g[j]=g[j]*(2+t)%MOD*(4+t)%MOD*(6+t)%MOD;
}
for(int j=0;j<=k;++j) f[j]=f[j]*g[j]%MOD;
int ans=0;
for(int j=0;j<=k;++j) { //convolution with e^{x/3}
ans=(ans+f[k-j]*luythua(i3,j)%MOD*igiaithua[j]%MOD)%MOD;
}
printf("%lld\n",ans);
return 0;
}
H. Alice và Bob
Liên kết đề bài
Tóm tắt đề bài
Cho một dãy dài \(n\), hai người A và B轮流 thực hiện thao tác, mỗi người có thể chia dãy thành hai phần, giữ lại phần có tổng giá trị lớn hơn, người không thể thao tác thua.
Nếu một người chắc chắn thắng, thì tối đa hóa số nhận được cuối cùng, ngược lại thì cực tiểu hóa số nhận được cuối cùng, xác định ai thắng và số nhận được cuối cùng.
Phạm dữ liệu: \(n\le 3000\).
Phân tích giải pháp
Xét dp trên đoạn, đặt \(dp_{l,r}\) là đáp án cho đoạn \(l,r\), nếu người đi trước chắc chắn thắng thì dương, ngược âm, tìm điểm giữa \(mid\) của dãy sao cho \(S(l,mid)\ge S(mid+1,r)\), có công thức chuyển:
[dp_{l,r}=-\min\left{\min_{k=l+1}^{mid}dp_{k,r}\ ,\ \min_{k=mid}^{r-1} dp_{l,k}\right} ]Chú ý trong quá trình chuyển, cùng một \(dp_{l,*}\), các đoạn truy vấn chắc chắn đơn điệu về bên phải, tối ưu bằng hàng đợi, tương tự \(dp_{*,r}\).
Độ phức tạp thời gian \(\mathcal O(n^2)\).
Mã nguồn
#include<bits/stdc++.h>
#pragma GCC optimize(2,3,"Ofast")
#define ll long long
using namespace std;
mt19937 rnd(time(0));
const int MAXN=3003,inf=2e9;
struct HANGDOI {
int val[MAXN],q[MAXN],hd,tl,last;
inline int query(int l,int r) {
if(l>r) return inf;
assert(last<=r);
for(int i=last+1;i<=r;++i) {
while(hd<=tl&&val[q[tl]]>=val[i]) --tl;
q[++tl]=i;
}
last=r;
while(hd<=tl&&q[hd]<l) ++hd;
return val[q[hd]];
}
inline void clear() { hd=1,tl=0,last=0; }
} trc[MAXN],sau;
ll s[MAXN];
inline ll tong(int l,int r) { return l<=r?s[r]-s[l-1]:0; }
int n,a[MAXN],dp[MAXN][MAXN],o[MAXN][MAXN];
void giai() {
cin>>n;
for(int i=1;i<=n;++i) trc[i].clear();
for(int i=1;i<=n;++i) cin>>a[i],s[i]=s[i-1]+a[i];
for(int i=1;i<=n;++i) {
dp[i][i]=-a[i];
trc[i].val[n-i+1]=dp[i][i];
trc[i].last=n-i;
}
for(int l=n;l>=1;--l) {
sau.clear(),sau.last=l-1,sau.val[l]=dp[l][l];
for(int r=l+1,mid=l;r<=n;++r) {
mid=max(mid,l);
while(mid<r&&tong(l,mid)<tong(mid+1,r)) ++mid;
dp[l][r]=-min(trc[r].query(n-mid+1,n-l),sau.query(mid,r-1));
sau.val[r]=dp[l][r];
trc[r].val[n-l+1]=dp[l][r];
}
}
if(dp[1][n]>0) cout<<"Alice "<<abs(dp[1][n])<<"\n";
else cout<<"Bob "<<abs(dp[1][n])<<"\n";
}
int main() {
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int T; cin>>T;
while(T--) giai();
return 0;
}
I. Màu Sắc
Liên kết đề bài
Tóm tắt đề bài
Cho một đồ thị vô hướng liên thông \(n\) đỉnh \(m\) cạnh, mỗi đỉnh và cạnh đều có giá trị, và các giá trị cạnh đôi một khác nhau.
Với một cạnh \(e\), khi và chỉ khi tồn tại một đường đi \(u\to v\) sao cho \(e\) là cạnh lớn nhất trên đường đi và \(val(u)\ge val(e)\), thì \(u\in S(e)\).
Với mỗi điểm có chi phí tô đen hoặc tô trắng, với mỗi cạnh yêu cầu số lượng đen trong \(S(e)\) không vượt quá \(x(e)\), số lượng trắng không vượt quá \(y(e)\), tìm chi phí tô màu nhỏ nhất. Đảm bảo có lời giải.
Phạm dữ liệu: \(n\le 1000\).
Phân tích giải pháp
Chú ý \(S(e)\) chính là các điểm trong cây重构 Kruskan của \(e\) có \(val(u)\ge val(e)\), xét mô hình luồng, trước hết tô trắng tất cả các điểm, sau đó dùng luồng đến \(e\) để thể hiện số lượng đen trong \(S(e)\), truyền trên cây重构 Kruskan là được, còn điều kiện \(val(u)\ge val(e)\) thì nối cạnh ngược từ mỗi \(u\) đến điểm đầu tiên có \(val(e)>val(u)\) để loại bỏ.
Để giới hạn \(x(e),y(e)\), chia mỗi điểm thành hai điểm, nối cạnh giới hạn trên dưới giữa chúng để giới hạn số lượng đen trong \(S(e)\), vấn đề chuyển thành luồng khả thi chi phí nhỏ nhất có giới hạn trên không có nguồn đích, chuyển thành luồng cực đại chi phí nhỏ nhất thông thường, do có thể có chu trình âm, cần thêm một cặp nguồn đích chạy luồng xóa chu trình chi phí nhỏ.
Độ phức tạp thời gian \(\mathcal O(n^3)\).
Mã nguồn
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Canh0 { int v,last,f,c; }; //cạnh trong spfa
struct Canh1 { int u,v,f,c; }; //cạnh trong đồ thị mạng
struct Canh2 { int u,v,w,l0,l1; }; //cạnh trong cây gốc
namespace MCMF {
const int MAXV=1e4+5,MAXE=2e5+5,inf=1e18;
Canh0 G[MAXE];
int ecnt=1,hd[MAXV];
inline void them(int u,int v,int f,int c) {
G[++ecnt]={v,hd[u],f,c},hd[u]=ecnt;
}
inline void lien(int u,int v,int f,int c) {them(u,v,f,c),them(v,u,0,-c); }
int dis[MAXV],last[MAXV],pre[MAXV]; //last: cạnh cuối, pre: đỉnh cuối
bool trong[MAXV];
inline bool SPFA(int S,int T) {
memset(dis,0x3f,sizeof(dis));
memset(last,-1,sizeof(last));
memset(pre,-1,sizeof(pre));
memset(trong,false,sizeof(trong));
queue <int> Q;
Q.push(S),dis[S]=0,trong[S]=true;
while(!Q.empty()) {
int u=Q.front(); Q.pop();
trong[u]=false;
for(int i=hd[u];i;i=G[i].last) if(G[i].f&&dis[u]+G[i].c<dis[G[i].v]) {
int v=G[i].v;
dis[v]=dis[u]+G[i].c;
pre[v]=u,last[v]=i;
if(!trong[v]) trong[v]=true,Q.push(v);
}
}
return ~pre[T];
}
int chi,luong;
inline void tang(int S,int T) {
int g=inf;
for(int u=T;u!=S;u=pre[u]) g=min(g,G[last[u]].f);
luong+=g,chi+=g*dis[T];
for(int u=T;u!=S;u=pre[u]) G[last[u]].f-=g,G[last[u]^1].f+=g;
}
int bac[MAXV];
inline array<int,2> SSP(const vector<Canh1>&N,int s,int t,int tot) {
int S=++tot,T=++tmp,tmp=0;
for(auto e:N) {
if(e.c>=0) {
lien(e.u,e.v,e.f,e.c);
} else {
bac[e.u]-=e.f,bac[e.v]+=e.f;
tmp+=e.f*e.c;
lien(e.v,e.u,e.f,-e.c);
}
}
for(int i=1;i<=tot-2;++i) {
if(bac[i]>0) lien(S,i,bac[i],0);
else lien(i,T,-bac[i],0);
}
lien(t,s,inf,0);
while(SPFA(S,T)) tang(S,T);
luong=0;
while(SPFA(s,t)) tang(s,t);
return {luong,chi+tmp};
}
inline void init() {
chi=0,luong=0,ecnt=1;
memset(hd,0,sizeof(hd));
memset(bac,0,sizeof(bac));
}
}
const int MAXN=2005,inf=1e18;
int val[MAXN],c0[MAXN],c1[MAXN];
int dsu[MAXN],l0[MAXN],l1[MAXN],cha[MAXN];
inline int tim(int x) { while(x^dsu[x]) x=dsu[x]=dsu[dsu[x]]; return x; }
int s[MAXN],t[MAXN],siz[MAXN],bac[MAXN];
inline void giai() {
int n,m,ans=0;
cin>>n>>m;
MCMF::init();
vector <Canh1> N;
vector <Canh2> E(m);
for(int i=1;i<=n;++i) cin>>c0[i]>>c1[i]>>val[i];
for(auto &e:E) cin>>e.u>>e.v>>e.w;
for(auto &e:E) cin>>e.l0;
for(auto &e:E) cin>>e.l1;
sort(E.begin(),E.end(),[&](auto e1,auto e2){ return e1.w<e2.w; });
iota(dsu+1,dsu+n+1,1);
int p=n,tot=n;
for(auto &e:E) {
int x=tim(e.u),y=tim(e.v);
if(x==y) continue;
++p,dsu[p]=dsu[x]=dsu[y]=p,cha[x]=cha[y]=p;
l0[p]=e.l0,l1[p]=e.l1,val[p]=e.w;
s[p]=++tot,t[p]=++tot,siz[p]=0;
}
auto lien=[&](int u,int v,int l,int r,int c) {
bac[u]-=l,bac[v]+=l;
N.push_back({u,v,r-l,c});
};
for(int i=1;i<=n;++i) {
lien(i,s[cha[i]],0,1,c1[i]-c0[i]);
ans+=c0[i];
int u;
for(u=cha[i];u&&val[i]>=val[u];u=cha[u]) ++siz[u];
if(u) lien(s[u],i,0,1,0);
else lien(t[p],i,0,1,0);
}
for(int i=n+1;i<=p;++i) {
lien(s[i],t[i],max(0ll,siz[i]-l0[i]),l1[i],0);
if(i<p) lien(t[i],s[cha[i]],0,inf,0);
}
int s=++tot,t=++tot;
for(int i=1;i<=tot-2;++i) {
if(bac[i]>0) lien(s,i,0,bac[i],0);
else lien(i,t,0,-bac[i],0);
bac[i]=0;
}
cout<<ans+MCMF::SSP(N,s,t,tot)[1]<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int T; cin>>T;
while(T--) giai();
return 0;
}
J. Tính Toán
Liên kết đề bài
Tóm tắt đề bài
Cho một đồ thị có hướng cơ sở, bạn có một số \(x\), đi qua một đỉnh \(i\) sẽ làm \(x\gets k_ix+b_i\).
\(q\) truy vấn: từ \(u\) xuất phát với giá trị ban đầu \(x_0\) đi \(d\) bước sau \(x\) là bao nhiêu.
Phạm dữ liệu: \(n,q\le 10^5,V=\max d\le 10^9\).
Phân tích giải pháp
Do hàm biến đổi một lần có thể hợp nhất, do đó trực tiếp duy trì mảng nhân lên là được.
Độ phức tạp thời gian \(\mathcal O((n+q)\log V)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,MOD=1e9+7;
int cha[MAXN][31];
struct ThongTin {
int k,b;
inline friend ThongTin operator *(ThongTin u,ThongTin v) { return {1ll*u.k*v.k%MOD,(1ll*u.b*v.k+v.b)%MOD}; }
} th[MAXN][31],I[MAXN];
inline void giai() {
int n,q; cin>>n>>q;
for(int i=1;i<=n;++i) cin>>I[i].k;
for(int i=1;i<=n;++i) cin>>I[i].b;
for(int i=1;i<=n;++i) cin>>cha[i][0],th[i][0]=I[cha[i][0]];
for(int k=1;k<31;++k) for(int i=1;i<=n;++i) {
cha[i][k]=cha[cha[i][k-1]][k-1];
th[i][k]=th[i][k-1]*th[cha[i][k-1]][k-1];
}
for(int x,d,u;q--;) {
cin>>u>>d>>x;
ThongTin I={1,0};
for(int k=0;k<31;++k) if(d&(1<<k)) I=I*th[u][k],u=cha[u][k];
cout<<(1ll*I.k*x+I.b)%MOD<<"\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int T; cin>>T;
while(T--) giai();
return 0;
}
K. Chuỗi
Liên kết đề bài
Tóm tắt đề bài
Cho một chuỗi \(S\), \(q\) truy vấn cho chuỗi \(T\), chọn ngẫu nhiên một chuỗi con \(T'\) của \(T\), tìm kỳ vọng số lượng chuỗi con của \(S\) chứa \(T'\).
Phạm dữ liệu: \(n=|S|\le 10^6,m=\sum |T|\le 10^6\).
Phân tích giải pháp
Xét \(T=S\), xây dựng SAM, quan sát mỗi lớp tương đương \(\{r_1,r_2,\dots,r_k\}\) của \(S\), số lượng chuỗi con tương ứng là \(\sum_{i=1}^k (r_{i+1}-r_i)\times l_i\), trong đó \(r_{k+1}=n+1\).
Dễ thấy số lượng phương án là hàm bậc nhất của độ dài chuỗi \(len\) \(f\), dùng cây đoạn hợp nhất để duy trì \(f\), đáp án của mỗi nút đều là tổng của một đoạn của \(f\).
Sau đó xét trường hợp tổng quát, xét một tiền tố của \(T\), dễ dàng khớp với một đoạn hậu缀 dài nhất trên SAM của \(S\) và nút tương ứng, đáp án là tổng đóng góp của tổ tiên trên cây Parent của nút này cộng với đóng góp của nút này, chú ý đóng góp của nút này có thể không đầy (đoạn không nhất giới hạn trên) cần tính riêng.
Độ phức tạp thời gian \(\mathcal O(n\log n+m)\).
Mã nguồn
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5,MOD=998244353;
int n,q;
char s[MAXN],t[MAXN];
struct ThongTin {
int lp,rp,b;
inline friend ThongTin operator +(ThongTin L,ThongTin R) {
if(!L.lp) return R;
if(!R.lp) return L;
int g=R.lp-L.rp,b=(L.b+R.b)%MOD;
return {L.lp,R.rp,(b+1ll*(L.rp+1)*g%MOD)%MOD};
}
};
class CayDoan {
private:
struct Node {
int ls,rs;
ThongTin I; //f(x) = ax+b
} tr[MAXN*20];
inline void lenl(int p) { tr[p].I=tr[tr[p].ls].I+tr[tr[p].rs].I; }
int siz;
public:
inline void init() {
for(int i=1;i<=siz;++i) tr[i]={0,0,{0,0,0}};
siz=0;
}
inline void Chen(int u,int l,int r &p) {
p=++siz;
if(l==r) return tr[p].I={l,r,0},void();
int mid=(l+r)>>1;
if(u<=mid) Chen(u,l,mid,tr[p].ls);
else Chen(u,mid+1,r,tr[p].rs);
lenl(p);
}
inline void Hopnhat(int l,int r,int q &p) {
if(!q||!p) return p|=q,void();
if(l==r) return tr[p].I={l,r,0},void();
int mid=(l+r)>>1;
Hopnhat(l,mid,tr[q].ls,tr[p].ls),Hopnhat(mid+1,r,tr[q].rs,tr[p].rs);
lenl(p);
}
inline int xuat(int u,int l,int r,int p) {
if(!p) return 0;
if(l==r) return 1;
int mid=(l+r)>>1;
return u<=mid?xuat(u,l,mid,tr[p].ls):xuat(u,mid+1,r,tr[p].rs);
}
inline ThongTin Query(int p) { return tr[p].I; }
} TR;
int rt[MAXN<<1];
struct Node {
map <char,int> ch;
int link,len;
} tr[MAXN<<1];
int tot,last;
inline int chen(char c) {
int cur=++tot,p=last;
tr[cur].len=tr[last].len+1;
while(p&&!tr[p].ch.count(c)) tr[p].ch[c]=cur,p=tr[p].link;
if(!p) tr[cur].link=1;
else {
int q=tr[p].ch[c];
if(tr[q].len==tr[p].len+1) tr[cur].link=q;
else {
int r=++tot;
tr[r]=tr[q],tr[r].len=tr[p].len+1;
tr[q].link=tr[cur].link=r;
while(p&&tr[p].ch[c]==q) tr[p].ch[c]=r,p=tr[p].link;
}
}
return last=cur;
}
vector <int> G[MAXN<<1];
int gt[MAXN<<1],a[MAXN<<1],b[MAXN<<1];
inline int tinh(int a,int b,int lo,int hi) { //ax+b when lo<x<=hi
auto c1=[&](int x) { return 1ll*x*(x+1)/2%MOD; };
auto c0=[&](int x) { return x; };
int ans=0;
ans=(ans+1ll*a*(c1(hi)+MOD-c1(lo))%MOD)%MOD;
ans=(ans+1ll*b*(c0(hi)+MOD-c0(lo))%MOD)%MOD;
return ans;
}
inline int luythua(int a,int b=MOD-2,int p=MOD) {
int kq=1;
while(b) kq=(b&1?1ll*kq*a%p:kq),a=1ll*a*a%p,b=b>>1;
return kq;
}
inline void dfs0(int u) {
for(int v:G[u]) dfs0(v),TR.Hopnhat(1,n,rt[v],rt[u]);
ThongTin I=TR.Query(rt[u]);
int g=(n+1-I.rp);
a[u]=MOD-(n+1-I.lp),b[u]=(I.b+1ll*g*(I.rp+1)%MOD)%MOD;
gt[u]=tinh(a[u],b[u],tr[tr[u].link].len,tr[u].len);
}
inline void dfs1(int u) {
for(int v:G[u]) gt[v]=(gt[v]+gt[u])%MOD,dfs1(v);
}
inline void giai() {
TR.init();
memset(rt,0,sizeof(rt));
for(int i=1;i<=tot;++i) tr[i].link=tr[i].len=0,tr[i].ch.clear(),G[i].clear();
tot=last=1;
scanf("%d%d%s",&n,&q,s+1);
for(int i=1;i<=n;++i) TR.Chen(i,1,n,rt[chen(s[i])]);
for(int i=2;i<=tot;++i) G[tr[i].link].push_back(i);
dfs0(1),dfs1(1);
while(q--) {
scanf("%s",t+1);
int m=strlen(t+1),p=1,ans=0;
for(int i=1,len=0;i<=m;++i) {
if(tr[p].ch.count(t[i])) p=tr[p].ch[t[i]],++len;
else {
while(p&&!tr[p].ch.count(t[i])) p=tr[p].link;
if(!p) p=1,len=0;
else len=tr[p].len+1,p=tr[p].ch[t[i]];
}
if(p!=1) {
ans=(ans+gt[tr[p].link])%MOD;
ans=(ans+tinh(a[p],b[p],tr[tr[p].link].len,len))%MOD;
}
}
printf("%lld\n",1ll*ans*luythua((1ll*m*(m+1)/2)%MOD)%MOD);
}
}
signed main() {
int T; scanf("%d",&T);
while(T--) giai();
return 0;
}