当前位置:首页 >> 学科竞赛 >>

多项式及求和 By 浙江省镇海中学 杜瑜皓 (OI-WC2013)


多项式及求和
杜瑜皓
浙江省镇海中学

January 26, 2013

首先我们来看一个问题
n

i d mod m
i=0

首先我们来看一个问题
n

i d mod m
i=0

d ≤

50, n ≤ 1018 , m ≤ 1018

首先我们来看一个问题
n

i d mod m
i=0

d ≤ 50, n ≤ 1018 , m ≤ 1018 d ≤ 200, n ≤ 1010000 , m ≤ 1018 ,m为素数

首先我们来看一个问题
n

i d mod m
i=0

d ≤ 50, n ≤ 1018 , m ≤ 1018 d ≤ 200, n ≤ 1010000 , m ≤ 1018 ,m为素数 d ≤ 2000, n ≤ 1010000 , m ≤ 1018 ,m为素数

首先我们来看一个问题
n

i d mod m
i=0

d ≤ 50, n ≤ 1018 , m ≤ 1018 d ≤ 200, n ≤ 1010000 , m ≤ 1018 ,m为素数 d ≤ 2000, n ≤ 1010000 , m ≤ 1018 ,m为素数 d ≤ 200000, n ≤ 1010000 , m ≤ 1018 ,m为素数

1.d ≤ 50, n ≤ 1018 , m ≤ 1018

1.d ≤ 50, n ≤ 1018 , m ≤ 1018 我们令
n?1

Sd (n) =
i=0

id

1.d ≤ 50, n ≤ 1018 , m ≤ 1018 我们令
n?1

Sd (n) =
i=0

id

构造向量Vn = {Sd (n), n0 , n1 , . . . , nd }T

1.d ≤ 50, n ≤ 1018 , m ≤ 1018 我们令
n?1

Sd (n) =
i=0

id

构造向量Vn = {Sd (n), n0 , n1 , . . . , nd }T 转移: Sd (n + 1) = Sd (n) + nd

1.d ≤ 50, n ≤ 1018 , m ≤ 1018 我们令
n?1

Sd (n) =
i=0

id

构造向量Vn = {Sd (n), n0 , n1 , . . . , nd }T 转移: Sd (n + 1) = Sd (n) + nd
i

(n + 1) =
j=0

i

i j n j

1.d ≤ 50, n ≤ 1018 , m ≤ 1018 我们令
n?1

Sd (n) =
i=0

id

构造向量Vn = {Sd (n), n0 , n1 , . . . , nd }T 转移: Sd (n + 1) = Sd (n) + nd
i

(n + 1) =
j=0

i

i j n j

Vn+1 = Vn ? A

A是一个(d + 2) ? (d + 2)的矩阵,具体系数可以通过前面的 转移方程得出。

A是一个(d + 2) ? (d + 2)的矩阵,具体系数可以通过前面的 转移方程得出。 用矩阵乘法加快速幂优化,那么就可以在O(d 3 log n)的时间 内解决。

A是一个(d + 2) ? (d + 2)的矩阵,具体系数可以通过前面的 转移方程得出。 用矩阵乘法加快速幂优化,那么就可以在O(d 3 log n)的时间 内解决。 这里并没有除法运算,所以和m取值的关系并不大。

2.d ≤ 200, n ≤ 1010000 , m ≤ 1018 ,m为素数

2.d ≤ 200, n ≤ 1010000 , m ≤ 1018 ,m为素数 我们可以证明Sd (n)是关于n的d + 1次的多项式。

2.d ≤ 200, n ≤ 1010000 , m ≤ 1018 ,m为素数 我们可以证明Sd (n)是关于n的d + 1次的多项式。 进行一下简单的数学推导

2.d ≤ 200, n ≤ 1010000 , m ≤ 1018 ,m为素数 我们可以证明Sd (n)是关于n的d + 1次的多项式。 进行一下简单的数学推导 d = 0时显然成立

2.d ≤ 200, n ≤ 1010000 , m ≤ 1018 ,m为素数 我们可以证明Sd (n)是关于n的d + 1次的多项式。 进行一下简单的数学推导 d = 0时显然成立 假设d = k时成立

2.d ≤ 200, n ≤ 1010000 , m ≤ 1018 ,m为素数 我们可以证明Sd (n)是关于n的d + 1次的多项式。 进行一下简单的数学推导 d = 0时显然成立 假设d = k时成立 当d = k + 1时
d

(j + 1)

d+1

?j

d+1

=
i=0

d +1 i j i

d

(j + 1)

d+1

?j

d+1

=
i=0

d +1 i j i

d

(j + 1) 把j从0到n ? 1求和
n?1

d+1

?j

d+1

=
i=0

d +1 i j i

n?1 d

(j + 1)d+1 ? j d+1 =
j=0 j=0 i=0

d +1 i j i

d

(j + 1) 把j从0到n ? 1求和
n?1

d+1

?j

d+1

=
i=0

d +1 i j i

n?1 d

(j + 1)d+1 ? j d+1 =
j=0 j=0 i=0

d +1 i j i

也就是 n
d+1

d

=
i=0

d +1 Si (n) i

d

(j + 1) 把j从0到n ? 1求和
n?1

d+1

?j

d+1

=
i=0

d +1 i j i

n?1 d

(j + 1)d+1 ? j d+1 =
j=0 j=0 i=0

d +1 i j i

也就是 n 即
d+1

d

=
i=0

d +1 Si (n) i
d?1

(d + 1) ? Sd (n) = n

d+1

?
i=0

d +1 Si (n) j

d?1

(d + 1) ? Sd (n) = nd+1 ?
i=0

d +1 Si (n) j

d?1

(d + 1) ? Sd (n) = nd+1 ?
i=0

d +1 Si (n) j

右边显然是一个次数不超过d + 1次的多项式,并且通过这 个式子我们可以递推算出Sd (n)。

d?1

(d + 1) ? Sd (n) = nd+1 ?
i=0

