[HNOI2013]数列
题目
思路
组合数学不诚，欺我老无力！
用生成函数推导一下，可以发现答案就是
∑
j
=
0
k
−
1
(
−
1
)
j
(
k
−
1
j
)
(
n
−
m
j
k
)
\sum_{j=0}^{k-1}(-1)^j{k-1\choose j}{n-mj\choose k}
j=0∑k−1(−1)j(jk−1)(kn−mj)
没错，这个式子看上去无比简洁。然而接下来该怎么办呢？可以 “合理” 联想一下：
∑
j
=
0
k
−
1
(
−
1
)
j
(
k
−
1
j
)
(
n
−
m
j
k
−
2
)
\sum_{j=0}^{k-1}(-1)^j{k-1\choose j}{n-mj\choose k-2}
∑j=0k−1(−1)j(jk−1)(k−2n−mj) 和它 几乎完全相同，而这个式子的组合意义是，
(
k
−
1
)
(k-1)
(k−1) 个变量，每个变量都是
[
1
,
m
]
[1,m]
[1,m] 中正整数，和为
n
n
n 的方案数。这东西难道可以化简么？
虽然看到限制条件
m
(
k
−
1
)
<
n
m(k{\rm-}1)<n
m(k−1)<n，觉得有些怪异，但终究没有想到它有什么作用。
所以我感到非常疑惑了。我不知道该怎么办了。我只好看题解：直接考虑差分数组
⟨
d
1
,
d
2
,
…
,
d
k
−
1
⟩
\langle d_1,d_2,\dots,d_{k-1}\rangle
⟨d1,d2,…,dk−1⟩ 的话，贡献总是
n
−
∑
d
i
n-\sum d_i
n−∑di，由于每个
d
i
d_i
di 是相同的，直接分别计算贡献就可以了。
所以答案就是
n
m
k
−
1
−
m
(
m
+
1
)
2
⋅
k
m
k
−
2
nm^{k-1}-\frac{m(m+1)}{2}\cdot km^{k-2}
nmk−1−2m(m+1)⋅kmk−2，时间复杂度
O
(
log
k
)
\mathcal O(\log k)
O(logk) 。
我仍然不知道为什么，两个几乎一样的式子，得到的式子却全然不同。我想，最难的题应该是：直接给出开头的数学式，然后让你求解。
代码
#include <cstdio> // ashamed of Queen of Rock Band
#include <iostream> // I'M ILL, INSANE and DESPERATE
#include <algorithm> // inside of Sister, only sister
#include <cstring> // inside of Principal, only principal
#include <cctype> // inside of me, what do you see
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
int a = 0, c = getchar(), f = 1;
for(; !isdigit(c); c=getchar())
if(c == '-') f = -f;
for(; isdigit(c); c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
void writeint(unsigned x){
if(x > 9) writeint(x/10);
putchar(char((x%10)^48));
}
int qkpow(llong b,int q,int MOD){
long long a = 1;
for(; q; q>>=1,b=b*b%MOD)
if(q&1) a = a*b%MOD;
return int(a);
}
int main(){
llong n; scanf("%lld",&n);
int k = readint()-1;
int m = readint(), MOD = readint();
llong ans = (llong(m+1)*m>>1)%MOD;
ans = llong(k)*qkpow(m,k-1,MOD)%MOD*ans%MOD;
ans = (n%MOD*qkpow(m,k,MOD)+MOD-ans)%MOD;
printf("%d\n",int(ans));
return 0;
}