多項式を用いて、解説します。

\(i=k+1\) として操作することを \(x^k\) と対応させることで、本問は次のように言い換えることができます：

多項式 \(A \in \mathbb{Z}[x]\) が与えられる。以下を満たす多項式 \(f\in \mathbb{Z}[x]\) が存在するかを判定し、存在する場合にはその係数の和の最小値を求めよ

• \((1-2x+x^2)f(x) \equiv A(x) \pmod{1-x^N}\)（つまり左辺と右辺の差がある \(g \in \mathbb{Z}[x]\) を用いて \(g(x)(1-x^N)\) と書ける）
• \(f\) の係数は非負整数

【注】未知数は \(f\) ですから、合同式は 未知数に関する \(1\) 次合同式です。したがって、\(a, b, n\in \mathbb{Z}\) に対して方程式 \(ax\equiv b\pmod{n}\) を考察するときと似た手順で考察を進めることができます。

【注】\(a, b, n\in \mathbb{Z}\) （ただし \(n>0\)）の場合には、\(1\) 次合同式 \(ax\equiv b \pmod{n}\) はの解の構造は次のようになります。

• \(g = \gcd(a,n)\) とする。
  • \(g\nmid b\) ならば解なしである
  • \(g\mid b\) ならば式全体を \(g\) で割り、\((a/b)x\equiv (b/g)\pmod{n/g}\) と変形できる。つまり、\(a,n\) が互いに素な場合の問題に帰着できる
• \(a,n\) が互いに素ならば、\(ax\equiv b\pmod{n}\) は \(n\) を法として一意な解を持つ。

この解説では、この事実やその証明に対する理解を前提とし、多項式に対して同様の考察を行うことで問題を解きます。

---

とりあえず係数の整数性・非負性は無視して考察を進めます。つまり、\(\mathbb{Q}[x]\) において、\((1-x)^2f(x)\equiv A(x)\pmod{1-x^N}\) を満たす \(f\) が存在するか・存在するならばどのようなものかを調べます。

この場合、\(\gcd(a,n)\) にあたるものは \(\gcd((1-x)^2, 1-x^n) = 1-x\) です。

まず、\(1-x\nmid A(x)\) のときは解なしです。そうでないとき、\(A(x) = (1-x)B(x)\) となる \(B\) をとり \(1-x\) で割ることで、条件は

\((1-x)f(x)\equiv B(x) \pmod{1+x+\cdots+x^{n-1}}\)

と書くことができます。

---

\(\mathbb{Q}[x]\) において、\(1-x\) と \(1+x+\cdots+x^{n-1}\) は互いに素です。\(a,b\) が互いに素なときに \(ax\equiv b\pmod{n}\) が \(n\) を法として一意な解を持つように、

\((1-x)f(x)\equiv B(x) \pmod{1+x+\cdots+x^{N-1}}\)

も \(\mathbb{Q}[x]\) において \((1+x+\cdots+x^{n-1})\) を法として一意な解を持ちます。

【注】体上の1変数多項式環では、除法が定義できて、\(\mathbb{Z}\) で行えた議論の多くが同様に行えることから分かります。確認してみてください。

そのひとつを求めるには、\(B(x) + c(1+x+\cdots+x^{N-1})\) が \(1-x\) で割り切れるような \(c\in \mathbb{Q}\) を求めればよいですが、これは剰余定理より \(c = -B(1)/N\) により求まります。

この \(c\) を求めて、\(f_0(x) = \frac{B(x) + c(1+x+\cdots+x^{N-1})}{1-x}\) とすることで、ひとつの解 \(f = f_0\) が得られました。

---

一般の \(f\) は、\(1-x^N\) を法として、これに \((1+x+\cdots+x^{N-1})\) の定数倍を加えたものと一致します。あとはこれが非負整数にできるかを判定し、係数の和を最小化するという課題がありますが、これは容易です。