VPNOI2025

· · 个人记录

含剧透。

没有大样例的 VP。[90,100]+[0,100]+[8,8]+[80,100]+[60,68]+[0,35]。我的评价是 d1t1~d2t1<d2t2<d1t2<d1t3<d2t3，其中两天 t3 的排序不太确定。

还是两天 t2 太慢了。如果都快一个小时，就可能能打到金牌线了……

Day1

2025/7/15 08:30-13:30

起晚了，所以 8:30 开始。

上来看到 t1 会了显然的 m\sqrt m\log m，有 90 分先不写，看 t2。

t2 开头看错题了，看成了 i-j=1。很快会了个 n\log n 的 dp，然后发现 n\le 5000，很疑惑。

想了会 t3，不会任何 poly 复杂度。

然后发现看错 t2 题了。发现修补一下就可以了。细节很多，写了两个小时大概到了 12:00。感觉很容易挂。

然后终于发现 t1 自己唐了。过了 t1。

最后 1h，想 t3。发现一点不会 8 分跑路。

题解

T1 考虑把 (u,p) 作为一个状态，这样的状态只有 m 个。然后把他与其上一个 p，下一个 p 和对应的出边更新。没了。复杂度 m\log m。

T2 发现最后一定是分成若干段，每段 [] 或 ==[] 或 []== 或 ==[]==，其中 = 表示 0 [] 表示操作的但是不一定是 0 的数。对这四种 dp 就行了。0 的情况有点细节。

T3 ？

Day2

2025/7/17 08:30-13:30

起早了但是想好好吃早饭，所以还是 8:30。

感觉 t1 极为神秘，但利用小样例找找规律就会了。9:40 左右过了 t1，觉得可能会有点卡常。

推 t2，一直不会。从送的 8 分，改到了 dp 的 16，然后突然会了一个容斥，28。然后再推了推就获得了 B 性质的所有和其他的 n4^n，最后 68 分。写完的时候已经一点多了，赶紧打 t3 暴力。

t3 在 t1 过了后短暂地想过一会，只会 35，去不掉二分更不会小于平方。过了 t2 写了 35 就结束了。

题解

t1 画一下就发现如果有 110 则找最前面的 110 然后输出 n-i-1，否则如果有 101 输出 1，否则输出 0。

t2 看下面

t3 35 分的贪心是显然的。先二分，然后能用杀换闪一定换（省 cd），如果杀不够了再换回来就行了。

Day 2 t2 题解详细版

为啥要集合幂级数？我连 FWT 都不写（比 FMT 即高位前后缀和差积操作容易错）！

做之前可以先写一个 8^n 的 dp 来当暴力等着对答案。

发现 f(P)=f(Q) 这个事情开头我们一点都不会用，先放着，钦定 f(P)=S,f(Q)=T。好的我们假设这个的答案（即 \sum_{f(P)=S,f(Q)=T}w(P\cup Q)）是 F(S,T)。那么我们考虑速算 F(S,T)。

考虑容斥，求 S\subset f(P),T\subset f(Q) 的答案 F'(S,T)。那么一点简单组合技巧告诉我们：

F'(S,T)=\left(\prod_{U\supset S,U\not\supset T}(a_U+1)\right)\left(\prod_{U\not\supset S,U\supset T}(a_U+1)\right)\left(\prod_{U\supset S,U\supset T}(2a_U+1)\right)

这个很容易用高维后缀积优化式子，最后长 F'(S,T)=X(S\cup T)Y(S)Y(T) 的样子。你这里需要 B 性质才能保证他是对的，因为其中你可能会乘再除以 (a_x+1)。

然后考虑计算 F(S,T)。你 9^n 的容斥是简单的，但是唐的没边了。发现从 F'(S,T) 算出 S\subset f(P),T=f(Q) 的答案是简单的，一次高位后缀差就行了。然后再从这个中转算出 F(S,T) 也是简单的。这样你就做到了 n4^n。但是这个其实跟正解没啥关系。

题外话：你注意到上面 n4^n 的做法可以记录 0 的个数就完成了 a_x+1=0 的情况。下面 B 性质拼上他有 68，也是我赛时得分。

考虑更帅的容斥。进行简单的推导发现从 F(S'\supset S,T'\supset T) 推到 F(S,T) 的容斥系数是 (-1)^{|S'|-|S|+|T'|-|T|}。然后我们就有了一个很好的式子！

f(S,T)=\sum_{S\subset U,T\subset V}(-1)^{|U|+|V|-|S|-|T|}X(U|V)Y(U)Y(V)

欸现在可以回到原题面了。原题只要求求 \sum f(S,S)！那么我们发现，可以合并各个 f(S,S)，如下！

