In mathematics you don't understand things, you just get used to them.

动态 书籍 杂项 关于 友链

分类 笔记 下的文章

link。

值域分治优化决策单调性 DP 的 trick。朴素做法 trivial，不赘述。

考虑求取一个区间 $[l,r]$ 的 DP 值。先搞定在 $m=\lfloor\frac{l+r}{2}\rfloor$ 的 DP 最优决策点，由于决策的单调性，$[l,m)$ 和 $(m,r]$ 的最优决策点就在 $[l',m']$ 和 $[m',r']$（$'$ 系列变量代表最优决策点）。

于是值域分治解决。

#include <bits/stdc++.h>
template <class T> inline void chmax(T& a, const T b) { a = a > b ? a : b; }
template <class T> inline void chmin(T& a, const T b) { a = a < b ? a : b; }
inline long long rd() {
  long long x = 0; bool f = 0; char ch = getchar();
  while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + (ch & 15), ch = getchar();
  return f ? -x : x;
}
template <class T>
constexpr T kInf = std::numeric_limits<T>::max();
int n, k, a[100100]; long long dp[100100][30];
namespace sm {
long long Res = 0; int app[100100], L = 1, R;
inline long long res() { return Res; }
inline long long cal(int x) { return 1ll * x * (x - 1) / 2; }
void prog(int l, int r) {
  auto upd = [&](int p, int d) -> void {
    Res -= cal(app[a[p]]);
    app[a[p]] += d;
    Res += cal(app[a[p]]);
  };
  while (L > l) upd(--L, 1);
  while (R < r) upd(++R, 1);
  while (L < l) upd(L++, -1);
  while (R > r) upd(R--, -1);
}
}  // namespace Sweepline Mo
void Rawgrass(int l, int r, int lg, int rg, int K) {
  if (l > r) return;
  int mid = (l + r) >> 1, pos = 0, rrg = std::min(rg, mid - 1);
  dp[mid][K] = kInf<long long>;
  for (int t = lg; t <= rrg; ++t) {
    sm::prog(t + 1, mid);
    if (dp[t][K - 1] != kInf<long long> && dp[mid][K] > dp[t][K - 1] + sm::res())
      dp[mid][K] = dp[t][K - 1] + sm::res(), pos = t;
  }
  Rawgrass(l, mid - 1, lg, pos, K);
  Rawgrass(mid + 1, r, pos, rg, K);
}
signed main() {
  n = rd(), k = rd();
  for (int i = 1; i <= n; ++i) a[i] = rd();
  for (int i = 1; i <= n; ++i) sm::prog(1, i), dp[i][1] = sm::res();
  for (int i = 2; i <= k; ++i) Rawgrass(1, n, 1, n, i);
  printf("%lld\n", dp[n][k]);
  return 0;
}

