TonyYin's Blog

Back

题意#

P7116 [NOIP2020] 微信步数 - 洛谷 - 计算机科学教育新生态

给定 kk 维场地,场地中的坐标表示为 (a1,a2,,ak)(a_1, a_2, \cdots, a_k),场地有大小限制 ww1aiwi1\leq a_i\leq w_i.

给定 nn 个指令构成的指令序列,每个指令用 (ci,di)(c_i, d_i) 表示,代表在第 cic_i 维上移动 di{1,1}d_i\in\{-1, 1\}。形式化地,若当前位于 (a1,a2,,aci,,ak)(a_1, a_2, \cdots, a_{c_i}, \cdots, a_k),下一步会到 (a1,a2,,aci+di,,ak)(a_1, a_2, \cdots, a_{c_i}+d_i, \cdots, a_k).

现在,小 CC 要从场地中的所有 P=i=1kwiP=\prod_{i=1}^k{w_i} 个点分别出发,不断重复这个路线,直到其走出场地范围。也就是说,走完 nn 步之后,如果小 CC 还在场地内,他将回到第 11 步,从头再走一遍。

每执行一次指令代表走一步,求从这 PP 个点出发一共走了多少步,对 109+710^9+7 取模。

若有一天永远走不出场地,输出 1-1.

测试点编号nn \lekk \lewiw_i \le
131 \sim 3555533
464 \sim 6100100331010
787 \sim 8105{10}^511105{10}^5
9129 \sim 12105{10}^522106{10}^6
131613 \sim 165×1055 \times {10}^51010106{10}^6
172017 \sim 205×1055 \times {10}^533109{10}^9

题解#

分析#

如果分别计算每个点的话,那复杂度一定会有一个 i=1kwi\prod_{i=1}^k{w_i},所以把每一维分开考虑。

不妨设我们在考虑第 ii 维的情况。对于维度 ii 的某个位置 p[1,wi]p\in[1, w_i],设 timei(p)\operatorname{time}_i(p) 表示在仅考虑维度 ii小 C 走出场地需要的最少步数。如果无论如何都无法走出场地那么 timei(p)=+\operatorname{time}_i(p)=+\infty

注意这里是仅考虑维度 ii 时,不考虑先从其他维度走出场地的情况。

求出 time\operatorname{time} 这个函数之后,小 C 从 (a1,a2,,ak)(a_1,a_2,\dots,a_k) 走出场地需要的步数就是 mini=1ktimei(ai)\min_{i=1}^k\operatorname{time}_i(a_i).

因此,题目最终的答案表示为:

Ans=(a1,a2,ak)Mapmini=1ktimei(ai)\operatorname{Ans} = \sum_{(a_1, a_2\cdots, a_k)\in \operatorname{Map}}\min_{i=1}^k\operatorname{time}_{i}(a_i)

转化#

这样求解的复杂度仍是 i=1kwi\prod_{i=1}^k{w_i} 的,不能接受。对上面的式子改变枚举顺序,可以得到:

Ans=(a1,a2,ak)Mapmini=1ktimei(ai)=i1j=1k(t=1wj[timej(t)i])\operatorname{Ans} = \sum_{(a_1, a_2\cdots, a_k)\in \operatorname{Map}}\min_{i=1}^k\operatorname{time}_{i}(a_i)=\sum_{i\ge 1}\prod_{j=1}^k(\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i])

t=1wj[timej(t)i]\sum\limits_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i] 代表,在仅考虑第 jj 维的情况下,jj 维中走完 ii 步还在地图内的坐标个数

j=1k(t=1wj[timej(t)i])\prod\limits_{j=1}^k(\sum\limits_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i]) 代表,走完 ii 步仍然在场地内的点的个数。根据乘法原理,把每个维度上可行的坐标乘起来,所得到的就是可行点的个数。

最外层枚举 ii 表示:走完 ii 步仍然在场地内

显然,枚举 ii,把所有可行点数加起来,得到的就是总步数。

容易发现,对这个式子求和的复杂度不再需要 i=1kwi\prod_{i=1}^k{w_i} 了,下面是一种可行的计算方法。

计算方法#

假设我们现在已经求出了所有的 timei(j)\operatorname{time}_i(j).

首先,我们把所有的 timei(j)\operatorname{time}_i(j) 拿出来,降序排序,同时存储 timei(j)\operatorname{time}_i(j) 所处的维度。

