根号算法Ⅰ

根号分治

小 Y 的背包计数问题

link
思路
很经典一道背包计数问题。
直接完全背包做肯定是不行的。我们不希望有那么多的物品，考虑根号分治。

1. 对于体积 $\le \sqrt{n}$ 的物品：
   直接使用多重背包计数，设表明考虑只从前 $i$ 个物品中取物品，取出的物品总体积为 $j$ 的方案数，则转移方程为：$$f_{i,j}=\sum _{k=0}^i{f}_{i-1,j-i\times k}$$
   可以使用类似于前缀和优化的方式进行优化转移，还可以滚动优化掉 $i$ 这一维（当然不用滚动数组也不会爆空间）。
2. 对于体积 $>\sqrt{n}$ 的物品：
   发现每类物品最多只能取 $\sqrt{n}$ 个，即可以装入背包的商品数很小。考虑枚举正确的商品序列数。设 $g_{i,j}$ 表示取了 $i$ 个这样的商品，最体积为 $j$ 的方案数。显然不能直接枚举第 $i$ 个商品的体积。但是对于某个体积为 $x$ 的商品 $(x>\sqrt{n})$ ，都可以由体积为 $\sqrt{n}+1$ 的商品不断扩大它的体积后得到（即体积不断 $+1$）。问题就转化成是否要取一个体积为 $\sqrt{n}+1$ 的商品以及是否要将已取的所有商品体积 $+1$ 。转移为：$$g_{i,j}=g_{i-1,j-(\sqrt{n}+1)}+g_{i,j-i}$$

这样复杂度均摊为 $O(n\sqrt{n})$ 。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5,maxbk=320,mod=23333333;
ll f[maxn],g[maxbk][maxn],sum[maxn];
int main(){int n; cin>>n; int bk=sqrt(n);f[0]=1;for(int i=1;i<=bk;i++){for(int j=0;j<=n;j++){sum[j]=f[j];if(j>=i) (sum[j]+=sum[j-i])%=mod;}for(int j=0;j<=n;j++){if(j>=i*(i+1)) f[j]=(sum[j]-sum[j-i*(i+1)]+mod)%mod;else f[j]=sum[j];}}g[0][0]=1;ll ans=f[n];for(int i=1;i<=bk;i++)for(int j=i*(bk+1);j<=n;j++){g[i][j]=(g[i-1][j-(bk+1)]+g[i][j-i])%mod;(ans+=f[n-j]*g[i][j]%mod)%=mod;}cout<<ans;return 0;
}

分块

分块题常见操作

修改：

1. 对序列 $[l,r]$ 内的每个数 $\pm k$ ；
2. etc

查询

1. 求序列 $[l,r]$ 的和；
2. 求序列 $[l,r]$ 内 $\le k$ ，$\ge k$ ，$<k$ ，$>k$ 的数的个数；
3. ect

教主的魔法

link
分块+排序后二分 ，板题。