No.1039 Project Euler でやれ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 14
作問者 : testestesttestestest / テスター : 37zigen37zigen
3 ProblemId : 3937 / 出題時の順位表
問題文最終更新日: 2020-04-24 18:50:59

ストーリー

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 
0012
1120
2201

$x ★ y = x+y+1 \pmod 3$
0 1 2 
0120
1201
2012

$x ★ y = x+y +2\pmod 3$
0 1 2 
0201
1012
2120

サンプル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 
03201
12310
20123
31032

この謎の演算は、例えばpythonで次のように計算されます。
pow(2,pow(3,x,5)+pow(3,y,5)+1,5)%4

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。