d +1 Si (n) j

右边显然是一个次数不超过d + 1次的多项式,并且通过这 个式子我们可以递推算出Sd (n)。 时间复杂度为O(d 3 + log n)。

3.d ≤ 2000, n ≤ 1010000 , m ≤ 1018 ,m为素数 我们定义伯努利数 x = x ?1 e
∞ n=0

Bn n x n!

3.d ≤ 2000, n ≤ 1010000 , m ≤ 1018 ,m为素数 我们定义伯努利数 x = x ?1 e 定义伯努利多项式
∞ n=0 ∞ n=0

Bn n x n!

βn (t) n x x = x e tx = ( n! e ?1

∞ n=0

Bn n x )( n!

∞ n=0

tn n x ) n!

3.d ≤ 2000, n ≤ 1010000 , m ≤ 1018 ,m为素数 我们定义伯努利数 x = x ?1 e 定义伯努利多项式
∞ n=0 ∞ n=0

Bn n x n!

βn (t) n x x = x e tx = ( n! e ?1
n

∞ n=0

Bn n x )( n!

∞ n=0

tn n x ) n!

也就是 βn (t) =

k=0

n Bn?k t k k

∞ n=0

βn (t + 1) ? βn (t) n xe (t+1)x xe tx x = x ? x n! e ?1 e ?1 = xe tx (e x ? 1) = xe tx = x ex ? 1
∞ n=0

tn n x n!

∞ n=0

βn (t + 1) ? βn (t) n xe (t+1)x xe tx x = x ? x n! e ?1 e ?1 = xe tx (e x ? 1) = xe tx = x ex ? 1
∞ n=0

tn n x n!

观察两边x n+1 的系数,即得 βn+1 (t + 1) ? βn+1 (t) tn = (n + 1)! n!

∞ n=0

βn (t + 1) ? βn (t) n xe (t+1)x xe tx x = x ? x n! e ?1 e ?1 = xe tx (e x ? 1) = xe tx = x ex ? 1
∞ n=0

tn n x n!

观察两边x n+1 的系数,即得 βn+1 (t + 1) ? βn+1 (t) tn = (n + 1)! n! 就是 βn+1 (t + 1) ? βn+1 (t) = (n + 1)t n

∞ n=0

βn (t + 1) ? βn (t) n xe (t+1)x xe tx x = x ? x n! e ?1 e ?1 = xe tx (e x ? 1) = xe tx = x ex ? 1
∞ n=0

tn n x n!

观察两边x n+1 的系数,即得 βn+1 (t + 1) ? βn+1 (t) tn = (n + 1)! n! 就是 βn+1 (t + 1) ? βn+1 (t) = (n + 1)t n 所以 Sd (n) = βd+1 (n) ? βd+1 (0) d +1

经化简可得
m?1

kn =
k=0

1 n+1

n k=0

n+1 Bk mn+1?k k

经化简可得
m?1

kn =
k=0

1 n+1

n k=0

n+1 Bk mn+1?k k

在这个式子中,令m = 1且n = 0,那么就有
n k=0

n+1 1 Bk = 0 ? Bn = ? k n+1

n?1 k=0

n+1 Bk k

经化简可得
m?1

kn =
k=0

1 n+1

n k=0

n+1 Bk mn+1?k k

在这个式子中,令m = 1且n = 0,那么就有
n k=0

n+1 1 Bk = 0 ? Bn = ? k n+1

n?1 k=0

n+1 Bk k

另外证明可以参见顾宇宙大神JZPKIL的题解或《具体数 学》

于是我们可以在O(d 2 )的时间内算出伯努利数,然后算 出Sd (n)时间复杂度为O(d 2 + log n)。

4.d ≤ 200000, n ≤ 1010000 , m ≤ 1018 ,m为素数

4.d ≤ 200000, n ≤ 1010000 , m ≤ 1018 ,m为素数 关注Sd (x)这个多项式本身,我们可以在O(d log d)的时间内 算出Sd (1), Sd (2), . . . , Sd (d + 1)

4.d ≤ 200000, n ≤ 1010000 , m ≤ 1018 ,m为素数 关注Sd (x)这个多项式本身,我们可以在O(d log d)的时间内 算出Sd (1), Sd (2), . . . , Sd (d + 1) 而确定了Sd (1), Sd (2), . . . , Sd (d + 1)也就代表确定了这个多 项式。

4.d ≤ 200000, n ≤ 1010000 , m ≤ 1018 ,m为素数 关注Sd (x)这个多项式本身,我们可以在O(d log d)的时间内 算出Sd (1), Sd (2), . . . , Sd (d + 1) 而确定了Sd (1), Sd (2), . . . , Sd (d + 1)也就代表确定了这个多 项式。 多项式的系数能在O(d 2 )的时间内计算。

4.d ≤ 200000, n ≤ 1010000 , m ≤ 1018 ,m为素数 关注Sd (x)这个多项式本身,我们可以在O(d log d)的时间内 算出Sd (1), Sd (2), . . . , Sd (d + 1) 而确定了Sd (1), Sd (2), . . . , Sd (d + 1)也就代表确定了这个多 项式。 多项式的系数能在O(d 2 )的时间内计算。 我们定义
d

Sd?1 (x) = P(x) =
k=0

x ak k

4.d ≤ 200000, n ≤ 1010000 , m ≤ 1018 ,m为素数 关注Sd (x)这个多项式本身,我们可以在O(d log d)的时间内 算出Sd (1), Sd (2), . . . , Sd (d + 1) 而确定了Sd (1), Sd (2), . . . , Sd (d + 1)也就代表确定了这个多 项式。 多项式的系数能在O(d 2 )的时间内计算。 我们定义
d

Sd?1 (x) = P(x) =
k=0

x ak k

经过二项式反演可得
k

ak =
j=0

(?1)k?j

k P(j) j

k

ak =
j=0

(?1)k?j

k P(j) j

k

ak =
j=0

(?1)k?j

k P(j) j

也就是 ak = k!