for(int i = 1; i <= k; i++) 
    for(int j = 1; j <= w[i]; j++) 
        T[++cnt] = make_pair(Time[i][j], i);
sort(T + 1, T + cnt + 1);
cpp

之后,我们按降序遍历 T[],对每维开一个桶,记录当前属于该维度的 timei(j)\operatorname{time}_i(j) 的个数。

当我们枚举到 T[i]T[i1]T[i]\neq T[i-1] 时,此时所有 T[i]\geq T[i]timei(j)\operatorname{time}_i(j) 已经全部加入到了桶中。

把桶上的数累乘,j=1ksumj=j=1k(t=1wj[timej(t)Ti])\prod_{j=1}^k{\operatorname{sum}_j}=\prod_{j=1}^k(\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge T_i]),就是上面表达式中 i=Tii=T_i 时的值,这很显然。

对应到上面 Ans\operatorname{Ans} 的表达式,i[Ti1+1,Ti]i\in[T_{i-1} + 1, T_i] 这个范围中的 j=1k(t=1wj[timej(t)i])\prod_{j=1}^k(\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i]) 都是相同的。

所以 Ans+=(TiTi1)×j=1ksumj\operatorname{Ans} += (T_i - T_{i-1})\times \prod_{j=1}^k{\operatorname{sum}_j}.

pair<int, int> T[10000010]; //first存Time,second存维度
int sum[MAXK]; //sum[i]代表:维度i下,可选的点的个数
int cnt = 0, ans = 0;
for(int i = cnt; i >= 1; i--) {
	sum[T[i].second]++;
	if(T[i - 1].first != T[i].first) { // >=T[i]的部分已经加入完成
		ll tmp = 1;
		for(int j = 1; j <= k; j++) tmp *= sum[j];
		ans += (T[i].first - T[i - 1].first) * tmp;
	}
}
cpp

代码没加取模,时间复杂度 O(kwi)\mathcal{O}(k\cdot \sum w_i).

timei(j)\operatorname{time}_i(j)#

对每个维度分别求。

stepi+n\operatorname{step}_{i+n} 表示在当前枚举的维度上,在一轮内,移动 ii 的距离需要的最小步数。由于 ii 不一定非负,所以下表要整体加 nn.

直接设初始在位置 00,遍历指令序列即可求出 step\operatorname{step},也能求出遍历一遍序列后移动的距离 cur\operatorname{cur}.

如果在一个周期内jj 就可以走出场地,那么此时 timei(j)\operatorname{time}_i(j) 已经可以求出了。

如果 jj 需要多个周期才能出去,我们考虑先求出这个周期数

不妨设 jj 在多个周期后从正方向(>wi>w_i)离开场地。

jj 经过若干个整周期后,位置为 xx,则其可以在一个新的周期中走出场地,当且仅当 wix+1Maxdisw_i-x+1\leq \operatorname{Maxdis}.

Maxdis\operatorname{Maxdis} 代表,在周期内,最多可以向正方向移动多少距离,这不一定等于周期结束时的移动距离

因此,周期数可以表示为:

T=wij+1cur\operatorname{T}= \left\lceil \frac{w_i-j+1}{\operatorname{cur}} \right\rceil

求出了周期数,就可以直接求值了:

timei(j)=T×n+step[(wij+1)T×cur+n]\operatorname{time}_i(j)=\operatorname{T}\times n+\operatorname{step}[(w_i-j+1)-\operatorname{T}\times \operatorname{cur}+n]

+n+n 的原因前面提到过了。

对于从负方向 <0<0 离开场地的情况也类似,只需要求出 Mindis\operatorname{Mindis} 即可。

Maxdis\operatorname{Maxdis}Mindis\operatorname{Mindis} 可以在求 step\operatorname{step} 的时候顺便处理出来。

