网易面试

建dp[i][j]以长度i结尾为j的方案数

转自//https://blog.csdn.net/u010045971/article/details/77188110
//长度为i,以j结尾
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<bitset>
#include<time.h>
using namespace std;
#define ll long long
const int maxn=1e5+7;
const int mod=1e9+7;
int dp[15][maxn];
int ans;
int n,k;
int main()
{
cin>>n>>k;
dp[0][1]=1;
for(int i=1;i<=n;i++)
{
int sum=0;
for(int j=1;j<=k;j++)
{
sum=(sum+dp[i-1][j])%mod;
}
for(int j=1;j<=k;j++)
{
int sum2=0;
for(int t=j+j;t<=k;t+=j)
{
sum2=(sum2+dp[i-1][t])%mod;
}
dp[i][j]=(sum-sum2+mod)%mod;
}
}
ans=0;
for(int i=1;i<=k;i++)
{
ans=(ans+dp[n][i])%mod;
}
cout<<ans<<endl;
return 0;
}