k j=0

(?1)k?j P(j) · (k ? j)! j!

k

ak =
j=0

(?1)k?j

k P(j) j

也就是 ak = k!

k j=0

(?1)k?j P(j) · (k ? j)! j!

注意这是一个卷积的形式,我们可以用FFT在O(d log d)的 时间内算出来。

k

ak =
j=0

(?1)k?j

k P(j) j

也就是 ak = k!

k j=0

(?1)k?j P(j) · (k ? j)! j!

注意这是一个卷积的形式,我们可以用FFT在O(d log d)的 时间内算出来。 FFT?

k

ak =
j=0

(?1)k?j

k P(j) j

k

ak =
j=0

(?1)k?j

k P(j) j

那么就有
d

P(n) =
k=0

n ak = k
d

d k=0 d

n k

k

(?1)k?j
j=0

k P(j) j

=
j=0

P(j)
k=j

(?1)k?j

n k

k j

d

(?1)
k=j d

k?j

n k

k j

d

=
k=j

(?1)k?j

n!k! k!(n ? k)!j!(k ? j)!
d

=
k=j

(?1)

k?j

(n ? j)! n! = j!(n ? j)! (n ? k)!(k ? j)! = n j
d?j

(?1)k?j
k=j

n j

n?j k ?j

(?1)k
k=0

n?j k

d

(?1)
k=j d

k?j

n k

k j

d

=
k=j

(?1)k?j

n!k! k!(n ? k)!j!(k ? j)!
d

=
k=j

(?1)

k?j

(n ? j)! n! = j!(n ? j)! (n ? k)!(k ? j)! = n j
d?j

(?1)k?j
k=j

n j

n?j k ?j

(?1)k
k=0

n?j k

k

(?1)i
i=0

n i

=

n n ? + ... = 0 1

n?1 n ? + ... 0 1

=?

n?1 n + +. . . = 1 2

n?1 n n?1 ? +. . . = (?1)k 2 3 k

d

(?1)k?j
k=j

n k

k j

= (?1)d?j

n?j ?1 d ?j

n j

d

(?1)k?j
k=j

n k
d

k j

= (?1)d?j

n?j ?1 d ?j n j

n j

P(n) =
j=0 d

(?1)d?j P(j)

n?j ?1 d ?j

=
j=0

(?1)d?j P(j)
d

(n ? j ? 1)!n! (d ? j)!(n ? d ? 1)!(n ? j)!j! n(n ? 1) . . . (n ? d) (d ? j)!j!(n ? j)

=
j=0

(?1)d?j P(j)

这样我们在知道P(0), P(1), . . . , P(d)的情况下,可以 在O(d)的时间复杂度内算出P(n)

这样我们在知道P(0), P(1), . . . , P(d)的情况下,可以 在O(d)的时间复杂度内算出P(n) 对于本题,Sd (n)的计算是瓶颈,注意到i d 是积性函数,那 么只要算出那些素数的幂次就可以算出所有的i d 的值了。

这样我们在知道P(0), P(1), . . . , P(d)的情况下,可以 在O(d)的时间复杂度内算出P(n) 对于本题,Sd (n)的计算是瓶颈,注意到i d 是积性函数,那 么只要算出那些素数的幂次就可以算出所有的i d 的值了。 由于不超过d的素数是O(d/ log d)个,而快速幂的复杂度 为O(log d),那么时间复杂度就是O(d)

这样我们在知道P(0), P(1), . . . , P(d)的情况下,可以 在O(d)的时间复杂度内算出P(n) 对于本题,Sd (n)的计算是瓶颈,注意到i d 是积性函数,那 么只要算出那些素数的幂次就可以算出所有的i d 的值了。 由于不超过d的素数是O(d/ log d)个,而快速幂的复杂度 为O(log d),那么时间复杂度就是O(d) 我们就在O(d)的时间内把这个问题解决了。

4? .d ≤ 200000, n ≤ 1010000 , m ≤ 1018

4? .d ≤ 200000, n ≤ 1010000 , m ≤ 1018 m不是素数,那么对组合数计算会带来困难。

4? .d ≤ 200000, n ≤ 1010000 , m ≤ 1018 m不是素数,那么对组合数计算会带来困难。
a a a 我们令m = p11 p22 . . . pk k M,其中pi ≤ d + 1。

4? .d ≤ 200000, n ≤ 1010000 , m ≤ 1018 m不是素数,那么对组合数计算会带来困难。
a a a 我们令m = p11 p22 . . . pk k M,其中pi ≤ d + 1。 a a a 我们可以分别求出Sd (n)对p11 , p22 , . . . , pk k , M取模,然后用 中国剩余定理进行合并即可。

4? .d ≤ 200000, n ≤ 1010000 , m ≤ 1018 m不是素数,那么对组合数计算会带来困难。
a a a 我们令m = p11 p22 . . . pk k M,其中pi ≤ d + 1。 a a a 我们可以分别求出Sd (n)对p11 , p22 , . . . , pk k , M取模,然后用 中国剩余定理进行合并即可。

对M取模我们可以根据上述的方法进行处理,因为M没有小 于d的因子,那么(d ? j)!j!和M一定是互质的,而n ? j一定 是n, n ? 1, . . . , n ? d中的某一个,只要约去即可。

接下来要求的是Sd (n)对p a 取模,令n ? 1 = q p a + r ,那么 就有Sd (n) ≡ q Sd (p a ) + Sd (r ) (mod p a ),所以只要考 虑n ≤ p a 时即可。

接下来要求的是Sd (n)对p a 取模,令n ? 1 = q p a + r ,那么 就有Sd (n) ≡ q Sd (p a ) + Sd (r ) (mod p a ),所以只要考 虑n ≤ p a 时即可。 令n ? 1 = qp + r ,那么Sd (n) =
qp?1 d i=0 i

+

n?1 d i=qp i

