No.3677 Global Checksum
みうね
harurun
TKTYI
問題文最終更新日: 2026-09-03 22:51:33
注意：この問題は実行時間制限が非常に厳しく設定されています。
問題文
$H$ 行 $W$ 列の整数からなる表 $A$ が与えられます。
各行 $i\ (1 \leq i \leq H)$ のチェックサム $S_i$ を
$$S_i = \left(\sum_{j=1}^{W} A_{i,j}\right) \bmod 2^{32}$$と定めます。また、データ全体のチェックサム $T$ を
$$T = \left(\sum_{i=1}^{H} S_i\right) \bmod 2^{32}$$と定めます。
各行 $i\ (1 \leq i \leq H)$ について、検証コード $C_i$ を
$$C_i = (S_i+T) \bmod 2^{32}$$と定めます。$C_1,C_2,\ldots,C_H$ を求めてください。
入力
入力は以下の形式で標準入力から与えられます。
$H\ W$
$A_{1,1}\ A_{1,2}\ \ldots\ A_{1,W}$
$A_{2,1}\ A_{2,2}\ \ldots\ A_{2,W}$
$\vdots$
$A_{H,1}\ A_{H,2}\ \ldots\ A_{H,W}$
制約
- $1\le H\le 10^6$
- $1\le W$
- $HW\le 4\times 10^6$
- $0\le A_{i,j}<10^9$
- 入力される値はすべて整数
出力
$C_1,C_2,\ldots,C_H$ をこの順に、1 行に 1 つずつ十進表記の非負整数として出力してください。
出力の末尾に改行してください。
サンプル
サンプル1
入力
3 2 1 2 3 4 5 6
出力
24 28 32
各行のチェックサムは順に $3,7,11$ であり、$T=21$ です。したがって、検証コードは順に $24,28,32$ となります。
サンプル2
入力
2 5 900000000 900000000 900000000 900000000 900000000 999999999 0 1 999999998 500000000
出力
2910065406 910065404
第 $1$ 行の和は $4500000000$ なので、$S_1=205032704$ となります。 また、$S_2=2499999998$ であるため、$T=2705032702$ です。 したがって、$C_1=2910065406, C_2=910065404$ となります。
サンプル3
入力
4 3 0 1 2 999999999 999999998 999999997 400000000 400000000 400000000 123456789 987654321 42
出力
1016143856 4016143847 2216143853 2127255005
各行のチェックサムは順に $3,2999999994,1200000000,1111111152$ です。 これらの和を $2^{32}$ で割った余りは $1016143853$ なので、$T=1016143853$ となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。