素数棋盘

Prompt

题目叫 《素数棋盘》。​ 设 p 为任意素数，​n\ge 2。​棋盘上的格子由 V=\{0,1,\ldots,p-1\}^{n} 中的向量编号，​共有 p^n 格，​每格写一个整数，​初始全部为 0。​ 一次操作为：​选择不全为零的向量 a=(a_1,\ldots,a_n) 以及 b\in\{0,\ldots,p-1\}，​把所有满足 a_1x_1+\cdots+a_nx_n\equiv b\pmod p 的格子中的数，​同时加 1，​或者同时减 1。​ 注意：​只有选择格子的条件取模，​格子里的整数不取模。​ 若两个局面可以通过有限次操作互相变成对方，​就称它们等价。​ 求解以下三个问题：​ 1. 完整分类。​ 为任意整数局面设计一组余数不变量，​使两个局面等价，​当且仅当它们的所有余数相同。​要求各个模数都是 p 的正整数次幂，​并且不变量彼此独立，​即每一种余数组合都能出现。​必须给出显式公式。​ 2. 精确计数。​ 求等价类总数，​答案须写成关于 p,n 的闭式。​ 3. 孤点制造。​ 希望最终只有原点上的数为正整数 m，​其余全部为 0。​找出所有可行的 m，​求每个可行 m 所需的最少操作次数，​并刻画、计数全部最短方案。​ 第三问不计操作的先后顺序；​影响同一组格子、增减方向相同的操作视为同一种操作。​