接下来要求的是Sd (n)对p a 取模,令n ? 1 = q p a + r ,那么 就有Sd (n) ≡ q Sd (p a ) + Sd (r ) (mod p a ),所以只要考 虑n ≤ p a 时即可。 令n ? 1 = qp + r ,那么Sd (n) = 对于
qp?1 d i=0 i

+

n?1 d i=qp i

n?1 d i=qp i 它的个数不超过p,也可通过暴力直接计算。

接下来要求的是Sd (n)对p a 取模,令n ? 1 = q p a + r ,那么 就有Sd (n) ≡ q Sd (p a ) + Sd (r ) (mod p a ),所以只要考 虑n ≤ p a 时即可。 令n ? 1 = qp + r ,那么Sd (n) = 对于
qp?1 d i=0 i

+

n?1 d i=qp i

n?1 d i=qp i 它的个数不超过p,也可通过暴力直接计算。

qp?1

q?1 p?1

q?1 p?1 d

id =
i=0 i=0 j=0

(ip + j)d =
i=0 j=0 k=0

d (ip)k j d?k k

接下来要求的是Sd (n)对p a 取模,令n ? 1 = q p a + r ,那么 就有Sd (n) ≡ q Sd (p a ) + Sd (r ) (mod p a ),所以只要考 虑n ≤ p a 时即可。 令n ? 1 = qp + r ,那么Sd (n) = 对于
qp?1 d i=0 i

+

n?1 d i=qp i

n?1 d i=qp i 它的个数不超过p,也可通过暴力直接计算。

qp?1

q?1 p?1

q?1 p?1 d

id =
i=0 i=0 j=0

(ip + j)d =
i=0 j=0 k=0

d (ip)k j d?k k

由于对p a 取模,那么(ip)k 中如果k ≥ a就可以忽略。

也就是

qp?1

q?1 p?1 a?1

i =
i=0 a?1 i=0 j=0 k=0

d

d (ip)k j d?k k
q?1

=
k=0

d k p k

p?1

j
j=0

d?k i=0

ik

也就是

qp?1

q?1 p?1 a?1

i =
i=0 a?1 i=0 j=0 k=0

d

d (ip)k j d?k k
q?1

=
k=0 p?1 d?k , j=0 j

d k p k

p?1

j
j=0

d?k i=0

ik

q?1 k i=0 i 两个互相独立,可以分开求和。

也就是

qp?1

q?1 p?1 a?1

i =
i=0 a?1 i=0 j=0 k=0

d

d (ip)k j d?k k
q?1

=
k=0

d k p k

p?1

j
j=0

d?k i=0

ik

p?1 d?k , q?1 i k 两个互相独立,可以分开求和。 j=0 j i=0 q?1 k p?1 d?k 可以暴力预处理。 i=0 i 我们可以递归计算, j=0 j

也就是

qp?1

q?1 p?1 a?1

i =
i=0 a?1 i=0 j=0 k=0

d

d (ip)k j d?k k
q?1

=
k=0

d k p k

p?1

j
j=0

d?k i=0

ik

p?1 d?k , q?1 i k 两个互相独立,可以分开求和。 j=0 j i=0 q?1 k p?1 d?k 可以暴力预处理。 i=0 i 我们可以递归计算, j=0 j 2 对于每个p,时间复杂度为O(p logp m log d + log3 m)。 p

FZU A math problem

FZU A math problem

找到一个最小的N,对所有的i从0到k满足N ≡ bi (mod PiCi )

FZU A math problem

找到一个最小的N,对所有的i从0到k满足N ≡ bi (mod PiCi ) M=
ci k i=0 pi

FZU A math problem

找到一个最小的N,对所有的i从0到k满足N ≡ bi (mod PiCi ) M= 求Ans
ci k i=0 pi = N iA i=1

mod M

FZU A math problem

找到一个最小的N,对所有的i从0到k满足N ≡ bi (mod PiCi )
ci k i=0 pi 求Ans = N i A mod M i=1 保证50 ≤ A ≤ 109 , k ≤ 20, 0

M=

≤ bi ≤ 200, N, M ≤ 109

FZU A math problem

找到一个最小的N,对所有的i从0到k满足N ≡ bi (mod PiCi )
ci k i=0 pi 求Ans = N i A mod M i=1 保证50 ≤ A ≤ 109 , k ≤ 20, 0

M=

≤ bi ≤ 200, N, M ≤ 109

Orz AekdyCoin大神

用中国剩余定理计算出N

用中国剩余定理计算出N
C C C 分别求Ans对P0 0 , P1 1 , . . . , Pk k 取模的余数,然后用中国剩 余定理合并即可。

用中国剩余定理计算出N
C C C 分别求Ans对P0 0 , P1 1 , . . . , Pk k 取模的余数,然后用中国剩 余定理合并即可。

因为bi ≤ 200,所以多出的部分可以暴力计算。

用中国剩余定理计算出N
C C C 分别求Ans对P0 0 , P1 1 , . . . , Pk k 取模的余数,然后用中国剩 余定理合并即可。

因为bi ≤ 200,所以多出的部分可以暴力计算。 问题就转化成了
P C ?1 d C i=0 i 对P 取模。

注意d ≥ 50 > log(109 ),那么就有区间内满足P|x都可以忽 略。

注意d ≥ 50 > log(109 ),那么就有区间内满足P|x都可以忽 略。 令p = P C , g 为p的原根。当i取遍0到?(p) ? 1时,g i 取 遍[0, p)中与p互质的数。

注意d ≥ 50 > log(109 ),那么就有区间内满足P|x都可以忽 略。 令p = P C , g 为p的原根。当i取遍0到?(p) ? 1时,g i 取 遍[0, p)中与p互质的数。
p?1 ?(p)?1

i ≡
i=0 i=0

d

g id

(mod p)

注意d ≥ 50 > log(109 ),那么就有区间内满足P|x都可以忽 略。 令p = P C , g 为p的原根。当i取遍0到?(p) ? 1时,g i 取 遍[0, p)中与p互质的数。
p?1 ?(p)?1

i ≡
i=0 i=0

