JZOJ 4286 Flower

注意到 ln 的增长率很慢，并且有下取整，所以直接对 ⌊Aln(n+B)+C⌋ 分个段做……（

首先解决一个简单的不等式问题：如何求每一段的端点？
设这一段为 [l,r]，其中 l 已知，并令 W=⌊Aln(l+B)+C⌋。
那么 r 是最大的满足 ⌊Aln(n+B)+C⌋=W 的整数，换句话说可以看作最大的满足 ⌊Aln(n+B)+C⌋≤W 的整数。
即 Aln(n+B)+C<W+1。
即 n<expW−C+1A−B。
即 n=⌈expW−C+1A−B⌉−1。

考虑一个朴素的背包 DP：fi,j=fi−1,j+W(n)fi−1,j−1。
分了段之后，可知其相当于 fi,j=fi−1,j+Wnfi−1,j−1。
可证此时 fi.j 实际上是一个关于 i 的 2j 次多项式，于是拉格朗日插值即可（
复杂度 O(k3logn)（众所周知 A,B,C 都是常数）。

代码：

#include <cmath>
#include <cstdio>
#include <algorithm>
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]);
}