容易想到暴力dp,f[i][j]表示到第i个位置,且i位置上填的是j的方案数。
虽然N非常大,但是如果我们考虑按\(\frac{n}{k}\)的值分块,那么就只有根号级别的数量
\(f[i][j]\)表示在到第i个位置,且第i个位置选了第j个块中的数的方案数,那么所有能转移到第j个块的就是tot-j+1个块以及之前的,因为对于两个数x,y,如果x/k=y/k,那么能够转移到这两个数的状态集合是相同的,反过来想一个块能够转移到的状态时相同的。因此他们是两两对应的,第一个块一定对应最后一个块,第二个块一定与倒数第二个对应,以此类推。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#include<set>
#include<unordered_map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
//typedef __int128 i128;
const int N=1e6+5;
const int S=1e5+5;
const int inf=1<<30;
const ll mo=1e9+7;
ll n,k,f[105][S],block[S],g[N],tot,l[N],t[N];
int main()
{
// freopen("data.in","r",stdin);
scanf("%lld %lld",&n,&k);
for (ll i=1,j;i<=n;i=j+1) {
j=n/(n/i);
block[++tot]=n/i;
l[tot]=(j-i+1);
}
fo(i,1,tot) f[1][i]=l[i];
fo(i,2,k) {
fo(j,1,tot) t[j]=(t[j-1]+f[i-1][j])%mo;
fo(j,1,tot) {
f[i][j]=(f[i][j]+ t[tot-j+1]*l[j]%mo)%mo;
}
}
ll ans=0;
fo(i,1,tot) ans=(ans+f[k][i])%mo;
printf("%lld",ans);
return 0;
}
标签:typedef,const,int,个块,Products,abc132F,Small,include,define
From: https://www.cnblogs.com/ganking/p/17966954