d

g id

(mod p)

这是一个等比数列求和,可以二分计算。

当P = 2且C ≥ 3时,原根并不存在。

当P = 2且C ≥ 3时,原根并不存在。 令Sc =
2c ?1 d i=0 i

当P = 2且C ≥ 3时,原根并不存在。 令Sc =
2c ?1 d i=0 i

当d为奇数时,有k d + (2c ? k)d ≡ 0 (mod 2c ),也就 是Sc ≡ 0 (mod 2c )

当P = 2且C ≥ 3时,原根并不存在。 令Sc =
2c ?1 d i=0 i

当d为奇数时,有k d + (2c ? k)d ≡ 0 (mod 2c ),也就 是Sc ≡ 0 (mod 2c ) 当d为偶数时,有Sc ≡ 2c?1 (mod 2c )

当P = 2且C ≥ 3时,原根并不存在。 令Sc =
2c ?1 d i=0 i

当d为奇数时,有k d + (2c ? k)d ≡ 0 (mod 2c ),也就 是Sc ≡ 0 (mod 2c ) 当d为偶数时,有Sc ≡ 2c?1 (mod 2c ) 当c = 0时Sc = 1,显然成立

当P = 2且C ≥ 3时,原根并不存在。 令Sc =
2c ?1 d i=0 i

当d为奇数时,有k d + (2c ? k)d ≡ 0 (mod 2c ),也就 是Sc ≡ 0 (mod 2c ) 当d为偶数时,有Sc ≡ 2c?1 (mod 2c ) 当c = 0时Sc = 1,显然成立 当c = i时,假设成立

当P = 2且C ≥ 3时,原根并不存在。 令Sc =
2c ?1 d i=0 i

当d为奇数时,有k d + (2c ? k)d ≡ 0 (mod 2c ),也就 是Sc ≡ 0 (mod 2c ) 当d为偶数时,有Sc ≡ 2c?1 (mod 2c ) 当c = 0时Sc = 1,显然成立 当c = i时,假设成立 那么就有当c = i + 1时,k d + (2c ? k)d ≡ 2k d (mod 2c ), 也就是Sc ≡ 2Sc?1 (mod 2c )

当P = 2且C ≥ 3时,原根并不存在。 令Sc =
2c ?1 d i=0 i

当d为奇数时,有k d + (2c ? k)d ≡ 0 (mod 2c ),也就 是Sc ≡ 0 (mod 2c ) 当d为偶数时,有Sc ≡ 2c?1 (mod 2c ) 当c = 0时Sc = 1,显然成立 当c = i时,假设成立 那么就有当c = i + 1时,k d + (2c ? k)d ≡ 2k d (mod 2c ), 也就是Sc ≡ 2Sc?1 (mod 2c ) 因为Sc?1 ≡ 2c?2 (mod 2c?1 ),所以就有Sc ≡ 2c?1 (mod 2c )

tyvj xlkxc

tyvj xlkxc

给定k, a, n, d, p,已知f (x) = 求 n g (a + id) mod p i=0

x k i=1 i , g (x)

=

x i=1 f (x),

tyvj xlkxc

给定k, a, n, d, p,已知f (x) = 求 n g (a + id) mod p i=0

x k i=1 i , g (x)

=

x i=1 f (x),

k ≤ 123, a, n, d ≤ 123456789, p = 1234567891

tyvj xlkxc

给定k, a, n, d, p,已知f (x) = 求 n g (a + id) mod p i=0 p为素数

x k i=1 i , g (x)

=

x i=1 f (x),

k ≤ 123, a, n, d ≤ 123456789, p = 1234567891

tyvj xlkxc

给定k, a, n, d, p,已知f (x) = 求 n g (a + id) mod p i=0 p为素数 Orz XLk大神

x k i=1 i , g (x)

=

x i=1 f (x),

k ≤ 123, a, n, d ≤ 123456789, p = 1234567891

法1

法1
我们可以通过伯努利数在O(k 2 )的时间内预处理,并 在O(k)的时间内算出f (x)的表达式。令
k+1

f (x) =
i=0

ai x i

法1
我们可以通过伯努利数在O(k 2 )的时间内预处理,并 在O(k)的时间内算出f (x)的表达式。令
k+1

f (x) =
i=0

ai x i

那么 g (x) =

x

k+1

k+1

x

ai j i =
j=1 i=0 i=0

ai
j=1

ji

法1
我们可以通过伯努利数在O(k 2 )的时间内预处理,并 在O(k)的时间内算出f (x)的表达式。令
k+1

f (x) =
i=0

ai x i

那么 g (x) =

x

k+1

k+1

x

ai j i =
j=1 i=0 i=0

ai
j=1

ji

由于 x j i 的系数可以在O(k)时间内算出,那么g (k)的表 j=1 达式可以在O(k 2 )时间内算出。

令 g (x) =

k+2

bi x i
i=0

令 g (x) =

k+2

bi x i
i=0

n

n k+2

n k+2

j

g (a+id) =
i=0 i=0 j=0 k+2

bj (a+id) =
i=0 j=0 j n

j

bj
k =0

j k

ak (id)j?k

=
j=0

bj
k =0

j k

ak d j?k
i=0

i j?k

令 g (x) =

k+2

bi x i
i=0

n

n k+2

n k+2

j

g (a+id) =
i=0 i=0 j=0 k+2

bj (a+id) =
i=0 j=0 j n

j

bj
k =0

j k

ak (id)j?k

=
j=0

bj
k =0

j k

ak d j?k
i=0

i j?k

将 n i d 的d相同的项前面的系数并在一起,然后利用伯努 i=0 利数计算,时间复杂度为O(k 2 )。

法2

法2

我们可以算出f (0), f (1), . . . , f (k + 3)的值,然后就可以算 出g (0), g (1), . . . , g (k + 3)的值。

法2

