No.1039 Project Euler でやれ
タグ : / 解いたユーザー数 15
作問者 :
testestest
/ テスター :
37zigen
ストーリー
yukiさんは次のような問題を作りました。
長さNの数列aが与えられます。
次の2種類のクエリQ個に答えてください。
・1 x y $a_x$を$y$に変更する ($0 \leq x < N,\ \ 0\leq y < M$)
・2 x y $a_x + a_{x+1} + ... + a_y \pmod M$を出力する ($0\leq x \leq y < N$)
Binary Indexed Treeを知っていますか？ yukiさんは知っています。
この問題はBinary Indexed Treeを用いて解くことができます。
yukiさんはBinary Indexed Treeが好きです。
ところで、集合と二項演算の組であって、いい感じの条件を満たすものをアーベル群といいます。
(正確な定義はwikipediaを参照してください：アーベル群)
Binary Indexed Treeには一般にアーベル群の構造がのることが知られています。
つまり、集合$\{0,...,M-1\}$が二項演算★によってアーベル群を成すならば、上記問題の2つ目のクエリを
・2 x y $a_x ★ a_{x+1} ★ ... ★ a_y$ を出力するに置き換えてもBinary Indexed Treeで解くことができます。
問題文
集合$\{0,...,M-1\}$上の二項演算であって、アーベル群を成すものは何種類存在するでしょうか？ $\bmod 10^9+7$で答えてください。入力
$M$
$1\leq M < 10^6$
出力
$\{0,...,M-1\}$上の二項演算であって、アーベル群を成すものの個数を $\bmod 10^9+7$で出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3
出力
3
次の3種類の演算が存在します。
$x ★ y = x+y \pmod 3$
| ★ | 0 | 1 | 2 |
| 0 | 0 | 1 | 2 |
| 1 | 1 | 2 | 0 |
| 2 | 2 | 0 | 1 |
$x ★ y = x+y+1 \pmod 3$
| ★ | 0 | 1 | 2 |
| 0 | 1 | 2 | 0 |
| 1 | 2 | 0 | 1 |
| 2 | 0 | 1 | 2 |
$x ★ y = x+y +2\pmod 3$
| ★ | 0 | 1 | 2 |
| 0 | 2 | 0 | 1 |
| 1 | 0 | 1 | 2 |
| 2 | 1 | 2 | 0 |
サンプル2
入力
4
出力
16
$x ★ y = x+y+k \pmod 4$ や $x ★ y = x \ \mbox{XOR}\ y\ \mbox{XOR} \ k\ (0\leq k < 4)$ などの他、次のような謎の演算も条件を満たします。
| ★ | 0 | 1 | 2 | 3 |
| 0 | 3 | 2 | 0 | 1 |
| 1 | 2 | 3 | 1 | 0 |
| 2 | 0 | 1 | 2 | 3 |
| 3 | 1 | 0 | 3 | 2 |
この謎の演算は、例えばpythonで次のように計算されます。
pow(2,pow(3,x,5)+pow(3,y,5)+1,5)%4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。