P7116 [NOIP2020] 微信步数 - 洛谷 - 计算机科学教育新生态 ↗
给定 k 维场地,场地中的坐标表示为 (a1,a2,⋯,ak),场地有大小限制 w,1≤ai≤wi.
给定 n 个指令构成的指令序列,每个指令用 (ci,di) 表示,代表在第 ci 维上移动 di∈{−1,1}。形式化地,若当前位于 (a1,a2,⋯,aci,⋯,ak),下一步会到 (a1,a2,⋯,aci+di,⋯,ak).
现在,小 C 要从场地中的所有 P=∏i=1kwi 个点分别出发,不断重复这个路线,直到其走出场地范围。也就是说,走完 n 步之后,如果小 C 还在场地内,他将回到第 1 步,从头再走一遍。
每执行一次指令代表走一步,求从这 P 个点出发一共走了多少步,对 109+7 取模。
若有一天永远走不出场地,输出 −1.
测试点编号 | n≤ | k≤ | wi≤ |
---|
1∼3 | 5 | 5 | 3 |
4∼6 | 100 | 3 | 10 |
7∼8 | 105 | 1 | 105 |
9∼12 | 105 | 2 | 106 |
13∼16 | 5×105 | 10 | 106 |
17∼20 | 5×105 | 3 | 109 |
如果分别计算每个点的话,那复杂度一定会有一个 ∏i=1kwi,所以把每一维分开考虑。
不妨设我们在考虑第 i 维的情况。对于维度 i 的某个位置 p∈[1,wi],设 timei(p) 表示在仅考虑维度 i 时小 C 走出场地需要的最少步数。如果无论如何都无法走出场地那么 timei(p)=+∞ 。
注意这里是仅考虑维度 i 时,不考虑先从其他维度走出场地的情况。
求出 time 这个函数之后,小 C 从 (a1,a2,…,ak) 走出场地需要的步数就是 mini=1ktimei(ai).
因此,题目最终的答案表示为:
Ans=(a1,a2⋯,ak)∈Map∑i=1minktimei(ai)
这样求解的复杂度仍是 ∏i=1kwi 的,不能接受。对上面的式子改变枚举顺序,可以得到:
Ans=(a1,a2⋯,ak)∈Map∑i=1minktimei(ai)=i≥1∑j=1∏k(t=1∑wj[timej(t)≥i])
t=1∑wj[timej(t)≥i] 代表,在仅考虑第 j 维的情况下,第 j 维中走完 i 步还在地图内的坐标个数。
j=1∏k(t=1∑wj[timej(t)≥i]) 代表,走完 i 步仍然在场地内的点的个数。根据乘法原理,把每个维度上可行的坐标乘起来,所得到的就是可行点的个数。
最外层枚举 i 表示:走完 i 步仍然在场地内。
显然,枚举 i,把所有可行点数加起来,得到的就是总步数。
容易发现,对这个式子求和的复杂度不再需要 ∏i=1kwi 了,下面是一种可行的计算方法。
计算方法#
假设我们现在已经求出了所有的 timei(j).
首先,我们把所有的 timei(j) 拿出来,降序排序,同时存储 timei(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) 的个数。
当我们枚举到 T[i]=T[i−1] 时,此时所有 ≥T[i] 的 timei(j) 已经全部加入到了桶中。
把桶上的数累乘,∏j=1ksumj=∏j=1k(∑t=1wj[timej(t)≥Ti]),就是上面表达式中 i=Ti 时的值,这很显然。
对应到上面 Ans 的表达式,i∈[Ti−1+1,Ti] 这个范围中的 ∏j=1k(∑t=1wj[timej(t)≥i]) 都是相同的。
所以 Ans+=(Ti−Ti−1)×∏j=1ksumj.
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(k⋅∑wi).
求 timei(j)#
对每个维度分别求。
设 stepi+n 表示在当前枚举的维度上,在一轮内,移动 i 的距离需要的最小步数。由于 i 不一定非负,所以下表要整体加 n.
直接设初始在位置 0,遍历指令序列即可求出 step,也能求出遍历一遍序列后移动的距离 cur.
如果在一个周期内,j 就可以走出场地,那么此时 timei(j) 已经可以求出了。
如果 j 需要多个周期才能出去,我们考虑先求出这个周期数。
不妨设 j 在多个周期后从正方向(>wi)离开场地。
设 j 经过若干个整周期后,位置为 x,则其可以在一个新的周期中走出场地,当且仅当 wi−x+1≤Maxdis.
Maxdis 代表,在周期内,最多可以向正方向移动多少距离,这不一定等于周期结束时的移动距离。
因此,周期数可以表示为:
T=⌈curwi−j+1⌉
求出了周期数,就可以直接求值了:
timei(j)=T×n+step[(wi−j+1)−T×cur+n]
+n 的原因前面提到过了。
对于从负方向 <0 离开场地的情况也类似,只需要求出 Mindis 即可。
Maxdis 和 Mindis 可以在求 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(k⋅∑wi).
参考资料#
fight for dream - 洛谷博客 ↗
Ubuntu Pastebin ↗
求自然数幂的和#
给定 n,k,求出:
1k+2k+⋯+nk=i=1∑nikmod1000000007
n≤109,k≤106.
解决这个问题需要用到一些简单的多项式技巧。
拉格朗日插值#
如果给定一个 k 次多项式上的 k+1 个点值,就可以通过拉格朗日差值求出这个多项式的表达式:
f(x)=i=1∑k+1yij=i∏xi−xjx−xj
对于每个点,我们构造一个 k 次多项式 gi(x),满足:
gi(xt)={0ytt=it=i
显然这样的多项式可以为:
gi(x)=yij=i∏xi−xjx−xj
我们把这 k+1 个 g 加起来,每个点值只会被加上一次,所以得到:
f(x)=i=1∑k+1gi(x)=i=1∑k+1yij=i∏xi−xjx−xj
k 次幂和是 k+1 次多项式#
f0(n)=n.
f1(n)=2n(n+1).
f2(n)=6n(n+1)(2n+1).
f3(n)=4n2(n+1)2.
众所周知,fk(n)=∑i=1nik,是一个 k+1 次多项式,可以用数学归纳法证明 ↗。
回到题目,设 Sk(n) 为题目所求。由上面的性质,Sk(n) 是 k+1 次多项式,需要 k+2 个点值进行构造。
如果直接选取 k+1 个点,利用拉格朗日插值计算,复杂度为 O(k2),无法通过。
考虑选连续的一段点,进行优化。
我们选择 k+2 个自变量,为 [1,k+2] 中的整数。也就是说选择的点集为:{(i,Sk(i))∣i∈N+,i≤k+2}.
将这些点代入拉格朗日插值公式,得到:
Sk(n)=i=1∑k+2Sk(i)j=i∏i−jn−j
简单变换后得到:
Sk(n)=i=1∑k+2Sk(i)j=i∏(i−j)j=i∏(n−j)
之后开始找规律)
对于累乘项的分子,暴力拆开:
j=i∏(n−j)=n(n−1)…(n−(i−1))×(n−(i+1))…(n−(k+2))=(j=1∏i−1(n−j))(j=i+1∏k+2(n−j))
所以我们维护 (n−j) 的前缀积和后缀积,就能直接得到分子的值了。
对于分母,假设 i 已经固定,那么有:
==i=j∏(i−j)1i(i−1)(i−2)…1×(−1)…(k+2−i−1)(k+2−i)1(−1)k+2−ii!(k+2−i)!1
所以我们预处理阶乘,再求逆元,就可以快速得到分母的值。
最后,把变换后的式子代入 Sk(n) 的表达式:
Sk(n)=i=1∑k+2Sk(i)(−1)k+2−ii!(k+2−i)!(j=1∏i−1(n−j))(j=i+1∏k+2(n−j))
时间复杂度是 O(klogk).
#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,阶乘的逆元可以线性预处理,问题就只剩:如何快速预处理
1k,2k,3k,⋯,kk
发现 f(t)=tk 是完全积性函数,于是可以只求所有质数的 k 次幂,然后线性筛。
这样整体复杂度大约是 O(k) 的。
参考资料#
地靈殿 - 洛谷博客 ↗
HenryHuang 的博客 - 洛谷博客 ↗
拉格朗日插值 - OI Wiki ↗