\begin{aligned} ans=\sum f(S,S)&=\sum_S\sum_{S\subset U,S\subset V}(-1)^{|U|+|V|-|S|-|S|}X(U|V)Y(U)Y(V)\\ &=\sum_{U\supset S,V\supset S}(-1)^{|U|+|V|}X(U|V)Y(U)Y(V)\sum_S 1\\ &=\sum_{U,V}2^{|U\cap V|}(-1)^{|U|+|V|}X(U|V)Y(U)Y(V)\\ &=\sum_{U,V}2^{|U|+|V|-|U\cup V|}(-1)^{|U|+|V|}X(U|V)Y(U)Y(V)\\ &=\sum_{U,V}2^{-|U\cup V|}X(U|V)(-2)^{|U|}Y(U)(-2)^{|V|}Y(V)\\ &=\sum_T2^{-|T|}X(T)\sum_{U|V=T}\left((-2)^{|U|}Y(U)\right)\left((-2)^{|V|}Y(V)\right)\\ \end{aligned}

现在我们把式子化成了可以或卷积的事情！于是你两次高维前缀和一次高维前缀差，就得到了后面的卷积。枚举 T 就得到了答案。这样我们结束了 B 性质。

没有 B 性质的时候，可以扩域，存储 (x,c)=x\times 0^c。注意到你累后缀积的时候一定有除以零的少于乘零的次数，所以在两个次数不等的时候也可以直接相加：(x,c)+(y,d)=(x,c)\ \ \ (c<d)。然后就做完了。

代码 2400B。

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
constexpr ll mod=998244353;

ll qpow(ll x, ll y) {
  if (y < 0)
    y += mod - 1 + mod - 1;
  if (x == mod - 1)
    return y & 1 ? mod - 1 : 1;
  ll res = 1;
  for (; y; y >>= 1) {
    if (y & 1) {
      res *= x;
      res %= mod;
    }
    x *= x;
    x %= mod;
  }
  return res;
}

int caseid;

int n;
ll a[1<<20|5];
struct safe_modint{
  ll x;
  int c;
  safe_modint(ll t=0):x(!t?1:t),c(!t){}
  safe_modint(const safe_modint&r):x(r.x),c(r.c){}
  safe_modint(ll x,int c):x(x),c(c){}
  friend safe_modint operator+(safe_modint p,safe_modint q){return p.c^q.c?(p.c<q.c?p:q):(safe_modint){(p.x+q.x)%mod,p.c};}
  friend safe_modint operator-(safe_modint p,safe_modint q){q.x=(mod-q.x)%mod;return p+q;}
  friend safe_modint operator*(safe_modint p,safe_modint q){return (safe_modint){p.x*q.x%mod,p.c+q.c};}
  safe_modint inv(){return (safe_modint){qpow(x,-1),-c};}
  ll val(){assert(c>=0);return c?0:x;}
};
safe_modint sum2[1<<20|5],sum1[1<<20|5],isum1[1<<20|5],X[1<<20|5],Y[1<<20|5],Z[1<<20|5],conv[1<<20|5];

void do_conv(safe_modint*p,safe_modint*r){ // FMT(高位前缀和差) 实现 r=p*p 或卷积
  rep(i,0,n-1)rep(j,0,(1<<n)-1)
    if (j>>i&1)p[j]=p[j]+p[j^1<<i];
  rep(i,0,(1<<n)-1)r[i]=p[i]*p[i];
  rep(i,0,n-1)rep(j,0,(1<<n)-1)
    if (j>>i&1)r[j]=r[j]-r[j^1<<i];
}

void solve(){
  scanf("%d",&n);
  rep(i,0,(1<<n)-1)scanf("%lld",&a[i]);
  rep(i,0,(1<<n)-1)sum1[i]=(a[i]+1)%mod,sum2[i]=(a[i]+a[i]+1)%mod;
  drep(i,n-1,0)drep(j,(1<<n)-1,0)
    if (j>>i&1)sum1[j^(1<<i)]=sum1[j^(1<<i)]*sum1[j],sum2[j^1<<i]=sum2[j^1<<i]*sum2[j];
  rep(i,0,(1<<n)-1)isum1[i]=sum1[i].inv();
  rep(i,0,(1<<n)-1)X[i]=isum1[i]*isum1[i]*sum2[i],Y[i]=sum1[i],Z[i]=Y[i]*qpow(mod-2,__builtin_popcount(i));
  // rep(i,0,(1<<n)-1)cout<<Z[i]<<" \n"[i==(1<<n)-1];
  do_conv(Z,conv);
  // rep(i,0,(1<<n)-1)cout<<conv[i]<<" \n"[i==(1<<n)-1];
  safe_modint res=0;
  // rep(U,0,(1<<n)-1)rep(V,0,(1<<n)-1)res+=qpow(mod-1,__builtin_popcount(U^V))*qpow(2,__builtin_popcount(U&V))%mod*X[U|V]%mod*Y[U]%mod*Y[V]%mod;
  rep(T,0,(1<<n)-1)res=res+X[T]*qpow(2,-__builtin_popcount(T))*conv[T];
  printf("%lld\n",res.val());
}

int main() {
  int tt;
  scanf("%d%d",&caseid,&tt);
  while (tt--)solve();
  return 0;
}