对 @command_block 没有 implementation 做法的细化。理论来说可以通过，但因为我实现得较劣无法通过。：(

把金币中的空隙看作石子，就是一个阶梯 Nim 的模型（有总共 $n-m$ 个石子，$m+1$ 个石堆，其中最左边有一个独立的石堆）。于是问题转化为满足偶数编号的石堆石子数异或和非零的初始方案数。

取补集后可以给出这样一个 DP：令 $f(k,i,j,v\in\{0,1\})$ 表示考虑第 $k$ 个二进制位，决策好了 $i$ 个石堆，恰好 $j$ 个石子被分配，当前填 $0$ / $1$ 的方案数。

转移，考虑根据 $k$ 来分层，然后每个层独立地转移，最后来合并。具体来说，$f(k,i,j,v)\rightarrow f(k,i+1,j,v)$，并且 $f(k,i,j,v)\rightarrow f(k,i+1,j+2^k,v\oplus[i+1\equiv0\pmod2])$，即考虑填 $0$ 还是 $1$。令第 $k$ 层合并后的结果为 $s(k,i,j,v)$，最后的答案即 $\binom{n}{m}-s(\lfloor\log_2a_i\rfloor,m+1,n-m,0)$。合并的过程是 $s(k,m+1,j,0)=\sum\limits_i f(k,m+1,i,0)\times s(k-1,m+1,j,0)$。

边界即 $f(k,0,0,0)=1,s(0,m+1,j,0)=f(0,m+1,j,0)$。

时间复杂度 $\Theta(nm\log_2n)$。这是一份比较朴素的实现方法，可以帮助理解，并不能通过此题。

然后你会发现可能由于内存访问不连续等原因，朴素的实现并不能通过此题较大的数据。

考虑交换数组顺序，利用分奇偶讨论转移的特殊性来乘一个 $\frac{1}{2}$ 的常数等方法卡常，有效，但不完全有效。

但是确实过不去，希望哪天来个卡常大师给卡进去。（

E

倒流一下，然后把负权边置零后跑 MST 即可。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2e5+5,M=2e5+5;
struct edge
{
    int u,v;
    long long w;
    edge(int U=0,int V=0,int W=0)
    {
        u=U;
        v=V;
        w=W;
    }
}tur[M];
int n,m,fa[N];
bool cmp(edge one,edge ano)
{
    return one.w<ano.w;
}
int find(int u)
{
    if(u^fa[u])    fa[u]=find(fa[u]);
    return fa[u];
}
long long spannin()
{
    long long res=0;
    for(int i=1;i<=m;++i)
    {
        int u=tur[i].u,v=tur[i].v;
        long long w=tur[i].w;
        int x=find(u),y=find(v);
        if(x^y)
        {
            fa[x]=y;
            res+=w;
        }
    }
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    long long sum=0;
    for(int i=1;i<=n;++i)    fa[i]=i;
    for(int i=1,u,v;i<=m;++i)
    {
        scanf("%d%d%lld",&u,&v,&tur[i].w);
    tur[i].w=max(tur[i].w,0LL);
        tur[i]=edge(u,v,tur[i].w);
        sum+=tur[i].w;
    }
    sort(tur+1,tur+1+m,cmp);
    printf("%lld\n",sum-spannin());
    return 0;
}

F

跑出原图的最短路树，非树边删除不需要考虑，树边就重新跑一次最短路（规模 $\Theta(n)$）。

类似的题（原题）有 JOI 2020 Final Olympic Bus。

#include<bits/stdc++.h>
int n,m,hd[500],ecnt,ont[319300],pre[500],ide[500];
struct edge {
  int nxt,to;
}e[319300];
void add_edge( int x,int y ) { e[++ecnt]={hd[x],y},hd[x]=ecnt; }
int dis[500],vis[500];
std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int>>,std::greater<std::pair<int,int>>> pq;
int find( int X ) {
  std::memset( dis+1,0x3f,n<<2 );
  std::memset( vis+1,0,n<<2 );
  for( dis[1]=0,pq.emplace( 0,1 ); pq.size(); ) {
    int x=pq.top().second; pq.pop();
    if( vis[x] ) continue; vis[x]=1;
    for( int i=hd[x]; i; i=e[i].nxt ) {
      if( i==X ) continue;
      int y=e[i].to;
      if( dis[y]>dis[x]+1 ) {
        dis[y]=dis[x]+1;
        pre[y]=x;
        ide[y]=i;
        if( !vis[y] ) pq.emplace( dis[y],y );
      }
    }
  }
  return dis[n]==0x3f3f3f3f?-1:dis[n];
}
signed main() {
  scanf( "%d%d",&n,&m );
  for( int i=1,x,y; i<=m; ++i ) scanf( "%d%d",&x,&y ),add_edge( x,y );
  int ret=find( -1 );
  if( ret==-1 ) {
    for( int i=1; i<=m; ++i ) puts( "-1" );
    return 0;
  }
  for( int now=n; now!=1; ) ont[ide[now]]=1,now=pre[now];
  for( int i=1; i<=m; ++i ) {
    if( ont[i] ) printf( "%d\n",find( i ) );
    else printf( "%d\n",ret );
  }
  return 0;
}

G

其实五分钟能冲出来的……去了板子码长 800B。

跑出每个结点到根的中位数，这个随便拿个数据结构维护下就行了，然后做个树 DP，就考虑深度奇偶性，和 P7443 的那个 SG 函数一个套路。注意是自底向上跑的。

#include<bits/stdc++.h>
struct btree {
  int ch[100100][2],fa[100100],val[100100],cnt[100100],sz[100100],tot,root;
  btree() { ins( std::numeric_limits<int>::max() ),ins( std::numeric_limits<int>::min() ); }
  bool wis( int p ) { return ch[fa[p]][1]==p; }
  void pull( int p ) { sz[p]=sz[ch[p][0]]+sz[ch[p][1]]+cnt[p]; }
  int dot( int v ) { return val[++tot]=v,sz[tot]=cnt[tot]=1,tot; }
  void link( int f,int p,int k ) { ch[f][k]=p,fa[p]=f; }
  void rot( int p ) {
    int f=fa[p],gf=fa[fa[p]],k=wis( p );
    link( gf,p,wis( f ) ),link( f,ch[p][k^1],k ),link( p,f,k^1 );
    pull( f ),pull( p );
  }
  void splay( int p,int t ) {
    for( ; fa[p]!=t; rot( p ) )
      if( fa[fa[p]]!=t ) rot( wis( p )!=wis( fa[p] )?p:fa[p] );
    if( t==0 ) root=p;
  }
  int find( int v ) {
    int p=root;
    if( !p ) return 0;
    while( ch[p][v>val[p]] && v!=val[p] ) p=ch[p][v>val[p]];
    return splay( p,0 ),p;
  }
  void ins( int v ) {
    int p=root,f=0;
    while( p && v!=val[p] ) f=p,p=ch[p][v>val[p]];
    if( p ) cnt[p]++;
    else fa[p=dot(v)]=f,( f && ( ch[f][v>val[f]]=p ) );
    splay( p,0 );
  }
  int boundary( int v,int f ) { // f: 0 - pre, 1 - suf
    int p=find( v );
    if( ( val[p]>v && f ) || ( val[p]<v && !f ) ) return p;
    p=ch[p][f];
    while( ch[p][f^1] ) p=ch[p][f^1];
    return p;
  }
  void del( int v ) {
    int pre=boundary( v,0 ),suf=boundary( v,1 );
    splay( pre,0 ),splay( suf,pre );
    if( cnt[ch[suf][0]]>1 ) cnt[ch[suf][0]]--,pull( suf ),splay( ch[suf][0],0 );
    else ch[suf][0]=0,pull( suf ),splay( suf,0 );
  }
  int id( int i ) {
    int p=root; i++;
    if( sz[p]<i ) return -1;
    while( 233 ) {
      if( sz[ch[p][0]]+cnt[p]<i ) i-=sz[ch[p][0]]+cnt[p],p=ch[p][1];
      else if( sz[ch[p][0]]<i ) return val[p];
      else p=ch[p][0];
    }
    return -1;
  }
}tr;
int n,a[100100],med[100100],dp[100100];
std::vector<int> g[100100];
void dfs( int x,int f,int d ) {
  tr.ins( a[x] );
  if( d&1 ) med[x]=tr.id( ( d+1 )/2 );
  else med[x]=( tr.id( d/2 )+tr.id( d/2+1 ) )/2;
  for( int y:g[x] ) if( y!=f ) dfs( y,x,d+1 );
  tr.del( a[x] );
}
void DP( int x,int f,int d ) {
  int leaf=1,mx=0,mn=1e9;
  for( int y:g[x] ) if( y!=f && ( leaf=0 )^1 )
    DP( y,x,d+1 ),mx=std::max( mx,dp[y] ),mn=std::min( mn,dp[y] );
  if( leaf ) dp[x]=med[x];
  else dp[x]=( d&1 )?mx:mn;
}
signed main() {
  scanf( "%d",&n ); for( int i=1; i<=n; ++i ) scanf( "%d",&a[i] );
  for( int i=1,x,y; i<n; ++i ) scanf( "%d%d",&x,&y ),g[x].emplace_back( y ),g[y].emplace_back( x );
  dfs( 1,0,1 ),DP( 1,0,1 ),printf( "%d\n",dp[1] );
  return 0;
}

H 不会 wqs / 反悔贪心，改天学下再说吧……

是不是有点水了呀……

没想到吧。

其实本文旨在以 object oriented 的方式工程化地描述线段树的抽象结构，大概是在翻译 ACL 的 lazysegtree。

在线段树上的结点中，有两种信息，分别称为 S，F，一个是维护的信息，一个是懒惰标记，又对应两个「空值」e() 和 id()。

线段树依赖于两个儿子的值是 S，依赖于父亲的值是 F，定义一个函数 op(x, y)，其中 $x,y\in\mathbb{S}$ 表示 $x,y$ 合并的结果，这个规则是自定义的，且需要满足结合律和交换律；以及 composition(x, y)，其中 $x,y\in\mathbb{F}$，表示把懒惰标记 $x$ 单向传递到懒惰标记 $y$ 上后的结果，其规则同样是自定义的。如果不理解为什么是单向请参考 Range Affine, Range Sum 问题。

类似于 composition(x, y) 使得可以让一个在 $\mathbb{F}$ 中的元素传递到另一个属于 $\mathbb{F}$ 的元素身上，我们有 mapping(x, y) 表示从 $\mathbb{F}$ 到 $\mathbb{S}$ 的映射，其中 $x\in\mathbb{F}$，$y\in\mathbb{S}$。

其实可以发现所谓的 S 就是一类幺半群（monoid），注意 F 显然不具有此类性质，但是 F 的 composition(x, y) 是有封闭性的。

例题 P3373，示例代码见此处，特征码 acl-k。

闲话，如果你的代码实现真的分这么细码量会激增哦。（

link。

钦定 $i>j$，研究得 $(x^i-1,x^j-1)\rightleftharpoons(x^i-x^j,x^j-1)\rightleftharpoons(x^j(x^{i-j}-1),x^j-1)$，注意到 $(x^j,x^j-1)=1$ 且当 $(a,c)=1$ 时 $(ab,c)=(a,b)(a,c)$，则原式 $\rightleftharpoons(x^{i-j}-1,x^j-1)\rightleftharpoons(x^{i\bmod j}-1,x^j-1)\rightleftharpoons x^{(i,j)}-1$。

于是题目即求 $\left(\sum\limits_{i=1}^n\sum\limits_{j=1}^nx^{(i,j)}\right)-n^2$。注意到 $1\leqslant(i,j)\leqslant n$，容易想到研究每一个 $(i,j)$ 的贡献次数，设其为 $f(x)$，显然有 $f(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^n[(i,j)=x]$，观察得 $f(x)=2\times\left(\sum\limits_{i=1}^{\lfloor\frac{n}{x}\rfloor}\varphi(i)\right)-1$，则答案为 $\sum\limits_{i=1}^nx^i\cdot f(i)$，整除分块 & 等比数列求和优化即可。

#include <bits/stdc++.h>
const int MOD = 1000000007;
template <typename T>
T add(T a, T b) {
  return (a + b) % MOD;
}
template <typename T, typename... Args>
T add(T a, T b, Args... args) {
  return add(add(a, b), args...);
}
template <typename T>
T sub(T a, T b) {
  return (a + MOD - b) % MOD;
}
template <typename T>
T mul(T a, T b) {
  return a * static_cast<long long>(b) % MOD;
}
template <typename T, typename... Args>
T mul(T a, T b, Args... args) {
  return mul(mul(a, b), args...);
}
template <typename T>
void Add(T &a, T b) {
  a = add(a, b);
}
template <typename T, typename... Args>
void Add(T &a, T b, Args... args) {
  Add(a, add(b, args...));
}
template <typename T>
void Sub(T &a, T b) {
  a = sub(a, b);
}
template <typename T>
void Mul(T &a, T b) {
  a = mul(a, b);
}
template <typename T, typename... Args>
void Mul(T &a, T b, Args... args) {
  Mul(a, mul(b, args...));
}
int tag[1000100], tot, p[1000100], n, x, ph[1000100], f[1000100];
void shai(int N) {
  tag[1] = ph[1] = 1;
  for (int i = 2; i <= N; ++i) {
    if (!tag[i]) {
      p[++tot] = i;
      ph[i] = i - 1;
    }
    for (int j = 1; j <= tot && i * p[j] <= N; ++j) {
      tag[i * p[j]] = 1;
      if (i % p[j] == 0) {
        ph[i * p[j]] = ph[i] * p[j];
        break;
      }
      ph[i * p[j]] = ph[i] * ph[p[j]];
    }
  }
  for (int i = 1; i <= N; ++i) Add(ph[i], ph[i - 1]);
  for (int i = 1; i <= N; ++i) f[i] = sub(mul(ph[i], 2), 1);
}
int fp(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, Mul(x, x))
    if (y & 1) Mul(res, x);
  return res;
}
int Inv(int x) { return fp(x, MOD - 2); }
int Sum(int n) { return mul(x, sub(1, fp(x, n)), Inv(sub(1, x))); }
int Sum(int l, int r) { return sub(Sum(r), Sum(l - 1)); }
signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int T;
  shai(1e6);
  for (std::cin >> T; T; --T) {
    std::cin >> x >> n;
    if (x == 1) {
      std::cout << "0\n";
      continue;
    }
    int res = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
      r = n / (n / l);
      Add(res, mul(Sum(l, r), f[n / l]));
    }
    std::cout << sub(res, mul(n, n)) << '\n';
  }
  return 0;
}
  1. 1
  2. ...
  3. 22
  4. 23
  5. 24
  6. 25
  7. 26
  8. 27
  9. 28
  10. ...
  11. 49