注意到 \(\ln\) 的增长率很慢，并且有下取整，所以直接对 \(\lfloor A\ln(n + B) + C\rfloor\) 分个段做……（
首先解决一个简单的不等式问题：如何求每一段的端点？
设这一段为 \([l,r]\)，其中 \(l\) 已知，并令 \(W = \lfloor A\ln(l + B) + C\rfloor\)。
那么 \(r\) 是最大的满足 \(\lfloor A\ln(n + B) + C\rfloor = W\) 的整数，换句话说可以看作最大的满足 \(\lfloor A\ln(n + B) + C\rfloor \le W\) 的整数。
即 \(A\ln(n + B) + C < W + 1\)。
即 \(n < \exp \frac{W - C + 1}A - B\)。
即 \(n = \lceil\exp \frac{W - C + 1}A - B\rceil - 1\)。
考虑一个朴素的背包 DP：\(f_{i,j} = f_{i-1,j} + W(n)f_{i-1,j-1}\)。
分了段之后，可知其相当于 \(f_{i,j} = f_{i-1,j} + Wnf_{i-1,j-1}\)。
可证此时 \(f_{i.j}\) 实际上是一个关于 \(i\) 的 \(2j\) 次多项式，于是拉格朗日插值即可（
复杂度 \(O(k^3 \log n)\)（众所周知 \(A,B,C\) 都是常数）。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;
const int K = 100;
long long n;
int k,a,b,c,mod,inv;
int f[(K << 1) + 5][K + 5];
int ans;
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int main()
{
freopen("flower.in","r",stdin),freopen("flower.out","w",stdout);
scanf("%lld%d%d%d%d%d",&n,&k,&a,&b,&c,&mod),inv = (mod + 1) >> 1;
f[0][0] = 1;
for(register long long l = 1,r;l <= n;l = r + 1)
{
int v = a * log(l + b) + c;
r = a ? min(n,(long long)(ceil(exp((double)(v + 1 - c) / a) - b) - 1)) : n;
for(register int i = 1;i <= (k << 1);++i)
{
f[i][0] = 1;
for(register int j = 1;j <= k;++j)
f[i][j] = (f[i - 1][j] + (l + i - 1) * v % mod * f[i - 1][j - 1]) % mod;
}
f[(k << 1) + 1][0] = 1;
if(r - l + 1 <= (k << 1))
{
for(register int i = 1;i <= k;++i)
f[0][i] = f[r - l + 1][i];
continue;
}
int x = (r - l + 1) % mod;
for(register int i = 1;i <= k;++i)
{
f[(k << 1) + 1][i] = 0;
for(register int j = 0,p1,p2;j <= (i << 1);++j)
{
p1 = p2 = 1;
for(register int l = 0;l <= (i << 1) && p1;++l)
(j ^ l) && (p1 = (long long)p1 * (x - l + mod) % mod,p2 = (long long)p2 * (j - l + mod) % mod);
f[(k << 1) + 1][i] = (f[(k << 1) + 1][i] + (long long)f[j][i] * p1 % mod * fpow(p2,mod - 2)) % mod;
}
}
for(register int i = 1;i <= k;++i)
f[0][i] = f[(k << 1) + 1][i];
}
printf("%d\n",f[0][k]);
}