专栏文章

VPNOI2025

NNewMarchqwq
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miovoufy
此快照首次捕获于
2025/12/03 01:55
3 个月前
此快照最后确认于
2025/12/03 01:55
3 个月前
查看原文
含剧透。
没有大样例的 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 会了显然的 mmlog⁡mm\sqrt m\log m，有 90 分先不写，看 t2。
t2 开头看错题了，看成了 i−j=1i-j=1。很快会了个 nlog⁡nn\log n 的 dp，然后发现 n≤5000n\le 5000，很疑惑。
想了会 t3，不会任何 poly 复杂度。
然后发现看错 t2 题了。发现修补一下就可以了。细节很多，写了两个小时大概到了 12:00。感觉很容易挂。
然后终于发现 t1 自己唐了。过了 t1。
最后 1h，想 t3。发现一点不会 8 分跑路。
题解
T1 考虑把 (u,p)(u,p) 作为一个状态，这样的状态只有 mm 个。然后把他与其上一个 p，下一个 p 和对应的出边更新。没了。复杂度 mlog⁡mm\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 性质的所有和其他的 n4nn4^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 即高位前后缀和差积操作容易错）！
做之前可以先写一个 8n8^n 的 dp 来当暴力等着对答案。
发现 f(P)=f(Q)f(P)=f(Q) 这个事情开头我们一点都不会用，先放着，钦定 f(P)=S,f(Q)=Tf(P)=S,f(Q)=T。好的我们假设这个的答案（即 ∑f(P)=S,f(Q)=Tw(P∪Q)\sum_{f(P)=S,f(Q)=T}w(P\cup Q)）是 F(S,T)F(S,T)。那么我们考虑速算 F(S,T)F(S,T)。
考虑容斥，求 S⊂f(P),T⊂f(Q)S\subset f(P),T\subset f(Q) 的答案 F′(S,T)F'(S,T)。那么一点简单组合技巧告诉我们：
F′(S,T)=(∏U⊃S,U⊅T(aU+1))(∏U⊅S,U⊃T(aU+1))(∏U⊃S,U⊃T(2aU+1))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∪T)Y(S)Y(T)F'(S,T)=X(S\cup T)Y(S)Y(T) 的样子。你这里需要 B 性质才能保证他是对的，因为其中你可能会乘再除以 (ax+1)(a_x+1)。
然后考虑计算 F(S,T)F(S,T)。你 9n9^n 的容斥是简单的，但是唐的没边了。发现从 F′(S,T)F'(S,T) 算出 S⊂f(P),T=f(Q)S\subset f(P),T=f(Q) 的答案是简单的，一次高位后缀差就行了。然后再从这个中转算出 F(S,T)F(S,T) 也是简单的。这样你就做到了 n4nn4^n。但是这个其实跟正解没啥关系。
题外话：你注意到上面 n4nn4^n 的做法可以记录 00 的个数就完成了 ax+1=0a_x+1=0 的情况。下面 B 性质拼上他有 68，也是我赛时得分。
考虑更帅的容斥。进行简单的推导发现从 F(S′⊃S,T′⊃T)F(S'\supset S,T'\supset T) 推到 F(S,T)F(S,T) 的容斥系数是 (−1)∣S′∣−∣S∣+∣T′∣−∣T∣(-1)^{|S'|-|S|+|T'|-|T|}。然后我们就有了一个很好的式子！
f(S,T)=∑S⊂U,T⊂V(−1)∣U∣+∣V∣−∣S∣−∣T∣X(U∣V)Y(U)Y(V)f(S,T)=\sum_{S\subset U,T\subset V}(-1)^{|U|+|V|-|S|-|T|}X(U|V)Y(U)Y(V)
欸现在可以回到原题面了。原题只要求求 ∑f(S,S)\sum f(S,S)！那么我们发现，可以合并各个 f(S,S)f(S,S)，如下！
ans=∑f(S,S)=∑S∑S⊂U,S⊂V(−1)∣U∣+∣V∣−∣S∣−∣S∣X(U∣V)Y(U)Y(V)=∑U⊃S,V⊃S(−1)∣U∣+∣V∣X(U∣V)Y(U)Y(V)∑S1=∑U,V2∣U∩V∣(−1)∣U∣+∣V∣X(U∣V)Y(U)Y(V)=∑U,V2∣U∣+∣V∣−∣U∪V∣(−1)∣U∣+∣V∣X(U∣V)Y(U)Y(V)=∑U,V2−∣U∪V∣X(U∣V)(−2)∣U∣Y(U)(−2)∣V∣Y(V)=∑T2−∣T∣X(T)∑U∣V=T((−2)∣U∣Y(U))((−2)∣V∣Y(V))\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}
现在我们把式子化成了可以或卷积的事情！于是你两次高维前缀和一次高维前缀差，就得到了后面的卷积。枚举 TT 就得到了答案。这样我们结束了 B 性质。
没有 B 性质的时候，可以扩域，存储 (x,c)=x×0c(x,c)=x\times 0^c。注意到你累后缀积的时候一定有除以零的少于乘零的次数，所以在两个次数不等的时候也可以直接相加：(x,c)+(y,d)=(x,c)   (c<d)(x,c)+(y,d)=(x,c)\ \ \ (c<d)。然后就做完了。
代码 2400B。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...