本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-04 01:44:57

题意

有 $n$ 个用户和 $10^9$ 首歌曲，第 $i$ 个用户喜欢的歌曲是编号在 $[l_i,r_i]$ 的一段连续子区间。

用户 $j$ 称为用户 $i$ 的预测者当且仅当 $[l_j,r_j]$ 包含 $[l_i,r_i]$。

对于每个用户 $i$，计算其预测者喜欢的歌曲的并集大小（原题求出结果后需要减去 $r_i-l_i+1$）。

做法

注意到完全包含的对数可以达到 $O(n^2)$ 级别，逐个计算是不可能的。

考虑对于每个人，如何计算其答案。

考虑简化问题，分别考虑对于一个人，其预测者喜欢的音乐的并集区间的左端点和右端点。

假设当前处理用户 $i$ 的答案。

容易注意到，左端点是在 $i$ 的预测者的左端点里面取最大值，右端点是在 $i$ 的预测者的右端点里面取最小值。

能否二分左右端点呢？

由于左右端点的做法是等价的，此处仅讨论左端点的情况。

此时，二分的目的是求出最大的 $l$ 使得 $l$ 是某个预测者的左端点。

注意到，一个左端点是某个预测者的左端点，当且仅当这个左端点能直接到达的最大右端点大于等于 $r_i$，当然，这对左端点右端点的组合不能是 $(l_i,r_i)$ 本身。

那么，二分 check 的时候只需要看从 mid 到 $l_i$ 是否存在一个预测者的左端点就可以了，可以 ST 表维护做到 $O(1)$ 判定。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-04 02:07:41

注意，本文章中如果提到某个端点没有固定，那么在固定前默认延伸到本区间的末尾

考虑哪些信息需要维护

首先需要维护题目要求的答案 $ans$，而有以下几种情况：

1. 两个答案区间在同一个子区间内，继承子区间答案就可以。
2. 两个答案区间分别在不同子区间内，需要维护 $ans2$ 代表单个答案区间的情况。
3. 其中一个答案区间跨了中点，此时两种情况：
   1. 左答案区间跨中点。
   2. 右答案区间跨中点。

首先考虑 $ans2$，此时需要再维护两个值 $premx,sufmx$，分别代表左端点固定，右端点固定（另一个端点一直到区间结束）的最大值。

随后考虑情况 3，此时的两种形式：

1. ....l1....mid....r1...l2....r2...
2. ....l1....r1....l2....mid...r2...

考虑用 $pre$ 代表左答案区间固定，右答案区间的右端点尚未存在的最大价值，$suf$ 代表右答案区间固定，左答案区间的左端点尚未存在的最大价值。

$pre,suf$ 的计算，经过分析后可知还需要维护一个值，代表存在两个答案区间，左答案区间的右端点固定，右答案区间的左端点固定的最大价值。

坑点

本题我调了很久也没调出来，看了题解发现思路和题解完全一致。

我总算是查出了错，原因在于我在 SGT 的信息里使用了前缀和，但是我忘了 $a$ 数组的修改会改变一整个后缀的前缀和，导致 SGT 的信息出错。

另外

以往我写线段树，通常只是将区间合并写死为树上左右子区间合并，而忽略了特殊情况下，查询的时候没法直接使用简单的加法乘法等操作将查询过程中找到的不同查询区间的子区间的答案合并，此时就需要使用 pushup 操作将它们逐个合并为整个查询的区间。

以后写线段树的时候需要注意这一点，防止类似情况再次被坑。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-05 12:56:35

给定 $a,b$，求解 $ax+by=\gcd(a,b)$ 的解。

考虑使用欧几里得算法的过程（这样 $\gcd(a,b)$ 全程不会变），并把深层的解通过一些推导转化为浅层的解。

若 $b=0$，则解为 $x=1,y=0$。

否则，则递归求解方程 $bx'+(a \bmod b)y' = \gcd(b,a \bmod b)$ 的解 $x',y'$。

注意到 $\gcd(a,b) = \gcd(b,a\bmod b)$，$a \bmod b = a - \lfloor \frac{a}{b} \rfloor b$。

