コンテストリンク
\(\text{著者：DaiRuiChen007}\)
A. [UOJ702] 張飛の精鋭兵団 (3.5)
問題リンク
コンテストの過程を木として捉え、値を大きい順に埋めていく。制約は親子のトポロジカル順序であり、係数が\(-1\)の層を優先的に埋める。もし埋められない場合は、子ノードが最も多く、勝利回数が最も多いノードを選ぶ。
コードに落とし込むと複雑度を効率的に改善できる。
計算時間 \(\mathcal O(n\log P)\)。
コード：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5,MOD=998244353,Q=MOD-1;
ll ksm(ll a,ll b,ll p=MOD) { ll s=1; for(;b;a=a*a%p,b>>=1) if(b&1) s=s*a%p; return s; }
ll ans=0,m;
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n; cin>>n,m=ksm(2,n,Q);
for(int i=n;~i;--i) {
ll c=(i==n);
if(i<=n-2) c=ksm(2,n-2-i,Q);
int t=(m+(Q-1-i)*c)%Q;
ans=(ans+(ksm(2,m)+MOD-ksm(2,t))*ksm(ksm(2,i+1)-1,MOD-2))%MOD,m=t;
}
cout<<ans<<"\n";
return 0;
}
B. [UOJ703] 趙雲の八門陣 (4.5)
問題リンク
線形基底における末尾要素のランクを保持する動的計画法を考える。\(a_i\) を追加した際に線形基底が変化するか否かで状態を分ける。基底が変化しない場合、末尾要素のランクは+1される。変化する場合、そのランク変化を高速に処理する。
より良い手法としては、線形基底に挿入されたすべての要素\(b_1\sim b_m\)を取り出し、もし\(b_i\)が答えに含まれるなら\([b_i,n]\)も含まれる。そのため、状態は\([b_i,n]\)中に\(j\)個の\(b\)要素とすべての非\(b\)要素があるときの最大の先頭要素を記録すればよい。
計算時間 \(\mathcal O(n\log V)\)。
コード：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5;
struct LB {
ll b[64];
bool ins(ll x) {
for(int i=59;~i;--i) if(x>>i&1) {
if(!b[i]) {
for(int j=i-1;~j;--j) if(x>>j&1) x^=b[j];
b[i]=x;
for(int j=i+1;j<60;++j) if(b[j]>>i&1) b[j]^=x;
return 1;
} else x^=b[i];
}
return 0;
}
ll rnk(ll x) {
ll k=0,z=0;
for(int i=59;~i;--i) if(b[i]) {
k<<=1;
if((z^b[i])<x) k|=1,z^=b[i];
}
return k;
}
ll val(ll k) {
ll x=0;
for(int i=0;i<60;++i) if(b[i]) {
x^=(k&1?b[i]:0),k>>=1;
}
return x;
}
ll pre(ll x,ll w) {
for(int i=59;~i;--i) x=min(x,x^b[i]);
if(x>=w) return -1;
for(int i=59;~i;--i) if((x^b[i])<w) x^=b[i];
return x;
}
} B[64];
int n,m,p[64];
ll a[MAXN],f[64];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=n;++i) if(B[m+1].ins(a[i])) p[m++]=i,B[m+1]=B[m];
p[m]=n+1,f[0]=1ll<<60,fill(f+1,f+m+1,-1);
ll z=0,s=0;
for(int i=m-1;~i;--i) {
ll c=p[i+1]-p[i]-1;
if(c) {
for(int j=0;j<=m-i;++j) if(f[j]>0) {
ll t=B[i+1].rnk(f[j]);
z=max(z,j+s+min(c,t+1));
if(t>=c) f[j]=B[i+1].val(t-c+1);
else f[j]=-1;
}
s+=c;
}
for(int j=m-i;~j;--j) if(~f[j]) f[j+1]=max(f[j+1],B[i].pre(a[p[i]],f[j]));
}
for(int i=0;i<=m;++i) if(~f[i]) z=max(z,s+i);
cout<<z<<"\n";
return 0;
}
C. [UOJ704] 馬超の潼関戦 (5)
問題リンク
残余ネットワークを縮約して、\(S\)を含む導出部分グラフの数を数える。
単純な再帰では\(\mathcal O(2^{2n})\)の複雑度になるが、メモ化再帰を行うと、探索していない部分集合のみを気にすれば、前\(n\)個の頂点は\(2^n\)通りの集合があり、後\(n\)個の頂点については\(2^n\)通りの状態のみメモ化される。複雑度は\(\mathcal O(n2^n)\)。
マッチングされていない頂点は必ず\(S\)の後続または\(T\)の先行となるため、気にする必要はない。
マッチングされた頂点の右端はただ一つの出辺を持つため、両方の端点を同時に決定すると、その後の集合には2つの異なる貢献しか生まれず、頂点数は\(n\)に減る。
計算時間 \(\mathcal O(n2^{n/2})\)。
コード：
#include<bits/stdc++.h>
#define ull unsigned long long
#define LL __int128
using namespace std;
struct Edge { int v,f,e; } G[2005];
int S,T,ec=1,hd[105],cur[105],d[105];
void link(int u,int v,int w) {
G[++ec]={v,w,hd[u]},hd[u]=ec;
G[++ec]={u,0,hd[v]},hd[v]=ec;
}
bool bfs() {
memset(d,-1,sizeof(d)),memcpy(cur,hd,sizeof(hd));
queue <int> Q; d[S]=0,Q.push(S);
while(Q.size()) {
int u=Q.front(); Q.pop();
for(int i=hd[u];i;i=G[i].e) if(G[i].f&&d[G[i].v]<0) d[G[i].v]=d[u]+1,Q.push(G[i].v);
}
return ~d[T];
}
int dfs(int u,int f) {
if(u==T) return f;
int r=f;
for(int &i=cur[u];i;i=G[i].e) if(d[G[i].v]==d[u]+1&&G[i].f) {
int g=dfs(G[i].v,min(G[i].f,r));
if(!g) d[G[i].v]=-1;
r-=g,G[i].f-=g,G[i^1].f+=g;
if(!r) return f;
}
return f-r;
}
int n,m,dfn[105],low[105],dcnt,st[105],tp,bl[105],scnt,vis[105];
bool ins[105];
vector <int> E[105];
void tarjan(int u) {
dfn[u]=low[u]=++dcnt,ins[st[++tp]=u]=1;
for(int i=hd[u];i;i=G[i].e) if(G[i].f) {
int v=G[i].v;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]) for(++scnt;ins[u];ins[st[tp--]]=0) bl[st[tp]]=scnt;
}
int k=0,h,id[105],fa[105],in[105];
LL L[105],R[105],a[105],U[105];
mt19937_64 rnd(time(0)); ull hv[105][2];
unordered_map<ull,LL>g;
ull hs(LL s) {
ull w=0;
for(int i=0;i<k;++i) w^=hv[i][s>>i&1];
return w;
}
LL dp(int i,LL s) {
if(i<0) return 1;
if(s>>i&1) return dp(i-1,s&U[i]);
ull o=hs(s|((LL)1<<i));
if(g.count(o)) return g[o];
return g[o]=dp(i-1,s&U[i])+dp(i-1,(s|a[i])&U[i]);
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m,S=2*n+1,T=S+1;
for(int i=1;i<=n;++i) link(S,i,1),link(i+n,T,1);
for(int i=1,u,v;i<=m;++i) cin>>u>>v,link(u,v+n,1);
while(bfs()) dfs(S,n);
for(int i=1;i<=T;++i) if(!dfn[i]) tarjan(i);
for(int u=1;u<=T;++u) for(int i=hd[u];i;i=G[i].e) if(G[i].f&&bl[u]!=bl[G[i].v]) E[bl[u]].push_back(bl[G[i].v]);
for(int i=1;i<=scnt;++i) {
L[i]=R[i]=(LL)1<<i;
for(int j:E[i]) R[i]|=R[j];
}
for(int i=scnt;i;--i) for(int j:E[i]) L[j]|=L[i];
for(int u=1;u<=n;++u) for(int i=hd[u];i;i=G[i].e) if(!G[i].f&&G[i].v<=2*n) if(bl[u]!=bl[G[i].v]) fa[bl[u]]=bl[G[i].v];
for(int i=1;i<=scnt;++i) id[i]=-1,in[i]=(R[bl[S]]|L[bl[T]])>>i&1;
for(int i=1;i<=scnt;++i) if(!in[i]&&id[i]<0) {
id[i]=k++;
for(int j=1;j<=i;++j) if((R[i]>>j&1)&&~id[j]) a[id[i]]|=(LL)1<<id[j];
if(fa[i]&&!in[fa[i]]) id[fa[i]]=k++,a[id[fa[i]]]=a[id[i]]|((LL)1<<id[fa[i]]);
}
for(int i=0;i<k;++i) U[i]=((LL)1<<i)-1,hv[i][0]=rnd(),hv[i][1]=rnd();
LL z=dp(k-1,0);
string Z; for(;z;z/=10) Z+=z%10+'0';
reverse(Z.begin(),Z.end()),cout<<Z<<"\n";
return 0;
}
D. [UOJ705] 黄忠の慶功宴 (5)
問題リンク
\(k\le \sqrt p\)の場合、累積和を使用する。\(k^{-1}\le \sqrt p\)の場合は、\(k^{-1}\)個の区間に分割できる。
\(k\)を\(x\times y^{-1}\)の形式に分解し、\(x,y=\mathcal O( \sqrt p)\)とする。\(ky\)が\(0\sim \sqrt p\)で取る値は\(0\sim p\)環上で最も近い2点の距離が\(\le\sqrt p\)であるため、これらの点を引いて\(y\in [-\sqrt p,\sqrt p]\)を得る。
\(x\)ごとに累積和を処理し、\(k^{-1}\le\sqrt p\)の処理を行う。
計算時間 \(\mathcal O((p+q)\sqrt p)\)。
コード：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5,B=800;
int p,q,a[MAXN],e[MAXN][2];
ll iv[MAXN],f[MAXN],s[MAXN];
ll qs(int l,int r) { return r<p?s[r+1]-s[l]:s[p]-s[l]+s[r-p+1]; };
void ad(int&x,const int&y){ x=x+y>=p?x+y-p:x+y; }
vector <array<int,4>> qy[MAXN];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>p>>q,iv[1]=1;
for(int i=2;i<p;++i) iv[i]=iv[p%i]*(p-p/i)%p;
for(int i=0;i<p;++i) cin>>a[i];
for(int i=1;i<p;++i) for(int k=1,r=i;!e[i][1];++k,ad(r,i)) {
if(r<=B) e[i][0]=r,e[i][1]=k;
if(r>=p-B) e[i][0]=p-r,e[i][1]=-k;
}
for(int i=1,x,k,l;i<=q;++i) cin>>x>>k>>l,x=(x-1+k-1)%p,qy[e[k][0]].push_back({x,e[k][1],l,i});
for(int x=1;x<=B;++x) if(qy[x].size()) {
for(int i=0,u=0;i<p;++i,ad(u,x)) s[i+1]=s[i]+a[u];
for(auto o:qy[x]) {
int u=o[0],y=o[1],c=o[2],k=x*iv[(y+p)%p]%p; ll &z=f[o[3]];
if(y<0) u=(u+1ll*(c-1)*k)%p,y=-y;
int h=iv[y],d=c/y-1,t=c%y; u=u*iv[x]%p;
for(int i=0;i<y;++i,ad(u,h)) z+=qs(u,u+d+(i<t));
}
}
for(int i=1;i<=q;++i) cout<<f[i]<<"\n";
return 0;
}
E. [UOJ1004] 王の沈殿 (4)
問題リンク
\(\texttt ?\to \texttt U\)の数を列挙し、検証時は各\(01\)シーケンスを判定し、境界線を列挙して両端から走査し、高速に判定する。
計算時間 \(\mathcal O(nk)\)。
コード：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,MAXK=1005,MOD=998244353;
int n,m,a[MAXN],f[MAXN],b[MAXN],z[MAXN],C[MAXK][MAXK];
int qry(int x,int y) {
int c=0,p=1,w=1,s=1;
for(int k=1;k<n;++k) {
auto upd=[&]() { while(p<n&&s<w) s+=a[++p]>k; };
s-=b[k]<=p,upd();
while((n-p)-(n-k-s)>1ll*c*y) ++c,w+=x,upd();
}
return c;
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string o;
cin>>n>>m>>o;
for(int i=0;i<=m;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
int U=0,D=0;
for(auto i:o) U+=i=='U',D+=i=='D';
for(int i=1;i<=n;++i) cin>>a[i],b[a[i]]=i;
for(int i=0,x;i<=m-U-D;++i) x=qry(U+i,m-U-i),z[x]=(z[x]+C[m-U-D][i])%MOD;
for(int i=0;i<n;++i) cout<<z[i]<<" \n"[i==n-1];
return 0;
}
*F. [UOJ1005] 王の钦定 (7)
問題リンク
極長な色数\(\le 2\)の区間を取り出し、\(l,r\)がそれぞれ増加し、\(r_i=1) { if(~l&1) s=s+tr[l^1]; if(r&1) s=s+tr[r^1]; } return s; } void ins(int x,auto&Z) { int o=h,p=0; ll z=0; for(int w=2;h;--h) { int q=b[h]; if(2*a[q]a[p]) swap(p,q); if(q) Z.push_back({b[h],z=max(z,a[x]%a[q]+a[q])}); } for(int i=h+1;in>>m>>ty; for(int i=1;i>a[i],tr[i+N]={i,0}; for(int i=N-1;i;--i) tr[i]=tr[ir,l=(l-1+z)%n+1,r=(r-1+z)%n+1; auto o=mx(l,r); z=max(qry(l,r,o.x)+a[o.y],qry(l,r,o.y)+a[o.x]%a[o.y]); cout