青青草原的表彰大会「NOIP多校联考 2019」

题意

给定n，k。求满足条件的数列个数：

1. 长度为k。

2. 每一项均为前一项的倍数。

3. 每一项都为[1,n]上的整数。

答案对1000000007取模。

---

思路

有一个朴素的DP：\(f[i][j]\)表示长度为j结尾为i的个数，这个转移是显然的。

那么所求答案为\(\sum (\sum f[i][j])*C^{i-1}_{k-1}\)

注意朴素算法跑不过，需要用费马小定理优化C的计算。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

    template<typename T>inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }

    template<typename T>inline void write (T x) {
        if (x<0) putchar('-'),x*=-1;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Project {
    #define int long long

    const int N=1000001;
    const int MOD=1000000007;

    int n,k,ans;
    int fact[N],f[24][N],cnt[24];

    int ksm (int base,int power) {
        int res=1;
        while (power) {
            if (power&1) res=(res*base)%MOD;
            base=(base*base)%MOD,power>>=1;
        }
        return res;
    }
    inline int C (int n,int m) {
        return (fact[n]%MOD*ksm(fact[m],MOD-2)%MOD*ksm(fact[n-m],MOD-2)%MOD)%MOD;
    }

    inline void MAIN () {
        read(n),read(k);
        fact[0]=1;
        for (register int i=1; i<=k; ++i) {
            fact[i]=(fact[i-1]*i)%MOD;
        }
        for (register int i=1; i<=n; ++i) f[1][i]=1;
        for (register int i=2; i<=23; ++i) {
            for (register int j=1; j<=n; ++j) {
                for (register int k=j+j; k<=n; k+=j) {
                    f[i][k]=(f[i][k]+f[i-1][j])%MOD;
                }
            }
        }
        for (register int i=1; i<=23; ++i) {
            for (register int j=1; j<=n; ++j) {
                cnt[i]=(cnt[i]+f[i][j])%MOD;
            }
        }
        for (register int i=1; i<=k&&i<=23; ++i) {
            ans=(ans+cnt[i]*C(k-1,i-1)%MOD)%MOD;
        }
        write(ans);
    }

    #undef int
}

int main () {
//  freopen(".in","r",stdin);
//  freopen("1.out","w",stdout);
    Project::MAIN();
}