我们可以算出f (0), f (1), . . . , f (k + 3)的值,然后就可以算 出g (0), g (1), . . . , g (k + 3)的值。 由于g 是一个次数为k + 2的多项式,那么我们肯定能 在O(k)算出g (a),也就是能在O(k 2 )的时间复杂度内算 出g (a), g (a + d), g (a + 2d), . . . , g (a + (k + 3)d)。

法2

我们可以算出f (0), f (1), . . . , f (k + 3)的值,然后就可以算 出g (0), g (1), . . . , g (k + 3)的值。 由于g 是一个次数为k + 2的多项式,那么我们肯定能 在O(k)算出g (a),也就是能在O(k 2 )的时间复杂度内算 出g (a), g (a + d), g (a + 2d), . . . , g (a + (k + 3)d)。 由于S(n) = n g (a + id)显然是一个关于n次数为k + 3的 i=0 多项值,我们知道了S(0), S(1), . . . , S(k + 3)的值,那么就 能算出S(n)。

法2

我们可以算出f (0), f (1), . . . , f (k + 3)的值,然后就可以算 出g (0), g (1), . . . , g (k + 3)的值。 由于g 是一个次数为k + 2的多项式,那么我们肯定能 在O(k)算出g (a),也就是能在O(k 2 )的时间复杂度内算 出g (a), g (a + d), g (a + 2d), . . . , g (a + (k + 3)d)。 由于S(n) = n g (a + id)显然是一个关于n次数为k + 3的 i=0 多项值,我们知道了S(0), S(1), . . . , S(k + 3)的值,那么就 能算出S(n)。 时间复杂度还是O(k 2 ),但是你要实现的仅是给定 的f (0), f (1), . . . , f (d),计算出f (n)即可。

Codechef QPOLYSUM

Codechef QPOLYSUM

给定一个次数为d的多项式P(x),给出P(0), P(1), . . . , P(d) modM的值,求 n?1 P(i)Q i mod M。 i=0

Codechef QPOLYSUM

给定一个次数为d的多项式P(x),给出P(0), P(1), . . . , P(d) modM的值,求 n?1 P(i)Q i mod M。 i=0 n ≤ 10100000 , d ≤ 20000, 0 ≤ Q, M ≤ 1018

Codechef QPOLYSUM

给定一个次数为d的多项式P(x),给出P(0), P(1), . . . , P(d) modM的值,求 n?1 P(i)Q i mod M。 i=0 n ≤ 10100000 , d ≤ 20000, 0 ≤ Q, M ≤ 1018 M与2, 3, . . . , d + 14互质

Codechef QPOLYSUM

给定一个次数为d的多项式P(x),给出P(0), P(1), . . . , P(d) modM的值,求 n?1 P(i)Q i mod M。 i=0 n ≤ 10100000 , d ≤ 20000, 0 ≤ Q, M ≤ 1018 M与2, 3, . . . , d + 14互质 官方题解的复杂度为 O(D(K log D + K 2 + log(M 2 D)) + log N · log M),其 中k = log(M 2 d)/ log(231 )

特殊处理Q = 0, Q = 1的情况,Q = 0时答案就是P(0)。

特殊处理Q = 0, Q = 1的情况,Q = 0时答案就是P(0)。 Q = 1时我们可以先算出P(d + 1),令S(n) = n P(i),那 i=0 么我们已经知道S(0), S(1), . . . , S(d + 1),就可以算 出S(n)的值。

特殊处理Q = 0, Q = 1的情况,Q = 0时答案就是P(0)。 Q = 1时我们可以先算出P(d + 1),令S(n) = n P(i),那 i=0 么我们已经知道S(0), S(1), . . . , S(d + 1),就可以算 出S(n)的值。 考虑Q不等于0或1时的情况,令
n?1

G (n) =
i=0

P(i)Q i = Q n F (n) ? F (0)

特殊处理Q = 0, Q = 1的情况,Q = 0时答案就是P(0)。 Q = 1时我们可以先算出P(d + 1),令S(n) = n P(i),那 i=0 么我们已经知道S(0), S(1), . . . , S(d + 1),就可以算 出S(n)的值。 考虑Q不等于0或1时的情况,令
n?1

G (n) =
i=0

P(i)Q i = Q n F (n) ? F (0)

其中F (n)次数为d的一个多项式,这个可以通过数学归纳法 得到。

当d = 0时显然成立。

当d = 0时显然成立。 当d = k时,假设成立。

当d = 0时显然成立。 当d = k时,假设成立。 当d = k + 1时,令Sd (n) =
n?1 i i=0 P(i)Q 。

当d = 0时显然成立。 当d = k时,假设成立。 当d = k + 1时,令Sd (n) = QSd (n) =
n?1 i+1 i=0 P(i)Q n?1 i i=0 P(i)Q 。 n i i=1 P(i ? 1)Q

=

当d = 0时显然成立。 当d = k时,假设成立。 当d = k + 1时,令Sd (n) = QSd (n) = (Q ?1)Sd
n?1 i+1 = i=0 P(i)Q (n) = P(n?1)Q n + n?1 i i=0 P(i)Q 。 n i i=1 P(i ? 1)Q n?1 i i=0 (P(i ?1)?P(i))Q ?P(?1)

当d = 0时显然成立。 当d = k时,假设成立。 当d = k + 1时,令Sd (n) = QSd (n) = (Q ?1)Sd
n?1 i+1 = i=0 P(i)Q (n) = P(n?1)Q n + n?1 i i=0 P(i)Q 。 n i i=1 P(i ? 1)Q n?1 i i=0 (P(i ?1)?P(i))Q ?P(?1)

P(i ? 1) ? P(i)是一个次数为d ? 1的多项式。

当d = 0时显然成立。 当d = k时,假设成立。 当d = k + 1时,令Sd (n) = QSd (n) = (Q ?1)Sd 那么
n?1 i+1 = i=0 P(i)Q (n) = P(n?1)Q n + n?1 i i=0 P(i)Q 。 n i i=1 P(i ? 1)Q n?1 i i=0 (P(i ?1)?P(i))Q ?P(?1)

