【2018 BSUIR Final C】Partial Sums問題解
12009 ワード
テーマの大意
nを1つ与える× m n\times m n×mの01行列A 0 A_0 A0.1回の動作は、この矩形の各要素を、A k[i,j]=(Σu=1 iΣv=1 j Ak−1[u,v])＃(m o d)2 A_k[i,j]=(\sum_{u=1}^i\sum_{v=1}^j A_{k-1}[u,v])\bmod 2 Ak[i,j]=(∑u=1i∑v=1jAk−1[u,v])mod2. 最小の正の整数k k k k kを求め、A 0=A k A_0=A_k A0=Ak.
n × m ≤ 1 0 6 n\times m\leq 10^6 n×m≤106
\\ \\ \\
問題解
まず,答えは2 2 2 2のべき乗に違いないことが分かった.この結論をこのように説明することができ、k i,j k_とする.{i,j}ki,jは左上角が(1,1)(1,1)(1,1)右下角が(i,j)(i,j)(i,j)のサブ矩形の答えを表し,k i,j k_{i,j}ki,jは、少なくともl c m(k i−1,j,k i,j−1)lcm(k_{i−1,j},k_{i,j−1})lcm(ki−1,j,ki,j−1)であり、このl c m lcmホイールが後(i,j)(i,j)(i,j)(i,j)の要素が変化しない場合、k i,j k_{i,j}ki,jはこれに等しい.そうしないと、l c m lcmホイールに戻ってくる.すなわち、k i,j=l c m⋅2 k_{i,j}=lcm\cdot 2 ki,j=lcm⋅2.またk 1のため、1=1 k_{1,1}=1 k 1,1=1であるため,任意k i,j k_を帰納証明できる.{i,j}ki,jは必ず2 2 2のべき乗である.
次に、k k k kホイール操作により、1つの格子(x,y)(x,y)(x,y)が右下の1つの格子(x+Δ x , y + Δ y ) (x+\Delta x,y+\Delta y) (x+Δx,y+Δy)の貢献はいくらですか. これは1つの駒が(x,y)(x,y)(x,y)(x,y)から始まり、その右下の1つの位置(自分自身を含む)にジャンプするたびに、k kステップ(x+Δ x , y + Δ y ) (x+\Delta x,y+\Delta y) (x+Δx,y+Δy)、のシナリオ数はいくらですか.これは明らかに(Δ x + k − 1 k − 1 ) ⋅ ( Δ y + k − 1 k − 1 )\binom{\Delta x+k-1}{k-1}\cdot\binom{\Delta y+k-1}{k-1} (k−1Δx+k−1)⋅(k−1Δy+k−1). Lucasの定理によると、k k kが2 2 2のべき乗である場合、Δ x\Delta x Δx和Δ y\Delta y Δyがいずれもk k kの倍数である場合,この式はやっと
そこでk=1,2,4,8,⋯k=1,2,4,8,cdots k=1,2,4,8,cdots k=1,2,4,8,⋯というように答えを列挙することができ,列挙のたびに各位置はΔ x\Delta x Δx和Δ y\Delta y Δyはk k k倍数の位置の寄与であり,O(n m)O(nm)O(nm)が最終行列を導出し判断できる.(コードを見る)
コード#コード#
nを1つ与える× m n\times m n×mの01行列A 0 A_0 A0.1回の動作は、この矩形の各要素を、A k[i,j]=(Σu=1 iΣv=1 j Ak−1[u,v])＃(m o d)2 A_k[i,j]=(\sum_{u=1}^i\sum_{v=1}^j A_{k-1}[u,v])\bmod 2 Ak[i,j]=(∑u=1i∑v=1jAk−1[u,v])mod2. 最小の正の整数k k k k kを求め、A 0=A k A_0=A_k A0=Ak.
n × m ≤ 1 0 6 n\times m\leq 10^6 n×m≤106
\\ \\ \\
問題解
まず,答えは2 2 2 2のべき乗に違いないことが分かった.この結論をこのように説明することができ、k i,j k_とする.{i,j}ki,jは左上角が(1,1)(1,1)(1,1)右下角が(i,j)(i,j)(i,j)のサブ矩形の答えを表し,k i,j k_{i,j}ki,jは、少なくともl c m(k i−1,j,k i,j−1)lcm(k_{i−1,j},k_{i,j−1})lcm(ki−1,j,ki,j−1)であり、このl c m lcmホイールが後(i,j)(i,j)(i,j)(i,j)の要素が変化しない場合、k i,j k_{i,j}ki,jはこれに等しい.そうしないと、l c m lcmホイールに戻ってくる.すなわち、k i,j=l c m⋅2 k_{i,j}=lcm\cdot 2 ki,j=lcm⋅2.またk 1のため、1=1 k_{1,1}=1 k 1,1=1であるため,任意k i,j k_を帰納証明できる.{i,j}ki,jは必ず2 2 2のべき乗である.
次に、k k k kホイール操作により、1つの格子(x,y)(x,y)(x,y)が右下の1つの格子(x+Δ x , y + Δ y ) (x+\Delta x,y+\Delta y) (x+Δx,y+Δy)の貢献はいくらですか. これは1つの駒が(x,y)(x,y)(x,y)(x,y)から始まり、その右下の1つの位置(自分自身を含む)にジャンプするたびに、k kステップ(x+Δ x , y + Δ y ) (x+\Delta x,y+\Delta y) (x+Δx,y+Δy)、のシナリオ数はいくらですか.これは明らかに(Δ x + k − 1 k − 1 ) ⋅ ( Δ y + k − 1 k − 1 )\binom{\Delta x+k-1}{k-1}\cdot\binom{\Delta y+k-1}{k-1} (k−1Δx+k−1)⋅(k−1Δy+k−1). Lucasの定理によると、k k kが2 2 2のべき乗である場合、Δ x\Delta x Δx和Δ y\Delta y Δyがいずれもk k kの倍数である場合,この式はやっと
そこでk=1,2,4,8,⋯k=1,2,4,8,cdots k=1,2,4,8,cdots k=1,2,4,8,⋯というように答えを列挙することができ,列挙のたびに各位置はΔ x\Delta x Δx和Δ y\Delta y Δyはk k k倍数の位置の寄与であり,O(n m)O(nm)O(nm)が最終行列を導出し判断できる.(コードを見る)
コード#コード#
#include
",k);
}