D1T1 季风
心梗题。
设 \(sx_i=\sum\limits_{j\le i} x_j\)，\(sy_i\) 同理。枚举 \(r=m\bmod n\)，设 \(m=p\cdot n+r\)，那么当 \(|x-(p\cdot sx_n+sx_r)|+|y-(p\cdot sy_n+sy_r)|\) 不超过 \((p\cdot n+r)k\)，一定存在合法的方案，即解关于 \(p\) 的绝对值不等式：
\[|x-(p\cdot sx_n+sx_r)|+|y-(p\cdot sy_n+sy_r)|\le (p\cdot n+r) k \]分类讨论，解不等式，时间复杂度 \(O(n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pir pair<ll,ll>
#define fi first
#define se second
#define mkp make_pair
using namespace std;
const ll maxn=1e6+10, G=5e12;
ll t,n,k,X,Y,x[maxn],y[maxn],ans;
pir calc(ll tx,ll dx,ll ty,ll dy,ll t){
if(n*k-dx-dy==0){
if(tx+ty-t*k<=0) return mkp(-G,G);
return mkp(G,G);
}
if(n*k-dx-dy<0){
return mkp(-G,(ll)floor(1.0*(tx+ty-t*k)/(n*k-dx-dy)));
}
return mkp((ll)ceil(1.0*(tx+ty-t*k)/(n*k-dx-dy)),G);
}
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld%lld%lld",&n,&k,&X,&Y);
for(ll i=1;i<=n;i++){
scanf("%lld%lld",x+i,y+i);
x[i]+=x[i-1], y[i]+=y[i-1];
} ans=5e18;
for(ll i=0;i<n;i++){
ll tx=X-x[i], ty=Y-y[i], dx=-x[n], dy=-y[n];
ll p1=G-1, p2=G-1;
if((__int128)tx*dx<0) p1=-tx/dx;
if((__int128)ty*dy<0) p2=-ty/dy;
if(p1<=p2){
pir res=calc(abs(tx),tx<0? -dx:dx,abs(ty),ty<0? -dy:dy,i);
res.fi=max(res.fi,0ll), res.se=min(res.se,p1);
if(res.fi<=res.se) ans=min(ans,res.fi*n+i);
res=calc(-abs(tx),tx<0? dx:-dx,abs(ty),ty<0? -dy:dy,i);
res.fi=max(res.fi,p1+1), res.se=min(res.se,p2);
if(res.fi<=res.se) ans=min(ans,res.fi*n+i);
res=calc(-abs(tx),tx<0? dx:-dx,-abs(ty),ty<0? dy:-dy,i);
res.fi=max(res.fi,p2+1), res.se=min(res.se,G);
if(res.fi<=res.se) ans=min(ans,res.fi*n+i);
} else{
pir res=calc(abs(tx),tx<0? -dx:dx,abs(ty),ty<0? -dy:dy,i);
res.fi=max(res.fi,0ll), res.se=min(res.se,p2);
if(res.fi<=res.se) ans=min(ans,res.fi*n+i);
res=calc(abs(tx),tx<0? -dx:dx,-abs(ty),ty<0? dy:-dy,i);
res.fi=max(res.fi,p2+1), res.se=min(res.se,p1);
if(res.fi<=res.se) ans=min(ans,res.fi*n+i);
res=calc(-abs(tx),tx<0? dx:-dx,-abs(ty),ty<0? dy:-dy,i);
res.fi=max(res.fi,p1+1), res.se=min(res.se,G);
if(res.fi<=res.se) ans=min(ans,res.fi*n+i);
}
}
if(ans>=(G-2)*n) printf("-1\n");
else printf("%lld\n",ans); }
return 0;
}
D1T2 魔法手杖
建立字典树，当我们选择了一个 \(x\) 时，相当于在对应层中交换所有左右儿子，然后拎出一些数字，改为 \(+x\)。
考虑贪心，从高到低看看每一位是否可以填 \(1\)。
维护一个点 \(u\)，表示在字典树上我们考虑点 \(u\) 的子树，一开始 \(u=rt\)。
我们在贪心的过程中再维护一个值 \(w\) 表示改为 \(+x\) 的数字在之前的决策后的最小数字还需要加 \(+w\) 才能使答案合法。
设当前填第 \(bit\) 位，我们需要时时刻刻保持 \(w<2^{bit}\)。
当 \(u\) 只有左儿子时，\(x\) 这一位填 \(1\)。此时检查 \(w\) 对下一位是否合法，合法则把 \(2^{bit-1}\) 加入答案并递归，否则直接递归。
当 \(u\) 只有右儿子时：
-
当 \(w<0\) 时，答案这一位都填 \(1\)，然后更新 \(w\)。
-
当 \(w\ge 2^{bit-1}\) 时，我们必须让 \(w\) 变小，考虑只在 \(x\) 这一位填 \(1\)，注意这样会把右边转到左边。
-
当 \(0\le w<2^{bit-1}\) 时，此时 \(x\) 这一位填不填 \(1\) 都可以。填 \(1\) 就是 \(w\) 贡献，不填 \(1\) 就是递归贡献。
当 \(u\) 两个儿子都有时：
考虑 \(x\) 填不填 \(1\)。
-
填 \(1\)：左右交换，\(w\) 差距会缩小，答案这一位填 \(1\) 的条件是能买掉右子树内所有数，由于此时右子树内所有数 \(+x\) 的贡献无需考虑，因此条件为 \(w\) 合法。
-
填 \(0\)：不交换，条件是能买掉左子树所有数，并且 \(w\) 和左子树最小值合法。
这样不用递归就能确定答案是否填 \(1\)。
若答案填 \(1\)，则对应地，递归左边和右边，取个最大值。
若答案不填 \(1\)，分讨也比较简单。
每个点递归一次，时间复杂度 \(O(nk)\)，实现时有一定细节。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pir pair<ll,ll>
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
using namespace std;
const ll maxn=1e5+10;
const __int128 INF=((__int128)1<<122);
ll t,n,m,k,b[maxn],tot=1,trie[maxn*120][2],sum[maxn*120];
__int128 a[maxn],mn[maxn*120];
__int128 min(const __int128 a,const __int128 b){return a<b? a:b;}
__int128 max(const __int128 a,const __int128 b){return a>b? a:b;}
void rd(__int128 &x){
char c;
while(!isdigit(c=getchar())) ;
x=c-'0';
while(isdigit(c=getchar())) x=x*10+c-'0';
}
void wt(const __int128 x){
if(x>9) wt(x/10);
putchar('0'+x%10);
}
void ins(const __int128 &x,const ll &v){
ll p=1; sum[1]+=v;
for(ll i=k;i;i--){
ll c=(x>>i-1)&1;
if(!trie[p][c]) trie[p][c]=++tot;
p=trie[p][c]; sum[p]+=v;
mn[p]=min(mn[p],x&(((__int128)1<<i-1)-1));
}
}
__int128 dp(ll bit,ll u,__int128 minx,ll k,ll ft){
if(bit==-1) return 0;
__int128 w=((__int128)1<<bit);
ll fl=0, lc=trie[u][0], rc=trie[u][1];
if(!rc){
if(minx<w) return dp(bit-1,lc,minx,k,ft)|w;
return 2*w-1-minx;
}
if(!lc){
if(minx<0) return dp(bit-1,rc,minx+w,k,ft)|w;
if(minx>=w) return dp(bit-1,rc,minx-w,k,1);
return max(dp(bit-1,rc,minx-w,k,1),w-1-minx);
}
if(sum[lc]<=k&&max(ft? -INF:w-mn[lc],minx+w)<w||sum[rc]<=k&&minx<w) fl=1;
if(fl){
__int128 res=-INF;
if(sum[lc]<=k&&max(ft? -INF:w-mn[lc],minx+w)<w) res=max(res,dp(bit-1,rc,max(minx+w,ft? -INF:w-mn[lc]),k-sum[lc],ft));
if(sum[rc]<=k&&minx<w) res=max(res,dp(bit-1,lc,minx,k-sum[rc],ft));
return res|w;
}
__int128 res=dp(bit-1,rc,minx-w,k,1);
if(minx<w) res=max(res,dp(bit-1,lc,minx,k,ft));
if(sum[lc]<=k) res=max(res,min(mn[lc],-minx)+w-1);
if(sum[rc]<=k) res=max(res,2*w-1-minx);
return res;
}
int main()
{
scanf("%*lld%lld",&t);
memset(mn,0x3f,sizeof mn);
while(t--){
scanf("%lld%lld%lld",&n,&m,&k);
ll s=0;
for(ll i=1;i<=n;i++) rd(a[i]);
for(ll i=1;i<=n;i++){
scanf("%lld",b+i);
ins(a[i],b[i]), s+=b[i];
}
if(s<=m){
__int128 g=INF;
for(ll i=1;i<=n;i++) g=min(g,a[i]);
g+=((__int128)1<<k)-1;
wt(g); puts("");
} else{
wt(dp(k-1,1,-INF,m,0)); puts("");
}
for(ll i=1;i<=tot;i++) trie[i][0]=trie[i][1]=sum[i]=0, mn[i]=INF;
tot=1;
}
return 0;
}
D1T3 虫洞
其实就是猜结论（？）
首先每个编号的边对应地组成一个排列。
考虑 \(m=k=1\) 的做法，在给出地排列中，发现只能在大小相同地环之间连边，并且连边是环形的。
我们猜测：已经确定了编号 \(1\sim p-1\) 的排列后，对应的 \((p-1)n\) 条边连成的所有连通块中，编号为 \(p\) 的排列只能连通同构的连通块。
这个同构比较抽象，其实就是去掉标号后，（不去掉边的编号）图的形态相同。
这个结论我一万年都猜不出来
这样，我们考虑先在原图中计算每一个同构的类中有多少个连通块，然后独立地计算答案。
先思考如何处理同构问题。注意到一个连通块中，每一个点都“同构”（感性理解吧），考虑从一个点开始 DFS，从小到大遍历边，记录下搜到的每条边的编号 + 到达的点的时间戳，哈希处理。
几个同构的连通块在 \(k\) 轮连边后会形成几个新的连通块，考虑 DP 计算答案。
这个 DP 很简单，我们实际要算的是几个同构的连通块最终形成一个大连通块的方案数。
设 \(f[i,j,p]\) 表示 \(i\) 轮连边，一开始 \(j\) 个同构的连通块最后形成一个连通块，且每个连通块大小为 \(p\) 的方案数。
枚举一轮后的连通块个数 \(x\)，有
\[f[i,j,p]=\sum_{x|j} g[i,x]f[i-1,x,\frac {jp}x]\cdot p^{j-x+1} \]其中 \(g[i,j]\) 为 \(i\) 个点分成 \(j\) 个大小相同的圆排列的方案数。
发现 \(p\) 这一维用处不大，且 \(p\) 会作为因子传入下一个状态，容易发现 \(f[i,j,p]=f[i,j,1]\cdot p^{i+j-1}\)。
默认第三维为 \(1\)，改设状态为 \(f[i,j]\)，有
\[f[i,j]\sum_{x|j} g[i,x]f[i-1,x] \cdot (\frac jx)^{i+x-2} \]尝试矩阵乘法，但是系数中带 \(i\)，不好处理。
注意 \((\frac jx)^{i-x+2}=(\frac jx)^{i-1}\cdot (\frac jx) ^{x-1}\)，考虑矩阵乘法中记录下“乘的次数”，对应到 \(i-1\)，这样就可以直接算了。
注意到一个矩阵中只有 \(j|i\) 的位置 \((i,j)\) 是合法的，考虑直接拎出这些位置处理即可。
时间复杂度 \(O(\text{可过})\)。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pir pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn=2010, mod=998244353;
ll n,m,k,fac[maxn],ifac[maxn],g[maxn][maxn],to[maxn][maxn],C[maxn][maxn];
const ull base=13331; ull val; ll siz;
ll dfn[maxn], tim;
void dfs(ll u){ dfn[u]=++tim; ++siz;
for(ll i=1;i<=m;i++){
ll v=to[u][i]; val=val*base+i;
if(!dfn[v]){
dfs(v);
} val=val*base+dfn[v];
}
}
map<pair<ull,ll>,ll>mp;
vector<pir>vec[maxn]; ll tot, id[maxn][maxn], Pow[maxn][maxn];
struct mat{
ll ti,dat[maxn<<5],pw[maxn];
const mat operator* (const mat t) const{
mat res; memset(res.dat,0,sizeof res.dat);
for(ll i=1;i<=n;i++)
for(pir j:vec[i]){ ll tmp=t.pw[i/j.se];
for(pir k:vec[j.se])
res.dat[id[i][k.se]]=(res.dat[id[i][k.se]]+dat[j.fi]*t.dat[k.fi]%mod*tmp)%mod;
}
res.ti=ti+t.ti;
for(ll i=1;i<=n;i++) res.pw[i]=pw[i]*t.pw[i]%mod;
return res;
}
}bas, ret; ll f[maxn], ans, dp[maxn];
ll power(ll a,ll b=mod-2){
ll s=1;
while(b){
if(b&1) s=s*a%mod;
a=a*a%mod; b>>=1;
} return s;
}
void solvedp(){
for(ll i=1;i<=n;i++)
for(pir j:vec[i])
bas.dat[j.fi]=g[i][j.se]*Pow[i/j.se][j.se-1]%mod;
for(ll i=1;i<=n;i++) bas.pw[i]=i; bas.ti=1;
for(ll i=1;i<=n;i++) ret.dat[id[i][i]]=ret.pw[i]=1;
ll p=k;
while(p){
if(p&1) ret=ret*bas;
bas=bas*bas; p>>=1;
}
for(ll i=1;i<=n;i++) f[i]=(f[i]+ret.dat[id[i][1]])%mod;
}
ll calc(ll c,ll sz){
dp[0]=1;
for(ll i=1;i<=c;i++){ dp[i]=0;
for(ll j=1;j<=i;j++)
dp[i]=(dp[i]+dp[i-j]*C[i-1][j-1]%mod*f[j]%mod*power(sz,j+k-1))%mod;
} return dp[c];
}
int main(){
scanf("%*lld%lld%lld%lld",&n,&m,&k);
for(ll i=1;i<=n;i++){
Pow[i][0]=1;
for(ll j=1;j<=n;j++)
Pow[i][j]=Pow[i][j-1]*i%mod;
}
for(ll i=1;i<=n;i++)
for(ll j=i;j<=n;j+=i)
vec[j].pb(mkp(++tot,i)), id[j][i]=tot;
C[0][0]=1;
for(ll i=1;i<=n;i++){
C[i][0]=1;
for(ll j=1;j<=i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
fac[0]=1;
for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
g[0][0]=1;
for(ll j=1;j<=n;j++)
for(ll i=1;i*j<=n;i++){
g[i*j][j]=g[i*(j-1)][j-1]*C[i*j-1][i-1]%mod*fac[i-1]%mod;
}
for(ll i=1;i<=n*m;i++){
ll u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
to[u][w]=v;
}
for(ll i=1;i<=n;i++)
if(!dfn[i]){
val=siz=tim=0; dfs(i);
++mp[mkp(val,siz)];
}
solvedp(); ans=1;
for(map<pair<ull,ll>,ll>::iterator it=mp.begin();
it!=mp.end();it++){
ll c=it->se, sz=it->fi.se;
ans=ans*calc(c,sz)%mod;
} printf("%lld",ans);
return 0;
}
D2T1 迷宫守卫
我们首先先决策根，一种思路是让第一个数尽量大。
设 \(s[u,i]\) 表示 \(u\) 子树内使得第一个数成为 \(i\) 的最小代价。注意到 \(s[u,i]\) 不一定是单调的，可以后缀 min 一下满足单调性，然后二分，容易知道我们二分一定是二分到一个代价不是后缀 min 过来的位置。
设二分到的第一个数为 \(x\)，我们考虑在使得 \(x\) 成为第一个数的最小代价操作方案中，根是否被操作。
先考虑根没有操作，判断 \(x\) 在左边还是右边，我们肯定是保证 \(x\) 的那一边字典序尽量小，再保证另一边，因为另一边的第一个数比 \(x\) 大，Bob 会优先走向 \(x\) 所在子树。
如果是左边则递归左边 solve 一下，并得到剩余的 \(k'\)，然后传递下去递归右边。 \(x\) 在右边同理。
考虑方案中操作根的情况，此时 \(x\) 在左边，且操作根的代价必然小于使得右边第一个数大于 \(x\) 的代价。设操作根的代价为 \(c\)，不妨先递归左边，传递的剩余钱数为 \(k-c\)，得到左边剩下的钱数 \(w\)。判断一下 \(w+c\) 是否可以让右边第一个数大于 \(x\)，如果可以那么操作根是不必要的，直接用 \(w+c\) 递归右边；否则，用 \(w\) 递归。
最后是求 \(s[u,i]\)，可以考虑归并排序，类似于归并排序双指针扫就行。
时间复杂度 \(O(n2^n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define mkp make_pair
#define fi first
#define se second
#define pir pair<ll,ll>
using namespace std;
const ll maxn=4e5+10, inf=1e17;
ll t,n,m,a[maxn],c[maxn],siz[maxn],b[maxn],cg[maxn],sr[maxn];
vector<ll>s[maxn],val[maxn],tg[maxn];
ll Find(ll u,ll x){
return upper_bound(val[u].begin(),val[u].end(),x)-val[u].begin();
}
ll print(ll u,ll k,ll l,ll r){
if(u>=(1<<n)){
printf("%lld ",a[u-(1<<n)]); return k;
}
ll pos=upper_bound(s[u].begin(),s[u].end(),k)-s[u].begin()-1;
ll mid=l+r>>1;
ll x=Find(u<<1,val[u][pos]-1), y=Find(u<<1|1,val[u][pos]-1);
if(tg[u][pos]){
ll w=print(u<<1,k-c[u],l,mid);
if(y<=siz[u<<1|1]&&s[u<<1|1][y]<=w+c[u]) w+=c[u];
return print(u<<1|1,w,mid+1,r);
} else if(b[val[u][pos]]<=mid){
ll w, t=s[u<<1|1][Find(u<<1|1,val[u][pos])];
w=print(u<<1,k-t,l,mid)+t;
return print(u<<1|1,w,mid+1,r);
} else{
ll w, t=s[u<<1][Find(u<<1,val[u][pos])];
w=print(u<<1|1,k-t,mid+1,r)+t;
return print(u<<1,w,l,mid);
}
}
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&m);
for(ll i=1;i<(1<<n);i++) scanf("%lld",c+i);
for(ll i=0;i<(1<<n);i++) scanf("%lld",a+i), siz[i+(1<<n)]=1, b[a[i]]=i;
for(ll i=(1<<n+1)-1;i;i--){
if(i<(1<<n)) siz[i]=siz[i<<1]+siz[i<<1|1];
val[i].clear(), s[i].clear(), tg[i].clear();
val[i].resize(siz[i]+1), s[i].resize(siz[i]+1), tg[i].resize(siz[i]+1);
if(i>=(1<<n)) val[i][1]=a[i-(1<<n)], s[i][1]=0;
cg[i]=0;
}
for(ll i=(1<<n);i<(1<<n+1);i++){
ll u=i;
while(u>1){
u>>=1; val[u][++cg[u]]=a[i-(1<<n)];
}
}
for(ll u=(1<<n)-1;u;u--){
sort(val[u].begin(),val[u].end());
for(ll i=1;i<=siz[u];i++) s[u][i]=inf;
for(ll i=1,j=1;i<=siz[u<<1];i++){
while(j<=siz[u<<1]&&val[u<<1|1][j]<val[u<<1][i]){
s[u][i+j-1]=min(s[u][i+j-1],s[u<<1][i]+s[u<<1|1][j]);
++j;
}
if(j<=siz[u<<1|1]){
s[u][i+j-1]=min(s[u][i+j-1],s[u<<1][i]+s[u<<1|1][j]);
}
if(s[u<<1][i]+c[u]<s[u][i+j-1]){
s[u][i+j-1]=s[u<<1][i]+c[u], tg[u][i+j-1]=1;}
}
for(ll i=siz[u]-1;i;i--) s[u][i]=min(s[u][i],s[u][i+1]);
}
print(1,m,0,(1<<n)-1);
if(t) puts("");
}
return 0;
}
D2T2 重塑时光
考虑转方案数，并且先去掉空段。
此时相当于求把一张 DAG 分成若干个连通块的方案数。
设 \(f[S,i]\) 表示点集 \(S\)，分成 \(i\) 个连通块的答案。
考虑枚举入度为 \(0\) 的连通块，设为 \(T\)，有 \(f[S,i]\gets \sum\limits_T f[S-T,i-1]\)。
类似于 DAG 计数，入度为 \(0\) 的连通块可能不止一个，考虑枚举两个、三个……，进行容斥。
枚举这些连通块的并集 \(T\)，枚举连通块个数 \(j\)，设 \(g[S,i]\) 表示把点集 \(S\) 分成没有连边关系的 \(i\) 个连通块的方案数，那么
\[f[S,i]=\sum_T \sum_{i=1}^{j} (-1)^{i-1}g[T,j]f[S-T,i-j] \]这玩意可以插值，但卡卡常就能过。卡常时间复杂度 \(O(3^nn^2)\)，插值时间复杂度 \(O(3^nn)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define mkp make_pair
#define fi first
#define se second
#define pir pair<ll,ll>
#define pb push_back
using namespace std;
const ll maxn=31, mod=1e9+7;
ll n,m,k,u,v,to[16],w[1<<15],fac[maxn],inv[maxn],invp[maxn];
ll f[1<<15][17],g[1<<15],dp[1<<15][17];
int main(){
// freopen("timeline7.in","r",stdin);
scanf("%lld%lld%lld",&n,&m,&k);
for(ll i=1;i<=m;i++){
scanf("%lld%lld",&u,&v);
to[u]|=(1<<v-1);
}
fac[0]=fac[1]=invp[0]=inv[1]=1;
for(ll i=2;i<=n+k;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod, fac[i]=fac[i-1]*i%mod;
for(ll i=1;i<=n+k;i++) invp[i]=invp[i-1]*inv[i]%mod;
g[0]=1;
f[0][0]=dp[0][0]=1;
for(ll S=0;S<(1<<n);S++){
for(ll i=1;i<=n;i++)
if(S&(1<<i-1)) w[S]|=to[i];
for(ll i=1;i<=n;i++)
if((S&(1<<i-1))&&!(to[i]&(S^(1<<i-1))))
g[S]=(g[S]+g[S^(1<<i-1)])%mod;
ll r=__builtin_popcount(S);
for(ll i=1;i<=r;i++){
for(ll T=S;T;T=(T-1)&S)
if(!(w[T]&(S^T))&&!(w[S^T]&T)) dp[S][i]=(dp[S][i]+dp[S^T][i-1]*g[T]%mod*inv[i])%mod;
for(ll T=S;T;T=(T-1)&S)
if(!(w[T]&(S^T))){
ll c=__builtin_popcount(T); c=min(c,i);
for(ll j=1;j<=c;j++)
f[S][i]=(f[S][i]+f[S^T][i-j]*(j&1? dp[T][j]:mod-dp[T][j]))%mod;
}
}
}
ll ans=0;
for(ll i=1;i<=k+1;i++) ans=(ans+f[(1<<n)-1][i]*fac[k+1]%mod*invp[k+1-i])%mod;
ans=ans*invp[n+k]%mod*fac[k]%mod;
printf("%lld",ans);
return 0;
}