可得出 $bx'+(a - \lfloor \frac{a}{b} \rfloor b)y'=\gcd(a,b)$ 。

$bx'+ay'-\lfloor \frac{a}{b} \rfloor by' = \gcd(a,b)$ 。

$ay' + b(x'-y'\lfloor \frac{a}{b} \rfloor) = \gcd(a,b)$ 。

至此，显然：$x=y',y=x'-y'\lfloor \frac{a}{b}\rfloor$。

思路

构造一个流程，可以在 log 级别内结束。

递归算法，深层的 $a,b$ 可以用浅层的 $a,b$ 轻易表示出来，较为容易的推导解之间的转化关系。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-18 16:03:51

做这题时没理解他是怎么报号的，猜了一种题意通过了，记录一下。

题意

有 $n$ 个人，从左到右编号为 $1,2,3,\cdots,n$，且 $n$ 右边是 $1$。

现在举行 $n$ 轮游戏。

对于第 $i$ 轮，从第 $i-1$ 轮被踢出的人的右边的第一个存活的人开始报数，对于第一轮，则从 $1$ 号开始。

从左到右报数，第一个人报 $1$，之后每个人报上一个人的数字加 $1$。

当有人报出 $k$ 时，本轮结束，这个人被踢出。

现在已知第 $i$ 个人是第 $a_i$ 轮出圈的，求最小的 $k$，或者报告 NIE。

做法

考虑依次模拟每一轮，并在每一轮开始前，将开始报数的人编号设置为 $1$ 并对所有存活的人按照报号顺序重新编号。

假设第 $i$ 轮重新编号后，编号为 $x$ 的人被踢出了，那么说明 $k \equiv x \pmod {(n-i+1)}$ 。

显然，EXCRT 合并就可以解决本题。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-22 15:52:30

给定 $n,m,p$，保证 $p$ 是质数。

证明 $\binom{n}{m} \equiv \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\cdot \binom{n \mod p}{m \mod p} \pmod p$。

过程

1. 前置引理 1。

   若 $p$ 为质数，则 $\binom{p}{i} \mod p$ 在 $i=0$ 或 $i=p$ 的情况下为 $1$，否则为 $0$。

   证明，首先 $i=0,i=p$ 的情况是显然的。

   其他情况，即 $0 \lt i \lt p$，由于 $p$ 是质数，$p$ 本身不可能被 $1,p$ 以外的数整除。

   而 $i,p-i \lt p$，且 $\binom{p}{i}$ 肯定是整数，所以 $\binom{p}{i}$ 最后一定包含 $p$ 作为因数。

   结论成立。

2. 前置引理 2。

   若 $p$ 为质数，则 $(x+1)^p \equiv x^p+1 \pmod p$。

   证明，考虑展开。

   $(x+1)^p = \sum\limits_{i=0}^p\binom{p}{i}x^i$。

   根据引理 1，$\sum\limits_{i=0}^p \binom{p}{i}x^i \equiv \binom{p}{0}x^0+\binom{p}{p}x^p \equiv 1+x^p \pmod p$。

3. 转化

   考虑 $\binom{n}{m}$ 和 $\binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\cdot \binom{n \mod p}{m \mod p}$ 如何对应到同一个式子里面。

   不难注意到 $\binom{n}{m}$ 是 $(x+1)^n$ 的 $m$ 次项的系数，即 $\binom{n}{m}$。

   通过这一点入手。

   设 $n=tp+q,m=sp+r$。

   $(x+1)^n = (x+1)^{tp+q} = ((x+1)^p)^t(x+1)^q$ 。

   由引理 2 可得，$((x+1)^p)^t(x+1)^q \equiv (x^p+1)^t(x+1)^q \pmod p$ 。

   $(x^p+1)^t(x+1)^q = (\sum\limits_{i=0}^t \binom{t}{i}x^{ip})(\sum\limits_{i=0}^q \binom{q}{i}x^i)$。

   由于 $m=sp+r$，所以 $x^m$ 的系数为第一个括号的 $x^{sp}$ 项的系数乘第二个括号的 $x^r$ 项的系数。

   即 $x^m$ 的系数等于 $\binom{t}{s}\binom{q}{r} \bmod p$。

   现在得到了两条信息：$x^m $ 的系数模 $p$ 同余 $\binom{n}{m}$，$x^m$ 的系数模 $p$ 同余 $\binom{t}{s}\binom{q}{r}$。

   lucas 定理得到证明。

思考大概方向

先考虑 $\binom{n}{m}$ 的实际含义，或者说将其对应到某个值。

然后，通过一系列转化，将 $\binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\cdot \binom{n \mod p}{m \mod p}$ 也对应到这个值。

中间比较重要的转化，一个是添加未知量 $t,q,r,s$ ，将 $n,m$ 用含 $p$ 的式子表示出来，并将 $(x+1)^n \bmod p$ 用这几个变量表示，转化。

然后就是利用 $p$ 为质数的性质，将这个式子进行简化，并展开为两个幂次分别为 $t,q$ 的二项式的乘积，随后计算出 $x$ 的 $m$ 次项对应的系数，完成证明 lucas 定理。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-27 12:12:28

题意

给定大小为 $n \times m$ 的矩阵 $A,B$，两个矩阵均由不大于 $10^9$ 的非负整数组成。

单次操作可以有以下两种形式：

1. 选择两个数 $i,x$，满足 $1 \le i \le n,x \ge 0$。

   对于 $1 \le \forall j \le m$，将 $A_{i,j}$ 替换为 $A_{i,j}$ 按位与 $x$，即整行按位与。

2. 选择两个数 $j,x$，满足 $1 \le j \le m,x\ge 0$。

   对于 $1 \le \forall i \le n$，将 $A_{i,j}$ 替换为 $A_{i,j}$ 按位或 $x$，即整列按位或。

问能否在任意次操作之后将 $A$ 变为 $B$。

做法

每一位都是独立的，考虑枚举每一位。

问题简化为了，两个 $n \times m$ 的 01 矩阵 $A,B$，每次可以将 $A$ 的一整行设置为 $0$，或将 $A$ 的一整列设置为 $1$，求能否将 $A$ 变为 $B$。

考虑对于 $(i,j)$，如果 $A_{i,j} \neq B_{i,j}$，该如何处理。

1. $A_{i,j}=1$ 且 $B_{i,j}=0$，此时需要对 $i$ 行执行一次操作。
2. $A_{i,j}=0$ 且 $B_{i,j}=1$，此时需要对 $j$ 列进行一次操作。

不难注意到，每一行，每一列最多执行一次操作。

如果对第 $i$ 行执行了操作，且存在 $j$ 满足 $B_{i,j}=1$，那么必然需要在此之后对 $j$ 列执行一次操作。

同理，如果对第 $j$ 列执行了操作，存在 $i$ 满足 $B_{i,j}=0$，那么必然需要在此之后对第 $i$ 列执行一次操作。

由此可以建立一个有向图，$x \rightarrow y$ 代表 $x$ 操作执行完成后必须执行 $y$ 操作。

从每个必须执行的操作出发 dfs，如果找到环，那么必然无解。

如果最终没有找到环，显然是有解的。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-27 18:21:37

本题披着博弈论的外衣，实际上，除了第一步用 Nim 定理转化题意以外，跟博弈论没什么关系。

题意

给定一个长度为 $n$ 的非负整数数组。

给定 $q$ 次询问，每次给定一个区间 $[l,r]$，问这个区间最多删除多少个位置，使得剩下的位置上的数异或和为 $0$。

不能删完，同时求出能使删除数字数量最多的方案数量。

两个方案不同当且仅当删除的位置的集合不同。

无解输出 $-1$。

做法

注意到值域是 $[0,50]$，也就是说最多有 $51$ 种数字。

对于每一种数字，其最多保留 $2$ 个，证明是假如最优解中出现多于 $2$ 个相同的数字，那么可以删除两个这样的数字得到更优的解。

随后 dp，$dp_{i,j,0/1}$ 代表前 $i$ 种数字，保留的数字异或和为 $j$，且前 $i$ 个数字是否全部删除。

状态转移的话，只需要对于每种数字，枚举其保留了几个，转移是显然的。

这是我的 dp 转移的代码：

int rem[51];\/\/ 每种数字出现的次数
int top;\/\/ 有多少不同的数字
dp[0][0][0]=0;\/\/ 最多删多少个
ways[0][0][0]=1; \/\/ 保证删最多个的方案数
auto ckmxdp=[&](int nxti,int nxtj,int nxtk,int i,int j,int k,int add,ll waymult)->void{
    \/\/ nxti,nxtj,nxtk 代表新的状态，i,j,k 是旧的状态，add 是旧的状态转移后 dp 值加上多少,waymult 是本次选保留的位置的方案数。
    if(dp[nxti][nxtj][nxtk]<dp[i][j][k]+add){
        dp[nxti][nxtj][nxtk]=dp[i][j][k]+add;
        ways[nxti][nxtj][nxtk]=ways[i][j][k]*waymult;
    }else if(dp[nxti][nxtj][nxtk]==dp[i][j][k]+add){
        ways[nxti][nxtj][nxtk]+=ways[i][j][k]*waymult;
    }
    ways[nxti][nxtj][nxtk]%=mod;
};
for(int i=0;i<top;i++){
    for(int j=0;j<=63;j++){
        for(int k=0;k<=1;k++){
            \/\/ 当前这个数不对总 xor 造成影响。  
            \/\/ 情况：保留 0 或 2 个。
            ckmxdp(i+1,j,k,i,j,k,rem[i+1],1);
            if(rem[i+1]>=2){
                ckmxdp(i+1,j,1,i,j,k,rem[i+1]-2,((ll)rem[i+1]*(rem[i+1]-1)\/2)%mod);
            }
            \/\/ 当前这个数对总 xor 造成影响。  
            \/\/ 情况：保留 1 个.
            if(rem[i+1]>=1){
                ckmxdp(i+1,j^b[i+1],1,i,j,k,rem[i+1]-1,rem[i+1]);
            }
        }
    }
}
if(dp[top][0][1]>=0){
    printf("%d %lld\n",dp[top][0][1],(ways[top][0][1]%mod+mod)%mod);
}else{
    puts("-1");
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-31 14:04:28

vp 被卡死在这题了，写个题解记录一下。

题意

长度为 $n$ 的序列，第 $i$ 个数的值域范围是 $l_i,r_i$。

求所有可能的序列中，所有数出现次数平方和的最小可能的值。

做法

注意到每个位置 $i$ 都只能有一个数，并且这个数在 $[l_i,r_i]$ 之间，相当于位置 $i$ 可以为 $[l_i,r_i]$ 中的某个数贡献一次出现次数。

从这里可以想到网络流，由于最终每个数都要出现一次，考虑将原问题求的总代价作为费用，而最大流量设计为能有效安排的位置个数，这样保证了使用最小费用最大流可以在有解的情况下求出最小代价，当然，此时最大流是 $n$。

考虑一下发现，上述过程对应的是源点向每个位置 $i$ 连一条容量为 $1$，代价为 $0$ 的边，每个位置 $i$ 向数值 $[l_i,r_i]$ 连一条容量为 $1$，代价为 $0$ 的边。

由于每种数值 $j$ 的出现次数决定了最终代价，考虑每个数值 $j$ 向汇点连 $n$ 条容量为 $1$，费用分别为 $1^2-0^0,2^2-1^2,3^2-2^2,\cdots,n^2-(n-1)^2$ 的边。

然后跑最小费用最大流就行，我用的是 Dinic，用时 46ms。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const int maxn=55;
int n,q;
int mx[maxn],mn[maxn];
struct EDGE{
    int to,nxt;
    int lim,cost;
}edge[maxn*maxn*6];
int head[maxn*2];
int cnt=1;
void _add(int u,int to,int lim,int cost){
    edge[++cnt].to=to;
    edge[cnt].nxt=head[u];
    edge[cnt].lim=lim;
    edge[cnt].cost=cost;
    head[u]=cnt;
}
void add(int u,int to,int lim,int cost){
	\/\/printf("%d -> %d\n",u,to);
    _add(u,to,lim,cost);
    _add(to,u,0,-cost);
}
int source=0,receive;
int dis[maxn*2];
int cur[maxn*2];
bool ins[maxn*2];
bool vis[maxn*2];
bool bfs(){
    queue<int> q;
    memset(dis,0x3f,sizeof dis);
    memcpy(cur,head,sizeof head);
	memset(vis,0,sizeof vis);
    q.push(source);
    dis[source]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        ins[u]=0;
        for(int i=head[u];i;i=edge[i].nxt){
            int to=edge[i].to;
            if(edge[i].lim&&dis[to]>dis[u]+edge[i].cost){
                dis[to]=dis[u]+edge[i].cost;
                if(!ins[to]){
                    q.push(to),ins[to]=1;
                }
            }
        }
    }
    return (dis[receive]<=1e8);
}
int dfs(int u,int flow){
    if(!flow||u==receive)return flow;
    int used=0;
	vis[u]=1;
    for(int& i=cur[u];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(dis[to]==dis[u]+edge[i].cost&&!vis[to]&&edge[i].lim>0){
            int use=dfs(to,min(flow-used,edge[i].lim));
            edge[i].lim-=use;
            edge[i^1].lim+=use;
            used+=use;
        }
        
        if(used==flow)return used;
    }
    return used;
}
void Dinic(){
    int mxflow=0,totcost=0;
    while(bfs()){
        int nwflow=dfs(source,1e9);
        mxflow+=nwflow;
        totcost+=nwflow*dis[receive];
    }
    if(mxflow!=n){
        puts("-1");
    }else{
        printf("%d\n",totcost);
    }
}
void solve(int id_of_test){
	read(n);
    read(q);
    FOR(i,1,n){
        mn[i]=1,mx[i]=n;
    }
    receive=2*n+1;
    FOR(i,1,q){
        int t,l,r,v;
        read(t);
        read(l);
        read(r);
        read(v);
        if(t==1){
            FOR(j,l,r){
                ckmx(mn[j],v);
            }
        }else{
            FOR(j,l,r){
                ckmn(mx[j],v);
            }
        }
    }
    FOR(i,1,n){
        add(source,i,1,0);
    }
    FOR(i,1,n){
        FOR(j,mn[i],mx[i]){
            add(i,n+j,1,0);
        }
    }
    FOR(v,1,n){
        FOR(mult,1,n){
            add(v+n,receive,1,mult*mult-(mult-1)*(mult-1));
        }
    }
    Dinic();
}
int main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 10:05:32

A

每个序列的长度递增的，容易证明只需要 $O(\sqrt n)$ 个序列，总长度就能超过 $n$。

B

scanf("%d:%d") 可以较为快捷的读入。

C

求给定子数组中哪个位置上的数不等于给定的数 $x$。

考虑预处理每种数字在哪些区间没有出现过，并以端点升序记录。

查询的时候，如果存在一个合法的区间，那么右端点大于等于 $l$ 的最小的区间一定是合法的。

D

长度为 $2n$ 的数列，包含 $[1,n]$ 的数，每个数出现了两次，令 $d_i$ 为 $i$ 的两次出现位置的差。

求如何排列这个序列，使得 $\sum\limits_{i=1}^n (n-i)|d_i+i-n|$ 最小。

注意到原式的每一项都大于等于 $0$，总和也大于等于 $0$。

猜想存在一种构造方案使得这个值是 $0$。

这就要求每一项都构造出 $0$。

由此可得 $d_1=n-1,d_2=n-2,d_3=n-3,\cdots,d_{n-1}=1$，$d_n$ 可以等于任何值。

首先将两个 $1$ 放到 $1,n$ 的位置，两个 $3$ 放到 $2,n-1$ 的位置，依次类推。

然后把两个 $2$ 放到 $n+1,2n-1$ 的位置，两个 $4$ 放到 $n+2,2n-2$ 的位置，依次类推。

最后如果剩下两个位置，那就用来放 $n$。

E

给定一棵树，每个叶子节点有一只蚂蚁。

