The 2024 ICPC Asia Hong Kong Regional Contest
題解：
https://files.cnblogs.com/files/clrs97/2024_Hong_Kong_Tutorial.pdf
Code：
A. General Symmetry
// floating point errors
#pragma GCC optimize("Ofast,unroll-loops")
// safe
// #pragma GCC optimize("O3,unroll-loops")
// doesn't work in yandex
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// doesn't work in some judges
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,tune=native")
// safe
// #pragma GCC target("sse4.2,bmi,bmi2,lzcnt,popcnt")
#include<iostream>
#include<bitset>
#include<algorithm>
using namespace std;
const int N=200005,V=1000,K=5;
int n,m,k,i,l,r,a[N];
struct BIT{
unsigned long long v[(N>>6)+1];
bool get(int x)const{return v[x>>6]>>(x&63)&1;}
void set(int x){v[x>>6]|=1ULL<<(x&63);}
void operator^=(const BIT&o){for(int i=0;i<=m;i++)v[i]^=o.v[i];}
void operator=(const BIT&o){for(int i=0;i<=m;i++)v[i]=o.v[i];}
void shiftand(const BIT&o){
for(int i=0;i<m;i++)v[i]=((v[i]>>1)+((v[i+1]&1)<<63))&o.v[i];
v[m]=(v[m]>>1)&o.v[m];
}
}occ[V+1],mask[V+1],f,save[(N>>K)+1];
inline int myabs(int x){return x>0?x:-x;}
inline bool check(int l,int r){return myabs(a[l]-a[r])<=k;}
inline int ask(int A,int B){
if(!check(A,B))return 0;
int l=((B-1)>>K)+1,r=n>>K,mid,t=0;
while(l<=r){
mid=(l+r)>>1;
int d=(mid<<K)-B;
if(A-d>=1&&save[mid].get(A-d))l=mid+1,t=d;else r=mid-1;
}
A-=t,B+=t;
while(A>1&&B<n&&check(A-1,B+1))A--,B++;
return B-A+1;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>k;
m=n>>6;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=n;i++)occ[a[i]].set(i);
for(i=2;i<=V;i++)occ[i]^=occ[i-1];
for(i=1;i<=V;i++){
l=max(i-k,1);
r=min(i+k,V);
mask[i]=occ[r];
mask[i]^=occ[l-1];
}
for(i=1;i<=n;i++){
m=i>>6;
f.shiftand(mask[a[i]]);
f.set(i);
if(i>1&&check(i-1,i))f.set(i-1);
if(!(i&((1<<K)-1)))save[i>>K]=f;
}
for(i=1;i<=n;i++){
cout<<ask(i,i);
if(i<n)cout<<" ";else cout<<"\n";
}
for(i=1;i<n;i++){
cout<<ask(i,i+1);
if(i+1<n)cout<<" ";else cout<<"\n";
}
}
B. Defeat the Enemies
#include <bits/stdc++.h>
using namespace std;
int n , m;
int a[500005] , b[500005];
const int mod = 998244353;
typedef long long ll;
void upd(int &x,int y) {
((x += y) >= mod ? (x -= mod) : 0) ;
}
int c[105] , k;
void solv() {
cin >> n >> m;
int mx = 0;
for(int i = 1;i <= n;i++) cin >> a[i];
for(int i = 1;i <= n;i++) cin >> b[i];
cin >> k;
for(int i = 1;i <= k;i++) cin >> c[i];
for(int i = 1;i <= n;i++) mx = max(mx , a[i] + b[i]) ;
vector<int> h(mx + k*2 + 1 , 1e9) ;
for(int i = 1;i <= n;i++) {
int x = mx - (a[i] + b[i]) ;
h[b[i] - 1] = min(h[b[i] - 1] , b[i] + x) ;
}
for(int i = mx + k*2 - 1; i >= 0;i--) h[i] = min(h[i] , h[i + 1]) ;
vector<ll> f(mx + k*2 + 1) ;
vector<int> g(mx + k*2 + 1) ;
ll ans = 1e18;
int cnt = 0;
for(int d = 0 ; d <= k * 2 - 2 ; d++) {
for(auto &x : f) x = 1e18;
for(auto &x : g) x = 0;
f[0] = 0; g[0] = 1;
for(int i = 0 ;i < mx + d ; i++) {
for(int j = 1 ; j <= k && i + j <= mx + d && i + j <= h[i] + d ; j++) {
if(f[i + j] > f[i] + c[j]) {
f[i + j] = f[i] + c[j] ;
g[i + j] = g[i] ;
}
else if(f[i + j] == f[i] + c[j]) {
upd(g[i + j] , g[i]) ;
}
}
}
if(f[mx + d] < ans) {
ans = f[mx + d]; cnt = g[mx + d] ;
}
else if(f[mx + d] == ans) upd(cnt , g[mx + d]) ;
}
cout << ans <<' ' << cnt << '\n' ;
return ;
}
int main() {
ios::sync_with_stdio(false) ; cin.tie(0) ;
int t ; cin >> t;
while(t--) solv() ;
}
C. The Story of Emperor Bie
#include <bits/stdc++.h>
using namespace std;
int p[500005];
int n ;
void solv() {
cin >> n;
for(int i = 1;i <= n;i++) cin >> p[i] ;
int mx = *max_element(p + 1 , p + n + 1) ;
for(int i = 1;i <= n;i++) {
if(p[i] == mx) cout << i <<' ' ;
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false) ; cin.tie(0) ;
int t ; cin >> t;
while(t--) solv() ;
}
D. Master of Both VI
#include<bits/stdc++.h>
using namespace std;
using ll=int;
const int N=5e5+1e3+7,Q=3e5+1e3+7;
int n,q,fa[N];
vector<int> g[N];
struct Mat {
ll f00,f01,f10,f11;
};
struct Vec {
ll f0,f1;
ll gmn(){return min(f0,f1);}
};
Vec operator *(const Mat &a,const Vec &b)
{
return {min(a.f00+b.f0,a.f01+b.f1),min(a.f10+b.f0,a.f11+b.f1)};
}
Mat operator *(const Mat &a,const Mat &b)
{
return {min(a.f00+b.f00,a.f01+b.f10),
min(a.f00+b.f01,a.f01+b.f11),
min(a.f10+b.f00,a.f11+b.f10),
min(a.f10+b.f01,a.f11+b.f11)};
}
struct T {
int ls,rs,cnt;
Mat v;
}t[Q*2*19];
int st[20][N],dfn[N],dc;
void dfs(int x,int f)
{
fa[x]=f;
st[0][dc]=f;
dfn[x]=++dc;
for(auto v:g[x])
{
if(v==f)
continue;
dfs(v,x);
}
}
int mn(int x,int y)
{
return dfn[x]<dfn[y]?x:y;
}
int lca(int x,int y)
{
if(dfn[x]>dfn[y])
swap(x,y);
int k=__lg(dfn[y]-dfn[x]);
return x!=y?mn(st[k][dfn[x]],st[k][dfn[y]-(1<<k)]):x;
}
vector<int> add[N],qr[N];
int rt[N],cnt;
ll w[Q];
void update(int x)
{
t[x].cnt=t[t[x].ls].cnt+t[t[x].rs].cnt;
if(!t[x].cnt)
return;
else if(!t[t[x].ls].cnt)
t[x].v=t[t[x].rs].v;
else if(!t[t[x].rs].cnt)
t[x].v=t[t[x].ls].v;
else
t[x].v=t[t[x].ls].v*t[t[x].rs].v;
}
Mat Z={0,(ll)1e9,(ll)1e9,0};
void ins(int &x,int l,int r,int p,int v)
{
if(!x)
x=++cnt;
if(l==r)
{
if(v>0)
{
t[x].cnt=1;
t[x].v={w[l]*2,w[l],w[l]*2,w[l]*2};
}
else
{
t[x].cnt=0;
t[x].v=Z;
}
return;
}
int mid=(l+r)>>1;
if(p<=mid)
ins(t[x].ls,l,mid,p,v);
else
ins(t[x].rs,mid+1,r,p,v);
update(x);
}
int merge(int x,int y,int l,int r)
{
if(!x||!y)
return x+y;
if(l==r)
return t[x].cnt?x:y;
int mid=(l+r)>>1;
t[x].ls=merge(t[x].ls,t[y].ls,l,mid);
t[x].rs=merge(t[x].rs,t[y].rs,mid+1,r);
update(x);
return x;
}
int fd;
int qry(int x,int l,int r,int p,Vec &u,ll h)
{
if(r<=p)
{
auto ru=t[x].v*u;
if(ru.gmn()<h)
{
u=ru;
return t[x].cnt;
}
}
if(l==r)
{
fd=1;
return 0;
}
int mid=(l+r)>>1;
int ret=0;
if(p>mid&&t[t[x].rs].cnt)
ret=qry(t[x].rs,mid+1,r,p,u,h);
if(!t[t[x].ls].cnt||fd)
return ret;
ret+=qry(t[x].ls,l,mid,p,u,h);
return ret;
}
int ans[Q];
void getans(int x)
{
for(auto v:g[x])
{
if(v==fa[x])
continue;
getans(v);
rt[x]=merge(rt[x],rt[v],1,q);
}
for(auto id:add[x])
ins(rt[x],1,q,abs(id),id);
for(auto id:qr[x])
{
Vec u={0,0};
fd=0;
ans[id]=qry(rt[x],1,q,id,u,w[id]*2);
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
t[0].v=Z;
cin>>n>>q;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<20;i++)
for(int j=1;j+(1<<i)-1<n;j++)
st[i][j]=mn(st[i-1][j],st[i-1][j+(1<<i-1)]);
memset(ans,-1,sizeof(ans));
for(int i=1;i<=q;i++)
{
string op;
cin>>op;
if(op[0]=='A')
{
int u,v;
cin>>u>>v>>w[i];
int p=lca(u,v);
add[u].push_back(i);
add[v].push_back(i);
add[fa[p]].push_back(-i);
}
else
{
int x;
cin>>x>>w[i];
qr[x].push_back(i);
}
}
getans(1);
for(int i=1;i<=q;i++)
if(ans[i]!=-1)
cout<<ans[i]<<"\n";
}
E. Concave Hull
#include<bits/stdc++.h>
using namespace std;
const int N=2505;
typedef long long ll;
const int mod=1e9+7;
int n,ans;
bool on[N];
struct Point{
int x,y,id;
Point(int _x=0,int _y=0,int _id=-1):x(_x),y(_y),id(_id){}
friend Point operator - (const Point &a,const Point &b){
return Point(a.x-b.x,a.y-b.y);
}
friend Point operator + (const Point &a,const Point &b){
return Point(a.x+b.x,a.y+b.y);
}
friend ll operator % (const Point &a,const Point &b){
return 1LL*a.x*b.y-1LL*a.y*b.x;
}
friend bool operator < (const Point &a,const Point &b){
return a.y==b.y?a.x<b.x:a.y<b.y;
}
inline ll len2(){
return 1LL*x*x+1LL*y*y;
}
inline int Quad(){
return y>0||(y==0&&x>0);
}
};
typedef vector<Point> poly;
inline bool Left(Point a,Point b){
return b%a>0;
}
poly A;
int Area(poly A){
int m=A.size();
int tot=0;
for(int i=0;i<m;++i){
tot=(tot+(A[i]%A[(i+1)%m]))%mod;
}
tot=(tot+mod)%mod;
return tot;
}
void calc(poly B){
sort(B.begin(),B.end(),[&](Point a,Point b){
return a.Quad()^b.Quad()?a.Quad()>b.Quad():Left(b,a);
});
for(int i=0;i<(int)B.size();++i){
if(on[B[i].id]){
rotate(B.begin(),B.begin()+i,B.end());
break;
}
}
B.push_back(B[0]);
int cnt=0;
poly st;
ll now=0;
for(auto &p:B){
while(st.size()>1&&Left(st.back()-st[st.size()-2],p-st[st.size()-2])){
now=(now-(st[st.size()-2]%st.back()))%mod;
st.pop_back();
}
if(st.size()>0){
now=(now+(st.back()%p))%mod;
}
st.push_back(p);
++cnt;
if(on[p.id]){
if(st.size()>1){
ans=(ans+cnt*((st[st.size()-2]%st.back())%mod))%mod;
}
cnt=0;
now=0;
}
ans=(ans-now)%mod;
}
reverse(B.begin(),B.end());
now=0;
for(auto &p:B){
while(st.size()>1&&Left(p-st[st.size()-2],st.back()-st[st.size()-2])){
now=(now-(st.back()%st[st.size()-2]))%mod;
st.pop_back();
}
if(st.size()>0){
now=(now+(p%st.back()))%mod;
}
st.push_back(p);
if(on[p.id]){
now=0;
}
ans=(ans-now)%mod;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
A.resize(n);
for(int i=0;i<n;++i){
cin>>A[i].x>>A[i].y;
A[i].id=i;
}
Point LTL=*min_element(A.begin(),A.end());
sort(A.begin(),A.end(),[&](Point a,Point b){
a=a-LTL;
b=b-LTL;
if((a%b)==0)return a.len2()<b.len2();
return Left(b,a);
});
poly st;
for(auto &p:A){
while(st.size()>1&&Left(st.back()-st[st.size()-2],p-st[st.size()-2])){
st.pop_back();
}
st.push_back(p);
}
for(auto &p:st){
on[p.id]=1;
}
for(auto &t:A){
if(on[t.id])continue;
poly B;
for(auto &p:A){
if(p.id!=t.id){
B.push_back(p-t);
B.back().id=p.id;
}
}
calc(B);
}
ans=(ans+mod)%mod;
ans=(1LL*(n-1)*(n-((int)st.size()))%mod*Area(st)%mod-ans+mod)%mod;
cout<<ans<<'\n';
return 0;
}
F. Money Game 2
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int N=5e5+1e3+7;
int T,n,a[N];
vector<pii> L[N],R[N];
int chk(int a,int b,int c,int d)
{
if(a>b)
return chk(a,n-1,c,d)&&chk(0,b,c,d);
if(c>d)
return chk(a,b,c,n-1)&&chk(a,b,0,d);
return a>d||c>b;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i],L[i].clear(),R[i].clear();
if(n==1)
{
cout<<a[0]<<"\n";
continue;
}
for(int r=0;r<n*2;r++)
{
int i=r%n;
auto tmp=L[(i+n-1)%n];
if(tmp.size()&&tmp.begin()->second==i)
tmp.erase(tmp.begin());
tmp.push_back({0,i});
L[i].clear();
reverse(tmp.begin(),tmp.end());
for(auto [x,y]:tmp)
{
if(!L[i].size()||x/2+a[i]!=L[i].back().first)
L[i].push_back({x/2+a[i],y});
}
reverse(L[i].begin(),L[i].end());
}
for(int r=n*2-1;r>=0;r--)
{
int i=r%n;
auto tmp=R[(i+1)%n];
if(tmp.size()&&tmp.begin()->second==i)
tmp.erase(tmp.begin());
tmp.push_back({0,i});
R[i].clear();
reverse(tmp.begin(),tmp.end());
for(auto [x,y]:tmp)
{
if(!R[i].size()||x/2+a[i]!=R[i].back().first)
R[i].push_back({x/2+a[i],y});
}
reverse(R[i].begin(),R[i].end());
}
for(int i=0;i<n;i++)
{
long long ans=0;
ans=max(ans,1ll*R[i][0].first);
for(int j=0,k=(int)R[i].size()-1;j+1<L[i].size();j++)
{
while(k>0&&chk(L[i][j].second,(i+n-1)%n,(i+1)%n,R[i][k-1].second))
k--;
ans=max(ans,1ll*R[i][k].first+L[i][j].first-a[i]);
}
cout<<ans<<" \n"[i+1==n];
}
}
}
G. Yelkrab
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e3+7;
int T,n,sz[N];
vector<int> fac[N];
int son[N][26],ans[N];
string s[N];
int t;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
for(int i=1;i<=500000;i++)
for(int j=i;j<=500000;j+=i)
fac[j].push_back(i);
cin>>T;
while(T--)
{
cin>>n;
memset(son[0],-1,sizeof(son[0]));
t=0;
for(int i=1;i<=n;i++)
ans[i]=0;
int ANS=0;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
int x=0;
for(auto c:s)
{
c-='a';
if(son[x][c]==-1)
{
son[x][c]=++t;
sz[t]=0;
memset(son[t],-1,sizeof(son[t]));
}
x=son[x][c];
sz[x]++;
for(auto p:fac[sz[x]])
{
ANS^=ans[p]*p;
ans[p]++;
ANS^=ans[p]*p;
}
}
cout<<ANS<<" \n"[i==n];
}
}
}
H. Mah-jong
#include <bits/stdc++.h>
using namespace std;
const int D = 8;
vector<int> g(D - 2) ;
typedef vector<int> vi;
typedef long long ll;
vector<pair<vi,vi> > t;
void dfs(int u) {
if(u == D - 2) {
vector<int> v(D) , lm(D);
for(int i = 0;i < D - 2;i++) {
v[i] += g[i];
v[i + 1] += g[i];
v[i + 2] += g[i];
}
for(int i = 0;i < D;i++) {
lm[i] = v[i] ;
v[i] %= 3;
}
t.push_back({v , lm}) ;
return ;
}
for(int i = 0;i < 3;i++) {
g[u] = i;
dfs(u + 1);
}
}
int n;
int a[100005];
int pre[100005][D];
int fir[D][100005];
const int D3 = 6561;
typedef pair<int,int> pii;
vector<int> tr(D);
void solv() {
cin >> n;
for(int i = 1;i <= n;i++) {
cin >> a[i] ; a[i]-- ;
}
for(int i = 1;i <= n;i++ ) {
for(int j = 0;j < D;j++) {
pre[i][j] = pre[i - 1][j];
}
fir[a[i]][pre[i][a[i]]] = i - 1; /// for num ai , the last one with <= j
pre[i][a[i]]++ ;
}
for(int j = 0;j < D;j++) fir[j][pre[n][j]] = n;
ll ans = 0;
for(auto &[v,lm] : t) {
vector<int> pre(D) , pv(D);
for(int j = 0;j < D;j++) pre[j] = ::pre[n][j] ;
int d = 0;
for(int j = 0;j < D;j++) {
pv[j] = (pre[j] - v[j] + 3) % 3;
d += pv[j] * tr[j] ;
}
vector<pii> qry;
int r = n + 1;
for(int j = 0;j < D;j++) {
if(pre[j] < lm[j]) r = -1;
else r = min(r , fir[j][pre[j] - lm[j]]) ;
}
if(r == -1) continue ;
for(int i = n;i >= 1;i--) {
r = min(r , i - 1);
if(r != -1) {
qry.push_back({r , d}) ;
}
d -= pv[a[i]] * tr[a[i]] ;
pv[a[i]]-- ;
if(pv[a[i]] < 0) pv[a[i]] += 3;
d += pv[a[i]] * tr[a[i]] ;
pre[a[i]]-- ;
if(pre[a[i]] < lm[a[i]]) {r = -1; break ;}
else r = min(r , fir[a[i]][pre[a[i]] - lm[a[i]]]) ;
}
reverse(qry.begin() , qry.end()) ;
vector<int> sum(D) , num(D3);
int hs = 0;
int nxt = 0;
for(int i = 0;i <= n;i++) {
if(i) {
hs -= sum[a[i]] * tr[a[i]] ;
sum[a[i]] = (sum[a[i]] + 1) % 3;
hs += sum[a[i]] * tr[a[i]] ;
}
num[hs]++ ;
while(nxt < qry.size() && qry[nxt].first <= i) {
ans += num[qry[nxt].second] ;
nxt++ ;
}
}
}
cout << ans << '\n';
return ;
}
int main() {
ios::sync_with_stdio(false) ; cin.tie(0) ;
dfs(0) ;
tr[0] = 1;
for(int i = 1;i < D;i++) tr[i] = tr[i - 1] * 3;
int t ; cin >> t;
while(t--) solv() ;
}
I. Ma Meilleure Ennemie
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace Pollard_Rho {
mt19937 rd(time(0));
inline int A(int x, int p) { return x >= p ? x - p : x; }
inline int D(int x, int p) { return x < 0 ? x + p : x; }
inline int Mul(int x, int y, int p) {
return D(A(x * y - (int)((long double)x * y / p) * p, p), p);
}
inline int Qpow(int x, int y, int p) {
int ans = 1;
for (; y; y >>= 1, x = Mul(x, x, p)) if (y & 1) ans = Mul(ans, x, p);
return ans;
}
inline bool Mr(int x, int b) {
int k = x - 1;
while (k) {
int cur = Qpow(b % x, k, x);
if (cur != 1 && cur != x - 1) return 0;
if ((k & 1) || cur == x - 1) return 1;
k >>= 1;
}
return 1;
}
int p[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
inline bool IsPrime(int n) {
if (n <= 1 || n == 46856248255981ll) return 0;
for(int i = 0; i < 7; i++) {
if(p[i] % n == 0)
continue;
if(n == p[i])
return 1;
if(!Mr(n, p[i]))
return 0;
}
return 1;
// if (n == 2 || n == 61) return 1;
// return Mr(n, 2) && Mr(n, 61);
}
inline int Pr(int x) {
int s = 0, t = 0, c = rd() % (x - 1) + 1;
int stp = 0, goal = 1;
int val = 1;
for (goal = 1; ; goal <<= 1, s = t, val = 1) {
for (stp = 1; stp <= goal; ++stp) {
t = A(Mul(t, t, x) + c, x);
val = Mul(val, abs(t - s), x);
if ((stp & 127) == 0) {
int d = __gcd(val, x);
if (d > 1) return d;
}
}
int d = __gcd(val, x);
if (d > 1) return d;
}
}
inline void Divide(int n, map<int, int> &ans) {
if (n <= 1) return;
if (IsPrime(n)) return void(++ans[n]);
int x = n;
while (x == n) x = Pr(n);
Divide(x, ans); Divide(n / x, ans);
}
inline map<int, int> Factor(int x) {
map<int, int> ans;
Divide(x, ans);
return ans;
}
}
int n, m;
vector<int> fac, id, wid;
const int P = 998244353;
vector<int> prod;
int qpow(int a, int b) {
b %= P - 1;
int ret = 1;
while(b) {
if(b & 1)
ret = ret * a % P;
b >>= 1;
a = a * a % P;
}
return ret;
}
signed main() {
cin >> n >> m;
if(n == 1) {
cout << m % P << "\n";
return 0;
}
auto tmp = Pollard_Rho::Factor(n);
for(auto [x, y] : tmp)
fac.push_back(x);
prod.resize(1 << fac.size(), 1);
wid.resize(prod.size());
id.resize(fac.size());
id[0] = 1;
for(int i = 1; i < fac.size(); i += 1)
id[i] = id[i - 1] * (tmp[fac[i - 1]] + 1);
for(int S = 0; S < (1 << fac.size()); S += 1)
for(int i = 0; i < fac.size(); i += 1)
if(S >> i & 1)
prod[S] *= fac[i], wid[S] += id[i];
int ID = 0;
for(int i = 0; i < fac.size(); i += 1)
ID += id[i] * tmp[fac[i]];
vector<int> dp(ID + 1, 0), wn(ID + 1, 0), wm(ID + 1, 0);
wn[ID] = n, wm[ID] = m;
for(int i = ID; i >= 0; i -= 1) {
for(int j = 0; j < fac.size(); j += 1) {
if(wn[i] % fac[j] == 0) {
wn[i - id[j]] = wn[i] / fac[j];
wm[i - id[j]] = wm[i] / fac[j];
}
}
}
for(int i = 0; i <= ID; i += 1) {
int T = 0;
for(int j = 0; j < fac.size(); j += 1)
if(wn[i] % fac[j] == 0)
T ^= 1 << j;
int ret = 0;
for(int S = T;;S = (S - 1) & T) {
int mu = __builtin_parity(S) ? -1 : 1;
int e = prod[S];
ret += mu * (wm[i] / e);
if(S) {
ret -= mu * qpow(dp[i - wid[S]], e);
}
if(!S)
break;
}
dp[i] = (ret % P + P) % P;
}
cout << dp[ID] << "\n";
return 0;
}
J. Reconstruction
#include<bits/stdc++.h>
using namespace std;
const int N=500050;
int n,ok[N];
vector<int> G[N],H[N];
struct Union_Set{
int f[N];
void init(int n){
for(int i=1;i<=n;++i){
f[i]=i;
}
}
inline int getf(int x){
return f[x]==x?x:f[x]=getf(f[x]);
}
}S;
int vis[N];
int dfs(int u,int fa){
for(auto v:H[u]){
if(v==fa)continue;
int x=dfs(v,u);
if(x)return x;
}
for(auto v:G[u]){
vis[S.getf(v)]=u;
}
for(auto v:H[u]){
if(v==fa)continue;
if(vis[v]!=u)return v;
S.f[S.getf(v)]=u;
}
return 0;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<n;++i){
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<n;++i){
int u,v;
cin>>u>>v;
H[u].push_back(v);
H[v].push_back(u);
}
S.init(n);
int rt=dfs(1,0),OK=0;
if(!rt)rt=1,OK=1;
memset(vis,0,sizeof(vis));
S.init(n);
if(OK||!dfs(rt,0)){
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(rt);
ok[rt]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:G[u]){
vis[v]=u;
}
for(auto v:H[u]){
if(vis[v]&&!ok[v]){
ok[v]=1;
q.push(v);
}
}
}
}
for(int i=1;i<=n;++i){
cout<<ok[i];
}
cout<<'\n';
return 0;
}
K. LR String
#include <bits/stdc++.h>
using namespace std;
string s ;
int q;
const int N = 5e5 + 5;
int nxt[N][2];
const int inf = 1e9;
void solv() {
cin >> s >> q;
int c[2] = {inf , inf} ;
for(int i= s.size() - 1;i >= 0;i--) {
nxt[i][0] = c[0];
nxt[i][1] = c[1];
if(s[i] == 'L') c[0] = i;
else c[1] = i;
}
while(q--) {
string t ; cin >> t;
if(s[0] == 'L' && t[0] != 'L') {
cout << "NO\n"; continue ;
}
if(s.back() == 'R' && t.back() != 'R') {
cout << "NO\n" ; continue ;
}
bool ff = 1;
int u = (t[0] == 'L' ? c[0] : c[1]);
for(int i = 1;i < t.size();i++) {
if(u >= s.size()) {
ff = 0 ; break ;
}
if(t[i] == 'L') u = nxt[u][0];
else u = nxt[u][1] ;
if(u >= s.size()) {
ff = 0 ; break ;
}
}
cout << (ff ? "YES\n" : "NO\n") ;
}
return ;
}
int main() {
ios::sync_with_stdio(false) ; cin.tie(0) ;
int t ; cin >> t;
while(t--) solv() ;
}
L. Flipping Paths
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
vector<string> s(n+5);
for(int i=1;i<=n;i++)
{
string t;
cin>>t;
s[i]=' '+t;
}
if(n==1 and m==1)
{
cout<<"YES\n0\n";
continue;
}
if(n==3 and m==3 and s[1]==" WBB" and s[2]==" BWB" and s[3]==" BBW")
{
cout<<"YES\n2\nRRDD\nDDRR\n";
continue;
}
if(n==2 and m==2 and s[1]==" BB" and s[2]==" BB")
{
cout<<"YES\n0\n";
continue;
}
if(n==1 and m==5 and s[1]==" WWWWW")
{
cout<<"YES\n0\n";
continue;
}
vector<string> ans;
int ok=0;
auto tmp=s;
auto flip=[&](char &ch){ch='B'+'W'-ch;};
for(auto ch:"BW")
{
s=tmp;
ans.clear();
for(int diag=m-2;diag>=1-n;diag--)//y-x
{
string op;
int x=1,y=1;
while(y-x<diag)flip(s[x][y]),y++,op+='R';
while(y-x>diag)flip(s[x][y]),x++,op+='D';
while(x<n and y<m)
{
if(s[x][y+1]!=ch)
{
flip(s[x][y]),y++,op+='R';
flip(s[x][y]),x++,op+='D';
}
else
{
flip(s[x][y]),x++,op+='D';
flip(s[x][y]),y++,op+='R';
}
}
while(y<m)flip(s[x][y]),y++,op+='R';
while(x<n)flip(s[x][y]),x++,op+='D';
flip(s[x][y]);
ans.push_back(op);
if(diag<=2-n)
{
int done=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]!=ch)
done=0;
}
}
if(done)
{
ok=1;
break;
}
}
}
if(ok)break;
}
if(ok)
{
cout<<"YES\n"<<ans.size()<<endl;
for(auto row:ans)
cout<<row<<endl;
}
else
{
cout<<"NO\n";
}
}
return 0;
}
M. Godzilla
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int>P;
typedef unsigned short U;
const int N=77,M=N*2,K=8,CE=N*N;
int n,m,ce,i,j,optd,optv,opt[4],f[M];
int maxd[4],two[4],twoedges[4],edge[3][3][4][2],extra[3][4];
struct E{int x,y,d,v;bool ban;}e[CE];
struct Basis{
int f,s,d,v;
bool oncircle,del;
}basis[M];
vector<int>adj[M];
int dfn,st[M],en[M],ccom,at[M],root[M],cir[M],delid[3];
struct Ranges{
vector<P>seg;
int r,nxt;
void init(int _l,int _r){
seg.clear();
r=_r;
nxt=_l;
}
void append(int l,int r){
if(nxt<l)seg.emplace_back(P(nxt,l-1));
nxt=r+1;
}
void finish(){
if(nxt>r)return;
seg.emplace_back(P(nxt,r));
}
bool find(int x)const{
for(const auto&it:seg)if(it.first<=x&&x<=it.second)return 1;
return 0;
}
void addtotree(vector<P>&v){
for(const auto&it:seg)v.emplace_back(it);
}
};
U top[4],top2[4][2];int Log[M];
inline void upu(U&a,U b){a<b?(a=b):0;}
struct RMQ{
U f[K][M][4][2];
void init(){
for(int i=1;i<=n;i++)for(int j=0;j<4;j++)for(int k=0;k<2;k++)f[0][i][j][k]=0;
}
void build(){
for(int i=1;(1<<i)<=n;i++)for(int j=1;j+(1<<i)-1<=n;j++)for(int k=0;k<4;k++){
const auto&A=f[i-1][j][k];
const auto&B=f[i-1][j+(1<<(i-1))][k];
auto&C=f[i][j][k];
if(A[0]>B[0]){
C[0]=A[0];
C[1]=max(A[1],B[0]);
}else if(A[0]<B[0]){
C[0]=B[0];
C[1]=max(A[0],B[1]);
}else{
C[0]=A[0];
C[1]=max(A[1],B[1]);
}
}
}
void fetchtop(const P&seg)const{
int k=Log[seg.second-seg.first+1];
const auto&L=f[k][seg.first];
const auto&R=f[k][seg.second-(1<<k)+1];
for(int i=0;i<4;i++){
upu(top[i],L[i][0]);
upu(top[i],R[i][0]);
}
}
void fetchtop2(const P&seg)const{
int k=Log[seg.second-seg.first+1];
const auto&L=f[k][seg.first];
const auto&R=f[k][seg.second-(1<<k)+1];
for(int i=0;i<4;i++){
const auto&A=L[i];
const auto&B=R[i];
auto&C=top2[i];
if(C[0]>=A[0]&&C[0]>=B[0]){
upu(C[1],A[A[0]==C[0]]);
upu(C[1],B[B[0]==C[0]]);
}else if(C[0]>=A[0]){
C[1]=max(C[0],B[1]);
C[0]=B[0];
}else if(C[0]>=B[0]){
C[1]=max(C[0],A[1]);
C[0]=A[0];
}else if(A[0]>B[0]){
C[1]=max(C[0],A[1]);
upu(C[1],B[0]);
C[0]=A[0];
}else if(A[0]<B[0]){
C[1]=max(C[0],B[1]);
upu(C[1],A[0]);
C[0]=B[0];
}else{
C[1]=max(C[0],A[1]);
upu(C[1],B[1]);
C[0]=A[0];
}
}
}
};
vector<RMQ>rmq[M];
inline bool cmpe(const E&a,const E&b){return a.d<b.d;}
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
inline void up(int&a,int b){a<b?(a=b):0;}
inline void solve2edges(int A,int B){
int i,j;
for(i=0;i<4;i++)twoedges[i]=0;
for(i=0;i<4;i++)if(edge[A][B][i][0])
for(j=0;j<=i;j++)if(edge[A][B][j][i==j])
up(twoedges[(i+j)&3],edge[A][B][i][0]+edge[A][B][j][i==j]);
}
inline void solve2components(int A,int B){
int i,j;
solve2edges(A,B);
static int one[4];
for(i=0;i<4;i++){
one[i]=max(extra[A][i],extra[B][i]);
two[i]=twoedges[i];
}
for(i=0;i<4;i++)if(extra[A][i])
for(j=0;j<4;j++)if(extra[B][j])
up(two[(i+j)&3],extra[A][i]+extra[B][j]);
for(i=0;i<4;i++)if(edge[A][B][i][0])
for(j=0;j<4;j++)if(one[j])
up(two[(i+j)&3],edge[A][B][i][0]+one[j]);
}
inline bool cmpv(int x,int y){return st[x]<st[y];}
inline void solve(int cntdel){
int i,j,k,x,y;
static int T,lastcom[M];
T++;
static vector<int>poolcom;
poolcom.clear();
for(i=0;i<cntdel;i++){
int o=delid[i];
x=basis[o].s;
y=at[x];
if(lastcom[y]!=T){
lastcom[y]=T;
poolcom.emplace_back(y);
}
}
int ctree=0;
static vector<P>tree[3];
for(i=0;i<cntdel;i++)tree[i].clear();
for(const auto&x:poolcom){
int S=root[x];
int L=st[S],R=en[S];
int pos=cir[x]?st[basis[cir[x]].s]:0;
static int pool[4];
pool[0]=S;
int cp=1;
for(j=0;j<cntdel;j++)if(!basis[delid[j]].oncircle){
y=basis[delid[j]].s;
if(at[y]==x)pool[cp++]=y;
}
sort(pool,pool+cp,cmpv);
static int q[4];
int top=0;
q[0]=0;
static Ranges ranges[4];
ranges[0].init(L,R);
for(i=1;i<cp;i++){
y=pool[i];
while(en[pool[q[top]]]<st[y])top--;
ranges[q[top]].append(st[y],en[y]);
q[++top]=i;
ranges[i].init(st[y],en[y]);
}
for(i=0;i<cp;i++)ranges[i].finish();
if(pos&&!basis[cir[x]].del){
for(i=0;i<cp;i++)if(ranges[i].find(pos))break;
if(!i)for(j=1;j<cp;j++)ranges[j].addtotree(tree[ctree++]);
else{
ranges[0].addtotree(tree[ctree]);
ranges[i].addtotree(tree[ctree]);
sort(tree[ctree].begin(),tree[ctree].end());
ctree++;
for(j=1;j<cp;j++)if(j!=i)ranges[j].addtotree(tree[ctree++]);
}
}else for(j=0;j<cp;j++)ranges[j].addtotree(tree[ctree++]);
}
static vector<P>all,outer;
all.clear();
outer.clear();
for(i=0;i<ctree;i++)for(const auto&it:tree[i])all.emplace_back(it);
sort(all.begin(),all.end());
int r=0;
for(const auto&it:all){
if(r+1<it.first)outer.emplace_back(P(r+1,it.first-1));
up(r,it.second);
}
if(r<n)outer.emplace_back(P(r+1,n));
for(i=0;i<ctree;i++){
for(j=0;j<4;j++)top[j]=0;
for(const auto&A:tree[i]){
const auto&ds=rmq[A.second][A.first];
for(const auto&B:tree[i]){
ds.fetchtop(B);
if(B.first==A.first)break;
}
for(const auto&B:outer)ds.fetchtop(B);
}
for(j=0;j<4;j++)extra[i][j]=e[top[j]].d;
for(j=i+1;j<ctree;j++){
for(k=0;k<4;k++)for(x=0;x<2;x++)top2[k][x]=0;
for(const auto&A:tree[i]){
const auto&ds=rmq[A.second][A.first];
for(const auto&B:tree[j])ds.fetchtop2(B);
}
for(k=0;k<4;k++)for(x=0;x<2;x++){
int id=top2[k][x];
edge[i][j][k][x]=edge[j][i][k][x]=e[id].d;
}
}
}
if(ctree==1){
for(i=0;i<4;i++)maxd[i]=extra[0][i];
return;
}
if(ctree==2){
solve2components(0,1);
for(i=0;i<4;i++)maxd[i]=two[i];
return;
}
for(i=0;i<4;i++)maxd[i]=0;
for(i=0;i<4;i++)if(edge[0][1][i][0])
for(j=0;j<4;j++)if(edge[0][2][j][0])
for(k=0;k<4;k++)if(edge[1][2][k][0])
up(maxd[(i+j+k)&3],edge[0][1][i][0]+edge[0][2][j][0]+edge[1][2][k][0]);
static int common[4];
for(i=0;i<4;i++){
common[i]=0;
for(j=0;j<3;j++)up(common[i],extra[j][i]);
}
for(int S=0;S<3;S++){
int A=(S+1)%3,B=(S+2)%3;
solve2components(A,B);
for(i=0;i<4;i++)if(two[i])
for(j=0;j<4;j++)if(extra[S][j])
up(maxd[(i+j)&3],two[i]+extra[S][j]);
for(i=0;i<4;i++)if(edge[S][A][i][0])
for(j=0;j<4;j++)if(edge[S][B][j][0])
for(k=0;k<4;k++)if(common[k])
up(maxd[(i+j+k)&3],edge[S][A][i][0]+edge[S][B][j][0]+common[k]);
for(int _=0;_<2;_++){
solve2edges(S,A);
for(i=0;i<4;i++)if(twoedges[i])
for(j=0;j<4;j++)if(edge[S][B][j][0])
up(maxd[(i+j)&3],twoedges[i]+edge[S][B][j][0]);
swap(A,B);
}
}
}
void dfs(int x,int y){
at[x]=ccom;
st[x]=++dfn;
for(const auto&id:adj[x]){
int u=basis[id].f^basis[id].s^x;
if(u==y)continue;
if(u!=basis[id].s)swap(basis[id].f,basis[id].s);
dfs(u,x);
}
en[x]=dfn;
}
inline void newcom(int S){
root[++ccom]=S;
dfs(S,0);
}
void search(int o,int x){
if(o){
solve(o);
for(int i=0;i<4;i++)if(maxd[i])up(opt[(optv+i)&3],optd+maxd[i]);
}
if(o==3)return;
for(;x<=n;x++){
optd-=basis[x].d;
(optv+=4-basis[x].v)&=3;
basis[x].del=1;
delid[o]=x;
search(o+1,x+1);
optd+=basis[x].d;
(optv+=basis[x].v)&=3;
basis[x].del=0;
}
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)for(j=1;j<=m;j++){
e[++ce].x=i;
e[ce].y=j+n;
scanf("%d",&e[ce].d);
}
ce=0;
for(i=1;i<=n;i++)for(j=1;j<=m;j++){
scanf("%d",&e[++ce].v);
e[ce].v&=3;
}
n+=m;
sort(e+1,e+ce+1,cmpe);
static bool g[M];
for(i=1;i<=n;i++)f[i]=i;
m=0;
for(i=ce;i;i--){
int x=F(e[i].x),y=F(e[i].y);
if(g[x]&&g[y])continue;
++m;
basis[m].f=e[i].x;
basis[m].s=e[i].y;
basis[m].d=e[i].d;
basis[m].v=e[i].v;
e[i].ban=1;
optd+=e[i].d;
(optv+=e[i].v)&=3;
if(x==y){
g[x]=1;
basis[m].oncircle=1;
}else{
f[x]=y;
g[y]|=g[x];
adj[e[i].x].emplace_back(m);
adj[e[i].y].emplace_back(m);
}
}
opt[optv]=optd;
for(i=1;i<=n;i++)if(basis[i].oncircle){
newcom(basis[i].f);
cir[ccom]=i;
}
for(i=1;i<=n;i++)if(!st[i])newcom(i);
for(i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
for(i=1;i<=n;i++){
rmq[i].resize(i+1);
for(j=1;j<=i;j++)rmq[i][j].init();
}
for(i=ce;i;i--)if(!e[i].ban){
int x=st[e[i].x],y=st[e[i].y],val=e[i].v;
for(int _=0;_<2;_++){
for(int r=x;r<=n;r++)for(int l=x;l;l--){
auto&f=rmq[r][l].f[0][y][val];
if(!f[0])f[0]=i;
else if(f[0]!=i&&!f[1])f[1]=i;
else break;
}
swap(x,y);
}
}
for(i=1;i<=n;i++)for(j=1;j<=i;j++)rmq[i][j].build();
search(0,1);
for(i=0;i<4;i++){
if(!opt[i])opt[i]=-1;
printf("%d\n",opt[i]);
}
}
浙公網安備 33010602011771號