No.8112 区間和係数多項式？

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > ネタ問題

No.8112 区間和係数多項式？

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : 👑

p-adic / テスター :

Shirotsume

0 ProblemId : 10632 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2024-04-01 20:16:29

注意

この問題は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

入力

出力

$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

入力

出力

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

入力

出力

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

入力

出力

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もしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

No.8112 区間和係数多項式？

注意

問題文

入力

制約

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力

サンプル4

入力

出力