P(i ? 1) ? P(i)是一个次数为d ? 1的多项式。
n?1 i=0 (P(i

? 1) ? P(i))Q i 一定能被表示成Q n f (x) ? f (0)

当d = 0时显然成立。 当d = k时,假设成立。 当d = k + 1时,令Sd (n) = QSd (n) = (Q ?1)Sd 那么
n?1 i+1 = i=0 P(i)Q (n) = P(n?1)Q n + n?1 i i=0 P(i)Q 。 n i i=1 P(i ? 1)Q n?1 i i=0 (P(i ?1)?P(i))Q ?P(?1)

P(i ? 1) ? P(i)是一个次数为d ? 1的多项式。
n?1 i=0 (P(i

? 1) ? P(i))Q i 一定能被表示成Q n f (x) ? f (0)

那么Sd (n)一定能被表示成Q n F (n) ? c,其 中F (n) = (f (n) + P(n ? 1))/(Q ? 1),c为一个常数。

当d = 0时显然成立。 当d = k时,假设成立。 当d = k + 1时,令Sd (n) = QSd (n) = (Q ?1)Sd 那么
n?1 i+1 = i=0 P(i)Q (n) = P(n?1)Q n + n?1 i i=0 P(i)Q 。 n i i=1 P(i ? 1)Q n?1 i i=0 (P(i ?1)?P(i))Q ?P(?1)

P(i ? 1) ? P(i)是一个次数为d ? 1的多项式。
n?1 i=0 (P(i

? 1) ? P(i))Q i 一定能被表示成Q n f (x) ? f (0)

那么Sd (n)一定能被表示成Q n F (n) ? c,其 中F (n) = (f (n) + P(n ? 1))/(Q ? 1),c为一个常数。 考虑n = 0时,Sd (n) = 0,也就是c = F (0)

当d = 0时显然成立。 当d = k时,假设成立。 当d = k + 1时,令Sd (n) = QSd (n) = (Q ?1)Sd 那么
n?1 i+1 = i=0 P(i)Q (n) = P(n?1)Q n + n?1 i i=0 P(i)Q 。 n i i=1 P(i ? 1)Q n?1 i i=0 (P(i ?1)?P(i))Q ?P(?1)

P(i ? 1) ? P(i)是一个次数为d ? 1的多项式。
n?1 i=0 (P(i

? 1) ? P(i))Q i 一定能被表示成Q n f (x) ? f (0)

那么Sd (n)一定能被表示成Q n F (n) ? c,其 中F (n) = (f (n) + P(n ? 1))/(Q ? 1),c为一个常数。 考虑n = 0时,Sd (n) = 0,也就是c = F (0) F (n)显然是一个次数为d的多项式,Sd (n) = Q n F (n) ? F (0)

G (n) =

n?1 i i=0 P(i)Q

= Q n F (n) ? F (0)

G (n) =

n?1 i i=0 P(i)Q

= Q n F (n) ? F (0)

相减得G (n + 1) ? G (n) = P(n)Q n = Q n+1 F (n + 1) ? Q n F (n)

G (n) = 即

n?1 i i=0 P(i)Q

= Q n F (n) ? F (0)

相减得G (n + 1) ? G (n) = P(n)Q n = Q n+1 F (n + 1) ? Q n F (n) F (n) + P(n) Q

P(n) = QF (n + 1) ? F (n) ? F (n + 1) =

G (n) = 即

n?1 i i=0 P(i)Q

= Q n F (n) ? F (0)

相减得G (n + 1) ? G (n) = P(n)Q n = Q n+1 F (n + 1) ? Q n F (n) F (n) + P(n) Q

P(n) = QF (n + 1) ? F (n) ? F (n + 1) =

我们并不知道F (0)的值,但可以通过递推 把F (1), F (2), . . . , F (d), F (d + 1)表示成关于F (0)的一次函 数。

G (n) = 即

n?1 i i=0 P(i)Q

= Q n F (n) ? F (0)

相减得G (n + 1) ? G (n) = P(n)Q n = Q n+1 F (n + 1) ? Q n F (n) F (n) + P(n) Q

P(n) = QF (n + 1) ? F (n) ? F (n + 1) =

我们并不知道F (0)的值,但可以通过递推 把F (1), F (2), . . . , F (d), F (d + 1)表示成关于F (0)的一次函 数。 由于F (x)是一个次数为d的多项值,那么就满足
d+1

(?1)i
i=0

d +1 F (i) = 0 i

G (n) = 即

n?1 i i=0 P(i)Q

= Q n F (n) ? F (0)

相减得G (n + 1) ? G (n) = P(n)Q n = Q n+1 F (n + 1) ? Q n F (n) F (n) + P(n) Q

P(n) = QF (n + 1) ? F (n) ? F (n + 1) =

我们并不知道F (0)的值,但可以通过递推 把F (1), F (2), . . . , F (d), F (d + 1)表示成关于F (0)的一次函 数。 由于F (x)是一个次数为d的多项值,那么就满足
d+1

(?1)i
i=0

d +1 F (i) = 0 i

这就是个关于F (0)的一次方程,我们可以解出F (0)的值。

注意到这里在递推和解方程中涉及了除法运算,但在模M的 条件下不一定有逆元。

注意到这里在递推和解方程中涉及了除法运算,但在模M的 条件下不一定有逆元。 递推中涉及到除Q。

注意到这里在递推和解方程中涉及了除法运算,但在模M的 条件下不一定有逆元。 递推中涉及到除Q。 F (i)中F (0)的系数为Q ?i ,那么最终方程中F (0)的系数就为
d+1

(?1)i
i=0

d +1 Q ?i = (1 ? Q ?1 )d+1 i

注意到这里在递推和解方程中涉及了除法运算,但在模M的 条件下不一定有逆元。 递推中涉及到除Q。 F (i)中F (0)的系数为Q ?i ,那么最终方程中F (0)的系数就为
d+1

(?1)i
i=0

d +1 Q ?i = (1 ? Q ?1 )d+1 i

