No.3112 区間和係数多項式？
タグ : / 解いたユーザー数 5
作問者 : 👑
p-adic
/ テスター :
Shirotsume
注意
この問題はApril Fool Contest 2024向けに作られたネタ問題です。
問題自体に嘘はありませんが、正攻法の考察で解くことは難しいかもしれません。
なおこの問題の実行時間制限は6000[ms]です。高速な言語・処理系の利用を推奨します。
参考までにwriter解はc++で2207[ms]、PyPy3で2691[ms]、Python3でTLEとなります。
問題文
入力に $3$ 個の正整数 $N, B, Q$ と $10$ 個の非負整数 $C_1, D_1, C_2, D_2, C_3, D_3, C_4, D_4, C_5, D_5$ が与えられます。
最初に長さ $N$ の非負整数列 $A$ が初項 $C_1$ 公比 $D_1$ の等比数列として与えられています。
まずは記法の導入です。$N$ 未満の各非負整数 $i$ に対し、$A_i$ で $A$ の $1+i$ 個目の成分を表します。
各正整数 $i$ に対し、$i$ の $2$ 進加法付値（$2$で割り切れる回数）を $\nu_2(i)$ と置き、$p(i) = i - 2^{\nu_2(i)}$ と定めます。
$N$ 未満の各非負整数 $j$ と非負整数 $y$ に対し、$A$ を用いて非負整数 $f(j,y)$ を以下のように再帰的に定めます：
$\displaystyle f(j,y) = \left\{ \begin{array}{ll} A_0 & (j = 0) \\ y f(p(j),y) + \sum_{i=p(j)+1}^{j} A_i & (j \neq 0) \end{array} \right. $
再帰的定義に慣れていない人向けの説明はこちらです。（クリックで開く）
いかなる正整数 $i$ に対しても $p(i) < i$ が成り立つので、$j$ に $p$ を反復して適用することでいずれ $0$ に到達します。その回数を $d$ と置くと、
$ f(j,y) = y^d A_0 + \sum_{n=0}^{d-1} \left( \sum_{p^{n+1}(j)+1}^{p^n(j)} A_i \right) y^n $
と表せます。右辺は $A$ の区間和を係数に持つ $y$ の多項式です。
以下で説明する $Q$ 個のクエリを処理してください。
各クエリは、$2$ 個の $N$ 未満の非負整数 $i,j$ と $2$ 個の非負整数 $x,y$ の組 $(i,j,x,y)$ です。
クエリ $(i,j,x,y)$ は以下のように処理します：
- まず $A$ の $1 + i$ 個目の成分 $A_i$ を $x$ で置き換えることで $A$ を更新する。
- 次に更新後の $A$ に対する $f(j,y)$ を $B$ で割った余りを求める。（以下、この値をこのクエリに対する回答と呼ぶ）
ただしクエリは入力から与えられません。$Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリ $(i,j,x,y)$ は
$\displaystyle (i,j,x,y) = ((C_2 D_2^{q-1}) \bmod N, (C_3 D_3^{q-1}) \bmod N, C_4 D_4^{q-1}, C_5 D_5^{q-1}) $
として定めます。ここで非負整数 $n$ に対する $n \bmod N$ は $n$ を $N$ で割った余りを表し、$0^0$ は $1$ と定義します。
入力
入力は以下の形式で標準入力から $6$ 行で与えられます：
- $1$ 行目に $N, B, Q$ が半角空白区切りで与えられます。
- $2$ 行目に $C_1, D_1$ が半角空白区切りで与えられます。
- $3$ 行目に $C_2, D_2$ が半角空白区切りで与えられます。
- $4$ 行目に $C_3, D_3$ が半角空白区切りで与えられます。
- $5$ 行目に $C_4, D_4$ が半角空白区切りで与えられます。
- $6$ 行目に $C_5, D_5$ が半角空白区切りで与えられます。
$N$ $B$ $Q$ $C_1$ $D_1$ $C_2$ $D_2$ $C_3$ $D_3$ $C_4$ $D_4$ $C_5$ $D_5$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq \textcolor{brown}{10^7}$ を満たす整数である。
- $B$ は $1 \leq B \leq \textcolor{red}{10^9}$ を満たす整数である。
- $Q$ は $1 \leq Q \leq \textcolor{blue}{10^6}$ を満たす整数である。
- $C_1$ は $0 \leq C_1 \leq \textcolor{red}{10^9}$ を満たす整数である。
- $D_1$ は $0 \leq D_1 \leq \textcolor{red}{10^9}$ を満たす整数である。
- $C_2$ は $0 \leq C_2 \leq \textcolor{brown}{10^7}$ を満たす整数である。
- $D_2$ は $0 \leq D_2 \leq \textcolor{brown}{10^7}$ を満たす整数である。
- $C_3$ は $0 \leq C_3 \leq \textcolor{brown}{10^7}$ を満たす整数である。
- $D_3$ は $0 \leq D_3 \leq \textcolor{brown}{10^7}$ を満たす整数である。
- $C_4$ は $0 \leq C_4 \leq \textcolor{red}{10^9}$ を満たす整数である。
- $D_4$ は $0 \leq D_4 \leq \textcolor{red}{10^9}$ を満たす整数である。
- $C_5$ は $0 \leq C_5 \leq \textcolor{red}{10^9}$ を満たす整数である。
- $D_5$ は $0 \leq D_5 \leq \textcolor{red}{10^9}$ を満たす整数である。
出力
$Q$ 以下の各正整数 $q$ に対し、$q$ 行目に $q$ 個目のクエリに対する回答を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1 1 0 1 0 0 0 1 1 1 1 0
出力
0
$N = 1$ であり、最初は $A = (0 \cdot 1^0) = (0)$ として与えられています。
$1$ 回目のクエリ $(i_1,j_1,x_1,y_1) = ((0 \cdot 0^0) \bmod N,(0 \cdot 1^0) \bmod N,1 \cdot 1^0,1 \cdot 0^0) = (0,0,1,1)$ により $A$ が
$\displaystyle (x_1) = (1) $
に置き換わり、
$\displaystyle f(j_1,y_1) = f(0,1) = A_0 = 1 $
を $B = 1$ で割った余り $0$ を出力します。
$Q = 1$ なので、これで全てのクエリが処理できました。
サンプル2
入力
2 2 2 1 1 1 0 0 1 1 0 1 0
出力
1 0
$N = 2$ であり、最初は $A = (1 \cdot 1^0,1 \cdot 1^1) = (1,1)$ として与えられています。
$1$ 回目のクエリ $(i_1,j_1,x_1,y_1) = ((1 \cdot 0^0) \bmod N,(0 \cdot 1^0) \bmod N,1 \cdot 0^0,1 \cdot 0^0) = (1,0,1,1)$ により $A$ が
$\displaystyle (A_0,x_1) = (1,1) $
に置き換わり（結果的に変化せず）、
$\displaystyle f(j_1,y_1) = f(0,1) = A_0 = 1 $
を $B = 2$ で割った余り $1$ を出力します。
$2$ 回目のクエリ $(i_2,j_2,x_2,y_2) = ((1 \cdot 0^1) \bmod N,(0 \cdot 1^1) \bmod N,1 \cdot 0^1,1 \cdot 0^1) = (0,0,0,0)$ により $A$ が
$\displaystyle (x_2,A_1) = (0,1) $
に置き換わり、
$\displaystyle f(j_2,y_2) = f(0,0) = A_0 = 0 $
を $B = 2$ で割った余り $0$ を出力します。
$Q = 2$ なので、これで全てのクエリが処理できました。
サンプル3
入力
4 3 2 1 2 2 2 3 1 2 1 2 1
出力
2 0
$N = 4$ であり、最初は $A = (1 \cdot 2^0,1 \cdot 2^1,1 \cdot 2^2,1 \cdot 2^3) = (1,2,4,8)$ として与えられています。
$1$ 回目のクエリ $(i_1,j_1,x_1,y_1) = ((2 \cdot 2^0) \bmod N,(3 \cdot 1^0) \bmod N,2 \cdot 1^0,2 \cdot 1^0) = (2,3,2,2)$ により $A$ が
$\displaystyle (A_0,A_1,x_1,A_3) = (1,2,2,8) $
に置き換わり、
$\displaystyle \begin{array}{rcl} \displaystyle f(j_1,y_1) &\displaystyle = &\displaystyle f(3,2) \\ \displaystyle &\displaystyle = &\displaystyle 2 f(2,2) + \sum_{i=2+1}^{3} A_i \\ \displaystyle &\displaystyle = &\displaystyle 2^2 f(0,2) + 2 \sum_{i=0+1}^{2} A_i + \sum_{i=2+1}^{3} A_i \\ \displaystyle &\displaystyle = &\displaystyle 2^2 A_0 + 2 \sum_{i=0+1}^{2} A_i + \sum_{i=2+1}^{3} A_i \\ \displaystyle &\displaystyle = &\displaystyle 2^2 \cdot 1 + 2 \cdot (2 + 2) + 8 \\ \displaystyle &\displaystyle = &\displaystyle 4 + 8 + 8 \\ \displaystyle &\displaystyle = &\displaystyle 20 \end{array} $
を $B = 3$ で割った余り $2$ を出力します。
$2$ 回目のクエリ $(i_2,j_2,x_2,y_2) = ((2 \cdot 2^1) \bmod N,(3 \cdot 1^1) \bmod N,2 \cdot 1^1,2 \cdot 1^1) = (0,3,2,2)$ により $A$ が
$\displaystyle (x_2,A_1,A_2,A_3) = (2,2,2,8) $
に置き換わり、
$\displaystyle \begin{array}{rcl} \displaystyle f(j_1,y_1) &\displaystyle = &\displaystyle f(3,2) \\ \displaystyle &\displaystyle = &\displaystyle 2^2 A_0 + 2 \sum_{i=0+1}^{2} A_i + \sum_{i=2+1}^{3} A_i \\ \displaystyle &\displaystyle = &\displaystyle 2^2 \cdot 2 + 2 \cdot (2 + 2) + 8 \\ \displaystyle &\displaystyle = &\displaystyle 8 + 8 + 8 \\ \displaystyle &\displaystyle = &\displaystyle 24 \end{array} $
を $B = 3$ で割った余り $0$ を出力します。
$Q = 2$ なので、これで全てのクエリが処理できました。
サンプル4
入力
8 4 2 1 1 3 2 7 1 2 3 3 2
出力
3 3
$N = 8$ であり、最初は $A = (1 \cdot 1^0,1 \cdot 1^1,1 \cdot 1^2,1 \cdot 1^3,1 \cdot 1^4,1 \cdot 1^5,1 \cdot 1^6,1 \cdot 1^7) = (1,1,1,1,1,1,1,1)$ として与えられています。
$1$ 回目のクエリ $(i_1,j_1,x_1,y_1) = ((3 \cdot 2^0) \bmod N,(7 \cdot 1^0) \bmod N,2 \cdot 3^0,3 \cdot 2^0) = (3,7,2,3)$ により $A$ が
$\displaystyle (A_0,A_1,A_2,x_1,A_4,A_5,A_6,A_7) = (1,1,1,2,1,1,1,1) $
に置き換わり、
$\displaystyle \begin{array}{rcl} \displaystyle f(j_1,y_1) &\displaystyle = &\displaystyle f(7,3) \\ \displaystyle &\displaystyle = &\displaystyle 3 f(6,3) + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 3^2 f(4,3) + 3 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 3^3 f(0,3) + 3^2 \sum_{i=0+1}^{4} A_i + 3 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 3^3 A_0 + 3^2 \sum_{i=0+1}^{4} A_i + 3 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 3^3 \cdot 1 + 3^2 \cdot (1 + 1 + 2 + 1) + 3 \cdot (1 + 1) + 1 \\ \displaystyle &\displaystyle = &\displaystyle 27 + 45 + 6 + 1 \\ \displaystyle &\displaystyle = &\displaystyle 79 \end{array} $
を $B = 4$ で割った余り $3$ を出力します。
$2$ 回目のクエリ $(i_2,j_2,x_2,y_2) = ((3 \cdot 2^1) \bmod N,(7 \cdot 1^1) \bmod N,2 \cdot 3^1,3 \cdot 2^1) = (6,7,6,6)$ により $A$ が
$\displaystyle (A_0,A_1,A_2,A_3,A_4,A_5,x_2,A_7) = (1,1,1,2,1,1,6,1) $
に置き換わり、
$\displaystyle \begin{array}{rcl} \displaystyle f(j_1,y_1) &\displaystyle = &\displaystyle f(7,6) \\ \displaystyle &\displaystyle = &\displaystyle 6 f(6,6) + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 6^2 f(4,6) + 6 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 6^3 f(0,6) + 6^2 \sum_{i=0+1}^{4} A_i + 6 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 6^3 A_0 + 6^2 \sum_{i=0+1}^{4} A_i + 6 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 6^3 \cdot 1 + 6^2 \cdot (1 + 1 + 2 + 1) + 6 \cdot (6 + 1) + 1 \\ \displaystyle &\displaystyle = &\displaystyle 216 + 180 + 42 + 1 \\ \displaystyle &\displaystyle = &\displaystyle 439 \end{array} $
を $B = 4$ で割った余り $3$ を出力します。
$Q = 2$ なので、これで全てのクエリが処理できました。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。