int step[MAXN << 1];
int Time[MAXK][MAXWI];
for(int i = 1; i <= k; i++) {//第i维
    memset(step, 0x3f, sizeof(step)); step[n] = 0;
    int cur = 0, maxdis = 0, mindis = 0;
    for(int j = 1; j <= n; j++) if(c[j] == i) {
        cur += d[j];
        if(cur > maxdis) maxdis = cur;
        if(cur < mindis) mindis = cur;
        step[cur + n] = min(step[cur + n], j);
    }
    //cur: 走n步,一个周期能移动cur
    for(int j = 1; j <= w[i]; j++) {
        //一个周期就能走到的情况
        if(w[i] - j + 1 + n >= 0 && w[i] - j + 1 <= n) 
            Time[i][j] = min(Time[i][j], step[w[i] - j + 1 + n]);
        if(n - j >= 0) Time[i][j] = min(Time[i][j], step[-j + n]);
        int rest = 0, tim = 0, T;
        //多个周期才能走到的情况
        if(cur > 0) { //向正方向
            rest = w[i] - j + 1;
            T = max(0ll, (rest - maxdis - 1) / cur + 1); //上取整
            tim = T * n + step[rest - T * cur + n];
            Time[i][j] = min(Time[i][j], tim);
        }
        if(cur < 0) { //向负方向
            rest = j;
            T = max(0ll, (rest + mindis - 1) / (-cur) + 1); //上取整
            tim = T * n + step[-rest + T * (-cur) + n];
            Time[i][j] = min(Time[i][j], tim);
        }
    }
}
cpp

这样实现的时间复杂度同样为:O(kwi)\mathcal{O}(k\cdot \sum w_i).

参考资料#

fight for dream - 洛谷博客

代码#

Ubuntu Pastebin

求自然数幂的和#

问题#

给定 n,kn, k,求出:

1k+2k++nk=i=1nikmod10000000071^k+2^k+\cdots+n^k=\sum_{i=1}^{n}{i^k}\bmod 1000000007

n109n\leq 10^9k106k\leq 10^6.

解决这个问题需要用到一些简单的多项式技巧。

拉格朗日插值#

如果给定一个 kk 次多项式上的 k+1k+1 个点值,就可以通过拉格朗日差值求出这个多项式的表达式:

f(x)=i=1k+1yijixxjxixjf(x)=\sum_{i=1}^{k+1}y_i\prod_{j\neq i}{\frac{x-x_j}{x_i-x_j}}

对于每个点,我们构造一个 kk 次多项式 gi(x)g_i(x),满足:

gi(xt)={0t=iyttig_i(x_t)= \left\{ \begin{align} &0 &t=i\\ &y_t &t\neq i \end{align} \right.

显然这样的多项式可以为:

gi(x)=yijixxjxixjg_i(x) = y_i\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}

我们把这 k+1k+1gg 加起来,每个点值只会被加上一次,所以得到:

f(x)=i=1k+1gi(x)=i=1k+1yijixxjxixjf(x)=\sum_{i=1}^{k+1}g_i(x)=\sum_{i=1}^{k+1}y_i\prod_{j\neq i}{\frac{x-x_j}{x_i-x_j}}

kk 次幂和是 k+1k+1 次多项式#

f0(n)=nf_0(n) =n.

f1(n)=n(n+1)2f_1(n) =\dfrac{n(n+1)}{2}.

f2(n)=n(n+1)(2n+1)6f_2(n)=\dfrac{n(n+1)(2n+1)}{6}.

f3(n)=n2(n+1)24f_3(n)=\dfrac{n^2(n+1)^2}{4}.

众所周知,fk(n)=i=1nikf_k(n)=\sum_{i=1}^{n}{i^k},是一个 k+1k+1 次多项式,可以用数学归纳法证明

分析#

回到题目,设 Sk(n)S_k(n) 为题目所求。由上面的性质,Sk(n)S_k(n)k+1k+1 次多项式,需要 k+2k+2 个点值进行构造。

如果直接选取 k+1k+1 个点,利用拉格朗日插值计算,复杂度为 O(k2)\mathcal{O}(k^2),无法通过。

优化#

考虑选连续的一段点,进行优化。

我们选择 k+2k+2 个自变量,为 [1,k+2][1, k+2] 中的整数。也就是说选择的点集为:{(i,Sk(i))iN+,ik+2}\{(i, S_k(i))\mid i\in \Bbb{N}^{+}, i\leq k+2\}.

将这些点代入拉格朗日插值公式,得到:

Sk(n)=i=1k+2Sk(i)jinjijS_k(n)=\sum_{i=1}^{k+2}{S_k(i)\prod_{j\neq i}{\frac{n-j}{i-j}}}

简单变换后得到:

Sk(n)=i=1k+2Sk(i)ji(nj)ji(ij)S_k(n)=\sum_{i=1}^{k+2}{S_k(i){\frac{\prod\limits_{j\neq i}(n-j)}{\prod\limits_{j\neq i}(i-j)}}}

之后开始找规律)

