数え上げN本ノック

数え上げN本ノック.md

特に注意がない場合はM＝1,000,000,007でMODを取ってください。 TLEは2sec

注意

答えはありません． ときどき筆者も解けるかどうかわかっていない問題があります．

Episode 0 基礎

Mは素数とは限らないことに注意せよ．

• 0.1 aのb乗mod Mをもとめよ(a,b< 10^18, M < 10^9)
• 0.2 ax = b mod M となるxが存在するか判定し存在するなら一つ教えて(a, b < 10^18, M < 10^9)
• 0.3 aの(bのc乗)乗 mod M を求めよ(a,b,c < 10^18, M < 10^9)
• 0.4 1以上N以下の整数のうちMと互いに素なものすべてに対して，mod Mでの逆元をあわせてO(N)で求めよ． (N < 10^6, M < 10^9)

Episode 1 グリッド上の経路の数え上げ

• 1.1. (i,j)から(i+1,j)か(i,j+1)に移動できるとする。(0,0)から(x,y)までの移動経路の個数を求めよ。 (x,y < 10^6)
• 1.2. 問1.1について(i>j)点(i,j)を通ってはいけない時の移動経路の個数を求めよ。
• 1.3. 問1.1について、追加で通ってはいけない点がN個与えられる。それらの点を通らない移動経路の個数を求めよ。 (N < 3000)
• 1.4. 問1.1について、(i,j)から(i-1,j)や(i,j-1)に移動してもいいものとする。(0,0)からちょうど(x+y+k)回の移動をしたときに(x,y)にいるような経路の個数を求めよ。(k < 10^6)
• 1.5. 問1.4について、(0,0)と(x,y)を(0 <= i <= x かつ 0 <= j <= y)となるような(i,j)しか通ってはいけない時はどうか？(k < 10^6)
• 1.6 問1.5について、(i,j)から(i-1,j)にはいけるが、(i,j-1)には行けないとする。同じ頂点を2度通ってはいけない場合の移動経路数を求めよ。(x <= 10, y <= 10^9)
• 1.7 問1.6について、(i,j)から(i,j-1)にも行けるとしたらどうか？(x <= 10, y <= 10)

Episode 2 玉と箱

• 2.1 n個の区別がつく玉とｍ個の区別がつく箱がある。玉を箱に分配する方法は何通りあるか。(n,m < 10^18)
• 2.2 問2.1について玉だけ区別がつかない場合はどうか？(n,m < 10^18)
• 2.3 問2.1について箱だけ区別がつかない場合はどうか？(n,m < 3000)
• 2.4 問2.1について玉も箱も区別がつかない場合はどうか？(n,m < 300)

Episode 3 約数

• 3.1 Nの約数の個数d(N)を求めよ (N < 10^14)
• 3.2 1以上N以下の素数の個数を求めよ (N < 10^7)
• 3.3 1以上N以下のiについてd(i)の総和を求めよ(N < 10^14)

Episode 4 グラフ

• 4.1 N頂点の連結な単純グラフの数を数えよ。頂点の区別はつくとする(N < 10^18)
• 4.2 問4.1について頂点の区別がつかないときはどうか？
• 4.3 N頂点の木の数を数えよ。頂点の区別はつくとする(N < 10^18)
• 4.4 問4.3について頂点の区別がつかないときはどうか？
• 4.5 N頂点の連結な単純グラフが与えられる。全域木の個数を求めよ(N < 300)

Episode 5 数列

• 5.1 N個の整数A_1, ..., A_Nが与えられる,総和が0となる3つ組の個数を求めよ(N < 3000, |A_i| < 10^9)
• 5.2 N個の整数A_1, ..., A_Nが与えられる。A_i > A_j かつ i < jとなる(i,j)の組の個数を数え上げよ (N < 10^6)
• 5.3 N個の整数A_1, ..., A_Nが与えられる。最長増加部分列の個数を求めよ。(N < 10^6)
• 5.4 N個の整数A_1, ..., A_Nが与えられる。（A_l, A_l+1, ... , A_r)が(A_r, A_r-1, ..., A_l)と一致する(l<=r)の組の個数を求めよ(N < 10^6)

Episode 6 コンビネーション（二項係数）

特に記述のない場合Mは素数とは限らないことに注意せよ．

• 6.1 nCk mod M を求めよ (n, k <= 10, M <= 1000000007)
• 6.2 nCk mod M を求めよ (n, k <= 1000, M <= 1000000007)
• 6.3 nCk mod M を求めよ (n <= 10^9, k <= 10^6, M は素数)
• 6.4 M<=10^9 を素数とする．「nCk mod M を求めよ (n <= 10^6, k <= 10^6)」に10^6回答えよ．
• 6.5 M<=10^6 を素数とする．「nCk mod M を求めよ (n, k <= 10^18)」に10^5回答えよ．
• 6.6 nCk mod M を求めよ (n, k <= 10^18, M <= 10^9)