抠了两天的题,必须单独开一篇博客
Y Mashmokh and ACM
题意:序列a1, a2, …, an,如果满足ai%ai-1 == 0 ( 2 <= i <= n ),就是好序列。给定n和k,n表示1~n的数,求长度为k的好序列的个数,答案对1e9+7取模。
由数1~n和长度k,联想到状态为以数j结尾,长度为i,构建二维数组dp[i][j]来表示,状态的值为以1~j,最大结尾数字为j,长度为i(以i个数字构成)的好序列个数(错误的状态值,正确的在后面)
第一次尝试,没大有思路,画了一个图来帮助理解:
列表示以哪个数字结尾,行表示由几个数字构成,每格表示结尾数字之前的所有可能组合
没看出什么规律来,第二次尝试,把每一格的数单独列出来找规律
依然是没有什么规律,这种方法行不通,想了好久也没什么新思路,去看了一些其他人的题解,都说是水题,为啥我抠了这么久都没抠出来,自己好菜哟。结合其他人的思路,在我原图的基础上做了一下改进(忽略掉我的丑字)
我们只用到涂蓝色的数,铅笔忽略。蓝色的表示比前一列多的种类,蓝色末位描黑的数表示在已经构建好的位数(没描黑)基础上,加上这一位数。举个例子:比如3行4列的格,蓝色的那些数是由2行1列,2行2列,2行4列的蓝色数在末尾+4构建成的,选取1列2列4列是因为其能被4整除,符合题意。所以状态的值应为以j结尾(结尾数字必须为j),由i个数构成的方案数
这样就好构建动态转移方程了:
d[i+1][k]=(d[i+1][k]+d[i][j])%mod
k用来表示j的倍数
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int mod=1e9+7;
int d[2005][2005];
int main()
{
int n,m,i,j,k;
while(cin>>n>>m)
{
memset(d,0,sizeof(d));
d[0][1]=1;
for(i=0; i<=m; i++)
{
for(j=1; j<=n; j++)
{
for(k=j; k<=n; k+=j)
{
d[i+1][k]=(d[i+1][k]+d[i][j])%mod;
}
}
}
int ans=0;
for(i=1; i<=n; i++)
{
ans=(ans+d[m][i])%mod;
}
cout<<ans<<endl;
}
return 0;
}
附两张图
啥时候我也能轻轻松松写出正确代码,然后在做题总结的开头,自信满满的写上两个大大的字—水题🤔