那么在解方程中涉及到(Q ? 1)的逆元。

令M = m1 m2 m3 ,存在u, v 使得(m2 m3 , Q) = 1, m1 |Q u , (m1 m3 , Q ? 1) = 1, m2 |(Q ? 1)v ,u, v 是满足条件的最小的 值。

令M = m1 m2 m3 ,存在u, v 使得(m2 m3 , Q) = 1, m1 |Q u , (m1 m3 , Q ? 1) = 1, m2 |(Q ? 1)v ,u, v 是满足条件的最小的 值。 可以分别算出模m1 , m2 , m3 的余数,然后用中国剩余定理合 并。

令M = m1 m2 m3 ,存在u, v 使得(m2 m3 , Q) = 1, m1 |Q u , (m1 m3 , Q ? 1) = 1, m2 |(Q ? 1)v ,u, v 是满足条件的最小的 值。 可以分别算出模m1 , m2 , m3 的余数,然后用中国剩余定理合 并。 对m3 取模可以用上述的方法解决

令M = m1 m2 m3 ,存在u, v 使得(m2 m3 , Q) = 1, m1 |Q u , (m1 m3 , Q ? 1) = 1, m2 |(Q ? 1)v ,u, v 是满足条件的最小的 值。 可以分别算出模m1 , m2 , m3 的余数,然后用中国剩余定理合 并。 对m3 取模可以用上述的方法解决 由于m1 |Q u ,当i ≥ u时,P(i)Q i 对Q u 取模为0,可以忽略。

a a a 令m1 = p11 p22 . . . pk k

a a a 令m1 = p11 p22 . . . pk k

又因为m1 |Q u , m1 Q u?1 ,这样就有u ≤ max{a1 , a2 , . . . , ak }

a a a 令m1 = p11 p22 . . . pk k

又因为m1 |Q u , m1 Q u?1 ,这样就有u ≤ max{a1 , a2 , . . . , ak } 又因为M和2, 3, . . . , d + 14的数互质,那么M最小的可能素 因子是17。

a a a 令m1 = p11 p22 . . . pk k

又因为m1 |Q u , m1 Q u?1 ,这样就有u ≤ max{a1 , a2 , . . . , ak } 又因为M和2, 3, . . . , d + 14的数互质,那么M最小的可能素 因子是17。 又有1715 > 1018 ,那么就有ai ≤ 14,也就是u ≤ 14。

a a a 令m1 = p11 p22 . . . pk k

又因为m1 |Q u , m1 Q u?1 ,这样就有u ≤ max{a1 , a2 , . . . , ak } 又因为M和2, 3, . . . , d + 14的数互质,那么M最小的可能素 因子是17。 又有1715 > 1018 ,那么就有ai ≤ 14,也就是u ≤ 14。 同理的v ≤ 14,即M和2, 3, . . . , d + v 互质。

对m2 取模,有
i

P(i)Q i = P(i)((Q ? 1) + 1)i = P(i)
j=0

i (Q ? 1)j j

对m2 取模,有
i

P(i)Q i = P(i)((Q ? 1) + 1)i = P(i)
j=0

i (Q ? 1)j j

当j ≥ v 时,(Q ? 1)j 对(Q ? 1)v 取模后值为0,可以忽略。

对m2 取模,有
i

P(i)Q i = P(i)((Q ? 1) + 1)i = P(i)
j=0

i (Q ? 1)j j

当j ≥ v 时,(Q ? 1)j 对(Q ? 1)v 取模后值为0,可以忽略。
n?1 v ?1 n?1

P(i)Q =
i=0 j=0

i

(Q ? 1)

j i=0

P(i)

i j

对m2 取模,有
i

P(i)Q i = P(i)((Q ? 1) + 1)i = P(i)
j=0

i (Q ? 1)j j

当j ≥ v 时,(Q ? 1)j 对(Q ? 1)v 取模后值为0,可以忽略。
n?1 v ?1 n?1

P(i)Q =
i=0 i j j=0

i

(Q ? 1)

j i=0 i j

P(i)

i j

显然是关于i的多项式,那么P(i) 过d + v ? 1的多项式。

是一个次数不超

对m2 取模,有
i

P(i)Q i = P(i)((Q ? 1) + 1)i = P(i)
j=0

i (Q ? 1)j j

当j ≥ v 时,(Q ? 1)j 对(Q ? 1)v 取模后值为0,可以忽略。
n?1 v ?1 n?1

P(i)Q =
i=0 i j j=0

i

(Q ? 1)

j i=0 i j

P(i)

i j

显然是关于i的多项式,那么P(i) 过d + v ? 1的多项式。 也就是说明 多项式。

是一个次数不超 + v的

n?1 i i=0 P(i)Q 是一个关于n的次数不超过d

令s(n) = 式。

n?1 i i=0 P(i)Q

mod m2 ,s(n)是一个关于n的多项

令s(n) = 式。

n?1 i i=0 P(i)Q

mod m2 ,s(n)是一个关于n的多项

我们可以算出s(0), s(1), . . . , s(d + v )

令s(n) = 式。

n?1 i i=0 P(i)Q

mod m2 ,s(n)是一个关于n的多项

我们可以算出s(0), s(1), . . . , s(d + v ) 因为m2 和2, 3, . . . , d + v 互质,那么我们就可以算出s(n)

令s(n) = 式。

n?1 i i=0 P(i)Q

mod m2 ,s(n)是一个关于n的多项

我们可以算出s(0), s(1), . . . , s(d + v ) 因为m2 和2, 3, . . . , d + v 互质,那么我们就可以算出s(n) 时间复杂度为O(d + log n),这种做法效率高,代码简单。

感谢长郡中学罗雨屏同学对我的帮助

感谢长郡中学罗雨屏同学对我的帮助 谢谢大家的倾听

感谢长郡中学罗雨屏同学对我的帮助 谢谢大家的倾听 欢迎交流和指出错误


相关文章:
更多相关标签: