对答案模 $n$ 的余数 $i$ 分类讨论。设每个周期季风位移为 $(x,y)$，终点矢量与 $1\dots i$ 时刻季风位移矢量和的差为 $(g_x,g_y)$。则问题转换为：考虑函数 $f(d)=|xd-g_x|+|yd-g_y|-k(nd+i)$，求最小自然数 $d$ 使得 $f(d)\leq 0$。

考虑 $f(d)$ 是一个由 不超过 $3$ 个折线段 构成的 凸函数。但我们不会分类讨论，考虑牛顿迭代法。具体而言：

初始时设指针 $p\larr 0$，进入以下循环：

• 循环开始时，已知 $∀0\leq d<p$，$f(d)>0$。
• 若 $f(p)\leq 0$，答案为 $p$，退出循环。
• 若 $f(p)\leq f(p+1)$，根据函数凸性，$∀d\geq p$，$f(d)>0$，故无解，退出循环。
• 假设答案在 $p$ 所在折线段上，可知其为 $p'=p+\lceil\frac{f(p)}{f(p)-f(p+1)}\rceil$（类似于找到当前折线段与 $x$ 轴的交点）。
• 根据函数凸性，$∀p\leq d<p'$，$f(d)>0$。于是令 $p\larr p'$。

对于倒数第二步，$f(p')>0$ 意味着 $p$ 与 $p'$ 不在同一折线段上；而折线段个数不超过 $3$，对于每个余数求解时间为 $\Theta(1)$，总复杂度 $\Theta(n)$。

#include <bits/stdc++.h>
#include <windows.h>
#include <conio.h>

using namespace std;

int a[1111][1111], vis[99999], mx[1111];
HDC Hdc = GetDC(GetConsoleWindow());

int mix(int ca, int cb, double rt){
	int Ar=(ca>>16);
	int Ag=((ca>>8)&((1<<8)-1));
	int Ab=(ca&((1<<8)-1));
	int Br=(cb>>16);
	int Bg=((cb>>8)&((1<<8)-1));
	int Bb=(cb&((1<<8)-1));
	int R=int(floor(rt*double(Ar)+(1.0-rt)*double(Br)));
	int G=int(floor(rt*double(Ag)+(1.0-rt)*double(Bg)));
	int B=int(floor(rt*double(Ab)+(1.0-rt)*double(Bb)));
	return (max(0,min(255,R))<<16)+(max(0,min(255,G))<<8)+max(0,min(255,B));
}
int L = 1;
void _(int x, int y, int c) {
	x*=L; y*=L;
	for (int i=0; i<L; ++i) {
		for (int j=0; j<L; ++j) {
			SetPixel(Hdc, x+i+30, y+j+30, c);
		}
	}
}
int main() {
	system("color F0");
	int cc=0, N=1000;
	for (int i=0; i<=N; ++i) {
		for (int j=0; j<=N; ++j) {
			if (i>j) {
				a[i][j]=a[j][i]; continue;
			}
			if ((i)||(j)) {
				++cc;
				for (int ii=0; ii<i; ++ii) vis[a[ii][j]]=cc;
				for (int jj=0; jj<j; ++jj) vis[a[i][jj]]=cc;
				for (int d=1; d<=min(i,j); ++d) vis[a[i-d][j-d]]=cc;
				while (vis[a[i][j]]==cc) ++a[i][j];
			}
			mx[max(i,j)] = max(mx[max(i,j)],a[i][j]);
		}
	}
	for (int i=1; i<=N; ++i) mx[i]=max(mx[i],mx[i-1]);
	for (;;) {
		for (int i=0; i<=N; ++i) {
			for (int j=0; j<=N; ++j) {
				if (!a[i][j]) _(i,j,0x000000);
				else _(i,j,mix(0x0000EE,0xFFCC66,double(a[i][j])/double(mx[max(i,j)])));
			}
		}
	}
	return 0;
}

考场上比较好想的一个解法，也是目前最快解。

设 $m$ 为所有 $w_i$ 的最小公倍数，$f_{i,j}$ 为前 $i$ 总物品填充 $j$ 权值的方案数，$F_i=f_{n,i}$。

枚举下标模 $m$ 的余数 $r$，可观察到 $f_{k,mx+r}$ 是一个关于 $x$ 的 $k-1$ 次函数。分析完全背包递推过程，由于 $w_i\ |\ m$，有

$$f_{k,mx+r}=\sum_{p}[p\equiv r\ (\text{mod}\ w_i)]\sum_{y=0}^{x-[p>r]}f_{k-1,my+p} $$

结合一个著名结论“$\forall k\in\bf N$，$\sum_{i=1}^xi^k$ 是关于 $x$ 的 $k+1$ 次函数”，可以归纳证明这一点。

证明此结论后，解法便水落石出了。预处理 $F_{0\dots nm-1}$ 的值，然后可以拉格朗日插值求出任意 $F_x$。设 $w_i$ 中最小值为 $a$，观察到 $F_i\leq F_{i+a}$，于是按答案下标模 $a$ 的值分别二分求解。

拉格朗日插值中精度损失很大，所以需要维护浮点型、取模整型各一个。

---

当然还有

.