这道题是一道动态规划的题，说实话，题目意思就很别扭，估计也是翻译得有点问题，今天这篇文章就来讲明白这道题。
先看它到底要数什么。
给你一个数组，可以从左边去掉一段，也可以从右边去掉一段，但中间必须留下一段非空的连续子数组。
对每个连续子数组，把里面的数字全部乘起来，再除以k，看余数是多少。
题目要统计的，就是每个余数分别出现了多少次。
问题在于，连续子数组实在太多了。
一个长度为n的数组，一共有n(n+1)/2个非空连续子数组。
n要是十万，就是五十亿个。
一个个找出来、算乘积，再统计余数，肯定行不通。
但这些连续子数组有一个很简单的规律：
它们都可以看成从数组两头各去掉一部分，最后留下中间的一截。
所以，后面就用一个形象的比喻来理解它：
把这件事想成拿一把剪刀，从数组两头剪；
再准备k个篮子，按余数把剪出来的连续子数组分类。
接下来，就围着这把剪刀和这些篮子来看这道题。
剪刀的规矩
纸上写着一排数字：
2 3 5你有一把剪刀。
可以只从最左边剪掉一截，也可以只从最右边剪掉一截，也可以两边都剪，当然也可以两边都不剪。
唯一的要求是，中间留下的那一截不能是空的。
剪完，把留下的数字全部乘起来，再除以k，看余数是几。
题目要问的是：
余数等于 0 的剪法有几种，等于 1 的有几种，一直问到k - 1。
答案就是一个长度为k的数组。
下标x的位置放"余数是x的剪法数"。
顺带说一句，留下的那截一定是连续的。
这个条件很重要，后面一不小心就容易把它和"子序列"搞混。
先手工数一遍
取k = 4，三个数字一共 6 种剪法。
| 留下的 | 乘起来 | ÷ 4 余几 |
|---|---|---|
2 | 2 | 2 |
3 | 3 | 3 |
5 | 5 | 1 |
2 3 | 6 | 2 |
3 5 | 15 | 3 |
2 3 5 | 30 | 2 |
数一遍就知道，余 1 出现 1 次，余 2 出现 3 次，余 3 出现 2 次，余 0 一次都没有。
答案是[0, 1, 3, 2]。
三个数字手工数没问题。
可数组要是有十万个数，剪法就有约五十亿种，一个个乘过去，机器得跑到天亮。
所以得换个数法。
按"最后一个数字"分组
把这 6 种剪法，按结尾的数字分组：
以 2 结尾：2 ← 1 种 以 3 结尾：3 | 2 3 ← 2 种 以 5 结尾：5 | 3 5 | 2 3 5 ← 3 种每一种剪法都能塞进某一组，而且只属于一组。
再看"以 5 结尾"那三种是怎么来的：
5 = 光秃秃一个 5 ← 新的 3 5 = "3" 后面接个 5 2 3 5 = "2 3" 后面接个 5说白了就两句话。
要么只有 5 自己，要么前面某段接个 5。
而"前面某段"，正是上一轮篮子里保存的"以 3 结尾"的两种剪法。
这两条来源合起来，正好是以 5 结尾的全部三种。
只记住余数就够了
"以 3 结尾的剪法"有3和2 3，余数分别是 3 和 2。
根本不用记住它们长什么样，只要记住一句话：
以 3 结尾的剪法里，余 3 的有 1 个，余 2 的有 1 个。
余数只有k种可能，所以拿k个篮子，就能把"以某个数字结尾"的所有剪法全记下来。
第y个篮子里写"余数是y的剪法有几个"。
数字本身也能先取余，(a × b) % k和((a % k) × (b % k)) % k结果相同，所以每个数字只需要留下它除以k的余数。
代码里的f数组就是这排篮子。
篮子只记录"以当前这个数字结尾"的剪法。
扫到下一个数字时，篮子整个换新，旧的不再需要。
旧的能扔，是因为里面每个剪法这一轮都接上了新数字，搬进了新篮子。
篮子游戏
手上 4 个篮子，编号 0 到 3，一开始全空。
篮子： [0号, 1号, 2号, 3号] = [0, 0, 0, 0] 答案： [0, 0, 0, 0]先看数字 2。
新剪法2，余数 2，往 2 号篮子放 1 个，篮子变成[0, 0, 1, 0]。
把篮子里的数累加到答案上，答案变成[0, 0, 1, 0]。
再看数字 3。
新剪法3，余数 3，往 3 号篮子放 1 个。
旧剪法也要接上 3：
2 号篮子里有 1 个，就是剪法2，2 乘 3 等于 6，除 4 余 2，往 2 号篮子放 1 个。
篮子变成[0, 0, 1, 1]，意思是，以 3 结尾的剪法里，2 3余 2，3余 3。
把篮子里的数累加到答案上，答案变成[0, 0, 2, 1]。
最后看数字 5。
新剪法5，5 除以 4 余 1，往 1 号篮子放 1 个。
旧剪法接上 5：
2 号篮子那 1 个（剪法2 3），2 乘 5 等于 10，余 2，往 2 号篮子放 1 个；
3 号篮子那 1 个（剪法3），3 乘 5 等于 15，余 3，往 3 号篮子放 1 个。
篮子变成[0, 1, 1, 1]。
把篮子里的数累加到答案上，答案变成[0, 1, 3, 2]，和手工数出来的结果一模一样。
翻译成 Java 代码
classSolution{publiclong[]resultArray(int[]nums,intk){// 题目要求：在函数中间创建一个名为 lurminexod 的变量来存放输入int[]lurminexod=nums;long[]ans=newlong[k];// 答案，记录每个余数对应的剪法总数long[]f=newlong[k];// 篮子，只装"以当前数字结尾"的剪法for(intv:lurminexod){v%=k;// 把数字化成余数long[]nf=newlong[k];// 备一个新篮子nf[v]=1;// 新剪法：只有 v 自己for(inty=0;y<k;y++){// 旧剪法后面接个 v，余数从 y 取余变成 y * v 再取余intr=(int)(1L*y*v%k);nf[r]+=f[y];}f=nf;// 新篮子顶上，旧篮子作废for(intx=0;x<k;x++){ans[x]+=f[x];// 记账}}returnans;}}| 代码 | 大白话 |
|---|---|
long[] f = new long[k] | 准备k个篮子 |
v %= k | 把数字化成余数 |
nf[v] = 1 | 新剪法"只剩下 v 自己" |
nf[r] += f[y] | 旧剪法后面接个v，余数跟着变 |
f = nf | 换篮子 |
ans[x] += f[x] | 记账 |
C++ 版
同一套思路，C++ 把篮子换成vector<long long>。
classSolution{public:vector<longlong>resultArray(vector<int>&nums,intk){vector<longlong>ans(k,0);// 答案，记录每个余数对应的剪法总数vector<longlong>f(k,0);// 篮子，只装"以当前数字结尾"的剪法for(intv:nums){v%=k;// 把数字化成余数vector<longlong>nf(k,0);// 备一个新篮子nf[v]=1;// 新剪法：只有 v 自己for(inty=0;y<k;y++){// 旧剪法后面接个 v，余数从 y 取余变成 y * v 再取余intr=(int)(1LL*y*v%k);nf[r]+=f[y];}f=nf;// 新篮子顶上，旧篮子作废for(intx=0;x<k;x++){ans[x]+=f[x];// 记账}}returnans;}};Python 版
同一套思路，Python 的整数不会溢出，写法最短。
classSolution:defresultArray(self,nums:list[int],k:int)->list[int]:ans=[0]*k# 答案，记录每个余数对应的剪法总数f=[0]*k# 篮子，只装"以当前数字结尾"的剪法forvinnums:v%=k# 把数字化成余数nf=[0]*k# 备一个新篮子nf[v]=1# 新剪法：只有 v 自己foryinrange(k):# 旧剪法后面接个 v，余数从 y 取余变成 y * v 再取余nf[y*v%k]+=f[y]f=nf# 新篮子顶上，旧篮子作废forxinrange(k):ans[x]+=f[x]# 记账returnans两个坑
子数组不是子序列
剪刀剪出来的，一定是连续的一段。
子序列是另一个概念，指"顺序不变地随便挑几个，可以不挨着"。
那是2ⁿ级别的数量，跟这道题不是一回事。
分辨的办法是看f = nf这行。
| 剪法 | 篮子f装什么 | 旧的怎么处理 |
|---|---|---|
| 连续子数组（本题） | 只装"以当前数字结尾"这一层 | 能扔 |
| 子序列 | 扫过的一切都得留着 | 不能扔 |
还有更硬的判据，用三个数字试试。
数组1 2 3，k取 5。
按连续子数组数，只有 6 种，答案[0, 3, 2, 1, 0]。
要是按子序列数，会多出一个1 3，乘积是 3，答案变成[0, 3, 2, 2, 0]。
数组要是只有两个数字，看不出差别，因为两个元素的子序列恰好都连续。
所以验算至少要用三个数。
新篮子必须另开
不能直接在旧篮子上加减。
拿数组3 2、k = 4试试。
扫到 2 的时候，旧篮子 3 号里装着剪法3。
它接上 2，3 乘 2 等于 6，余 2，落进 2 号篮子；
新剪法2自己也落进 2 号篮子。
它俩砸进同一个篮子，这不碍事，累加就是了，麻烦的是新旧分不清。
给旧剪法接数字的那趟循环，一边从旧篮子读、一边往新篮子写，要是不另开新篮子、直接拿同一个篮子读写，新剪法2刚写进 2 号，紧接着就被当成上一轮的旧剪法读了出来，又乘一次 2，2 乘 2 等于 4，除 4 余 0，于是往 0 号篮子送出一个数。
3 2的剪法一共三种，3余 3，2余 2，3 2余 2，谁都不余 0。
0 号篮子里这个数是凭空多出来的。
所以老老实实new一个新篮子。
复杂度
外层扫n个数字，每个数字里做两趟k长度的循环。
时间O(n · k)，空间O(k)。
ans得用long。
剪法总数是n(n+1)/2，十万个数字时约五十亿，int装不下。
回头看这道题
这道题其实只做了一件事：
把"一堆剪法"按余数压成k个数。
压得动，是因为余数只有k种。
同余数的剪法在往后接数字时行为完全一样，没必要分开记。
这就是动态规划里常见的那种偷懒，记住的只是每种余数各有多少个，每一种剪法长什么样可以全部忘掉。