每秒可以同时移动一些蚂蚁，但要求除了 $1$ 以外任何节点不能有超过两只蚂蚁，求最少多少秒将所有蚂蚁移动到 $1$。

注意到 $1$ 的每个子树都是独立的，可以对于每个子树单独算答案，最后取 max。

考虑单个子树内部，让深度最浅的蚂蚁先去。

随后，深度第 $2$ 浅的蚂蚁至少在前一只蚂蚁的下一秒才能到达终点，这个时间与自己原本与 $1$ 的距离取 max 就是真实时间。

后面依次类推就可以。

本题思路在于先将整个问题拆分为多个同类的子任务。

对于单个子任务，考虑实际顺序是怎么样的，根据这个过程去逐步递推求解。

F

给定 $n,k$，求 $\sum\limits_{i=1}^{n} i^k \pmod {{10}^9+7}$，$n \le 10^9,k \le 10^6$。

本题的答案是一个 $k+1$ 次多项式，但是我不会证明，这个坑以后再填。

拉格朗日插值的复杂度是 $O(k^2)$ 的，但是可以带入一些特殊值优化计算过程，此处代入 $1,2,\cdots,k+2$。

回想一下拉格朗日插值的形式，给定 $n$ 组 $x_i,y_i$，代表 $f(x_i)=y_i$。

然后 $f(p) = \sum\limits_{i=1}^n \frac{\prod\limits_{j \in [1,n],j\neq i}(p-x_j)}{\prod\limits_{j \in [1,n],j\neq i}(x_i-x_j)} y_i$。

回到本题，式子变为：
$f(p) = \sum\limits_{i=1}^{k+2} \frac{\prod\limits_{j \in [1,k+2],j\neq i}(p-j)}{\prod\limits_{j \in [1,k+2],j\neq i}(i-j)}\sum\limits_{j=1}^{i} j^k$。

考虑对于 $\forall x \in [1,k]$，右边式子里面 $i=x$ 时的贡献 $g_x$。

$g_x = \frac{\prod\limits_{j \in [1,k+2],j\neq x}(p-j)}{\prod\limits_{j \in [1,k+2],j\neq x}(x-j)}\sum\limits_{j=1}^{x} j^k$。

$\sum\limits_{j=1}^x j^k$ 可以预处理，$O(1)$ 计算。

$\prod\limits_{j \in [1,k+2],j\neq x}(p-j)$ 相当于 $\prod\limits_{j \in [1,k+2]}(p-j)$ 乘上 $p-x$ 的逆元，同样可以通过预处理逆元 $O(1)$ 计算。

$\prod\limits_{j \in [1,k+2],j\neq x}(x-j) = \prod\limits_{j=1}^{x-1}(x-j)\prod\limits_{j=x+1}^{k+2} (x-j) = \prod\limits_{j=1}^{x-1} j \prod\limits_{j=1}^{k+2-x} (-j)$。
本部分可以预处理阶乘，逆元乘积 $O(1)$ 计算。

我们成功得到了一个 $O(k)$ 的算法！

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 10:52:08

参照：洛谷本题第二篇题解。

首先，注意到从 $i$ 走到 $i+1$ 的边的边权可以算到 $i+1$ 的点权上，这样就将边权转化为了点权。

设 $f_i$ 代表时间为 $i$ 的最大收益。

$r_{i,j}$ 代表时间 $i$ 到达位置 $j$ 的奖励。

$c_i$ 代表第 $i$ 个工厂的单个机器人花费。

$s_{i,j}$ 代表从 $1$ 时刻开始，一直向前走，走到 $i$ 时刻，到达 $j$ 工厂的总收益。

对于 $f$ 的计算，升序枚举时间 $i$，枚举此时的位置 $j$，然后再枚举上一次机器人走了 $k$ 步到达的当前节点。

$f_i = \max(f_{i-k}+s_{i,j}-s_{i-k,j-k}-c_{j-k})$。

设 $rec_{i,j} = {f_i-s_{i,j}-c_{j}}$。

$f_i = \max(rec_{i-k,j-k})+s_{i,j}$。

接下来每个对角线维护一个单调队列就搞定了。