平面图    2017-02-18 20:21:01    157    0    0

题意:

一个n×m的网格图,边带权.
q次询问,每次询问任意两点间的最短路.

数据范围: n×m2×104,Q105,w104.

做法:

每次暴力求最短路肯定会T.

接下来考虑怎么尽量减少重复计算的东西,也就是将尽量多的询问使用相同的信息.

对于一个网格图,选出一列点,那么这列点左侧的点到右侧一定会经过这列点中的一点.这样对于一次询问,如果能够求出起点到终点到它们中间一列点的最短路,就可以枚举这列上的点求出询问的最短路了.

大概长这样:

那么现在我们进行平面图分治.

每次分治找出行列较大的分治(这样枚举的就是较小的一侧),暴力枚举中线上的点在当前分治区域中跑最短路,然后用每个点暴力更新当前分治处理的询问.

当前询问中端点被中线分割,则不向下递归处理,否则丢进询问所在的一侧继续递归.

其实平面图分治还是比较暴力的,只是要注意细节和常数.

比如枚举中线上的点,要更新当前所有询问,不能只更新被中线隔断的询问.
因为每次枚举中点跑最短路局限于当前分治区域,有可能一组询问被当前区域的中线隔断,但是最短路经过的其他区域的中线.

最后是复杂度的计算.

设总点数为N,因为每次枚举的都是较小的一侧,那么每次分治跑最短路的点不会超过

第二类斯特林数 FFT    2017-02-15 15:31:21    82    0    0

题意:

求:

i=0nj=0iS(i,j)×2j×j!

其中S(i,j)为斯特林数.
这里规定递推式为:S(i,j)=j×S(i1,j)+S(i1,j1) , (1ji1)
边界条件:S(i,i)=1 (0i) , S(i,0)=0 (1i).

998244353取模.

数据范围:

生成函数 FFT    2017-02-15 15:31:19    88    0    0

题意:

c 种颜色的巧克力, 每种颜色有无限个. 现在每次取出一个巧克力, 其颜色等概率为 [1,c] 中的一种.
问最终有 m 种颜色的巧克力个数为奇数的概率.
998244353 取模.

数据范围: n109,mc105

做法:

首先将问题转化为一个计数问题:
一个长度为 n 的数列, 每个位置是 [1,c] 中任意一个数, 求有多少种方案使得出现次数为奇数的值为 m 个.

排列问题, 考虑指数生成函数.

出现次数为奇数的颜色的生成函数:

f(x)=x+x33!+x55!+...=exex2
生成函数 FFT    2017-02-13 21:51:31    107    0    0

题意:

给出一个 N×N 的矩形, 每次可以这么等分:

(显然 N 必须为奇数才可以继续分下去)
Q 次询问, 每次给定 N,K, 问将 N×NK 次操作最终有多少种情况. (不考虑操作顺序不同)
7340033 取模.

数据范围: N109,K1000,Q105

做法:

首先考虑暴力 DP.
N 为奇数并且 >1 时, 显然有

生成函数 多项式求逆 多项式开方 FFT    2017-02-13 21:51:31    112    0    0

题意:

给你 n 个不同权值 c1,c2,...,cn .
现在你可以给若干个点赋权值xc.
同时定义一棵带权二叉树的权值为每个点的权值和.
对于每一个 s[1,m], 请你求出权值为 s 的二叉树的个数. 注意二叉树的左右子树视作是不同的.

998244353 取模.

数据范围: n,m,c105

做法:

首先考虑 DP.
dp(i)表示权值和为i的二叉树的数量.
转移:

生成函数 多项式求逆 FFT    2017-02-13 21:51:31    107    0    0

题意:

求出有 N 个点的有标号简单连通无向图的个数.

1004535809 取模.

数据范围: N1.3×105

做法:

f(n) 表示 n 个点时的答案, g(n) 表示不要求一定连通时的方案, 显然:g(n)=2(n2) .

因为这是游标好的, 枚举 1 号点所在的连通分量的大小, 考虑与1在同一连通块的点集,则有:

g(n)=i=1nf(i)g(ni)(
杜教筛    2017-02-13 14:25:35    143    0    0

题意:

求:

S(n)=i=1nσ0(i2)

数据范围:T104,n1012.

做法:

该问题为一类积性函数的前缀和,考虑使用杜教筛.

f(x)x 不同质因子的个数, 显然有:

σ0(i2)=d|i2f(d)

考虑n的约数d,可以在d2中去掉d的一个质因数集合,也就是2f(d)种集合,可以枚举出所有

积性函数 杜教筛    2017-02-12 20:57:57    43    0    0

题意:

求:

i=1nj=1mlcm(i,j)

数据范围: n,m107

做法:

对式子进行转化(枚举gcd):

i=1nj=1mijgcd(i,j)

g=1ni=1ngj=1mg(ig)(jg)g[gcd(i,j)==1]

积性函数 树状数组    2017-02-12 20:57:55    58    0    0

题意:

有一张n×m的数表,其第i行第j列的数值为能同时整除i和j的所有自然数之和.给定a,计算数表中不大于a的数之和.

数据范围: n,m105,T104

做法:

先不考虑限制,有如下做法:

实际上每个格子的值为σ1(gcd(i,j)),其中σ1为约数和函数.

我们要求:

i=1nj=1mσ1(gcd(i,j))

考虑每种

积性函数    2017-02-12 20:57:49    39    0    0

题意:

同BZOJ2818,加强版,多组数据.

数据范围:T104,n,m107.

做法:

同BZOJ2818的μ函数做法.
求出式子:

i=1nnimip|iμ(ip)

先预处理线性筛出F(i)=p|iμ(ip),并求出前缀和.
对每次询问分块.
复杂度:O(n+Tn)

这是代码:

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int maxn=10000001;
  6. int prime[maxn],cnt;
  7. int mu[maxn];
  8. int f[maxn];
  9. long long sum[maxn
1/11