对于累乘项的分子,暴力拆开:

ji(nj)=n(n1)(n(i1))×(n(i+1))(n(k+2))=(j=1i1(nj))(j=i+1k+2(nj))\begin{align} \prod_{j\neq i}(n-j)&= n(n-1)\dots (n-(i-1))\times(n-(i+1))\dots(n-(k+2))\\ &= (\prod_{j=1}^{i-1}(n-j))(\prod_{j=i+1}^{k+2}(n-j)) \end{align}

所以我们维护 (nj)(n-j) 的前缀积和后缀积,就能直接得到分子的值了。

对于分母,假设 ii 已经固定,那么有:

1ij(ij)=1i(i1)(i2)1×(1)(k+2i1)(k+2i)=(1)k+2i1i!(k+2i)!\begin{aligned} &\dfrac{1}{\prod\limits_{i\not ={j}}(i-j)}\\ = &\dfrac{1}{i(i-1)(i-2) \dots 1 \times(-1) \dots (k+2-i-1)(k+2-i)}\\=&(-1)^{k+2-i}\dfrac{1}{i! (k+2-i)!} \end{aligned}

所以我们预处理阶乘,再求逆元,就可以快速得到分母的值。

最后,把变换后的式子代入 Sk(n)S_k(n) 的表达式:

Sk(n)=i=1k+2Sk(i)(1)k+2i(j=1i1(nj))(j=i+1k+2(nj))i!(k+2i)!S_k(n)=\sum_{i=1}^{k+2}S_k(i)(-1)^{k+2-i}\dfrac{(\prod\limits_{j=1}^{i-1}(n-j))(\prod\limits_{j=i+1}^{k+2}(n-j))}{i!(k+2-i)!}

时间复杂度是 O(klogk)\mathcal{O}(k\log k).

代码#

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXK = 1e6 + 10, mod = 1e9 + 7;
int n, k;
int pre[MAXK], suf[MAXK], fac[MAXK];
int power(int x, int k) {
	int ret = 1;
	while(k) {
		if(k & 1) ret = ret * x % mod;
		k >>= 1;
		x = x * x % mod;
	}
	return ret;
}
inline int inv(int x) {
	return power(x, mod - 2);
}
signed main() {
	scanf("%lld%lld", &n, &k);
	fac[0] = pre[0] = 1;
	for(int i = 1; i <= k + 2; i++) {
		pre[i] = pre[i - 1] * (n - i) % mod;
		fac[i] = fac[i - 1] * i % mod;
	}
	suf[k + 3] = 1;
	for(int i = k + 2; i >= 1; i--) suf[i] = suf[i + 1] * (n - i) % mod;
	int tmp = 0, ans = 0;
	for(int i = 1; i <= k + 2; i++) {
		tmp = (tmp + power(i, k)) % mod;
		int a = pre[i - 1] * suf[i + 1] % mod;
		int b = fac[i - 1] * fac[k + 2 - i] % mod;
		if((k - i) % 2 == 0) ans = (ans + tmp * a % mod * inv(b) % mod) % mod;
		else ans = (ans - tmp * a % mod * inv(b) % mod) % mod;
	}
	cout << (ans + mod) % mod << endl;
	return 0;
}
cpp

进一步优化#

上面做法有两个部分的复杂度带 logk\log k,阶乘的逆元可以线性预处理,问题就只剩:如何快速预处理

1k,2k,3k,,kk1^k, 2^k, 3^k, \cdots, k^k

发现 f(t)=tkf(t)=t^k 是完全积性函数,于是可以只求所有质数的 kk 次幂,然后线性筛。

这样整体复杂度大约是 O(k)\mathcal{O}(k) 的。

参考资料#

地靈殿 - 洛谷博客

HenryHuang 的博客 - 洛谷博客

拉格朗日插值 - OI Wiki

【洛谷-P7116】 [NOIP2020] 微信步数
https://www.tonyyin.top/blog/oi-solution/p7116
Author TonyYin
Published at September 14, 2021
Comment seems to stuck. Try to refresh?✨