题面翻译
从序列 \(\{a_1,\ a_2,\ ..\ ,\ a_n\}\) 中选出非空子序列 \(\{b_1,\ b_2,\ ..\ ,\ b_k\}\)，一个子序列合法需要满足 \(\forall\ i \in [1,\ k],\ i\ |\ b_i\)。求有多少互不相等的合法子序列，答案对 \(10^9 + 7\) 取模。
序列 \(\{1,\ 1\}\) 有 \(2\) 种选法得到子序列 \(\{1\}\)，但 \(1\) 的来源不同，认为这两个子序列不相等。
做法
看到题目就可以联想到动态规划状态转移方程式：
\[f_{i,j}=\begin{cases}f_{i-1,j} \\f_{i-1,j}+f_{i-1,j-1}&j\mid a_i\end{cases}\]
显然，数据范围过不去。无论从空间还是时间上都超了。
优化：
空间优化：滚动数组可以把第一维优化了，因为第一维只与上一次的状态有关系。
时间优化：只有满足 \(j\) 是 \(a_i\) 的因数时，状态才有效，所以对于每一个 \(a_i\) ，提前枚举它的因数即可，但状态不能互相影响，所以要排序。
代码
#include#include#include#include#include#includenamespace FastIo{ static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw; #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++ inline void pc(const char &ch){ if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw; *pw++=ch;} #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw struct QIO{ char ch; int st[40]; templateinline void read(T &x){ x=0,ch=gc; while(!isdigit(ch))ch=gc; while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}}templateinline void write(T a){do{st[++st[0]]=a%10;a/=10;}while(a);while(st[0])pc(st[st[0]--]^48);}}qrw;}using namespace FastIo;#define NUMBER1 1000000const int mod=1e9+7;#define P(A) A=-~A#define fione(i,a,b) for(register int i=a;i=b;--i)int a[NUMBER1+5],f[NUMBER1+5],num[NUMBER1+5],len;signed main(){int n,ans(0),k;qrw.read(n);fione(i,1,n)qrw.read(a[i]);f[0]=1;fione(i,1,n){len=0,k=sqrt(a[i]);for(register int j(1);j<=k;P(j)){// 提取因数if(!(a[i]%j)){num[++len]=j;if(j*j!=a[i])num[++len]=a[i]/j;}}std::sort(num+1,num+len+1);fdone(j,len,1)f[num[j]]=(f[num[j]]+f[num[j]-1])%mod;//状态转移}fione(i,1,n)ans=(ans+f[i])%mod;qrw.write(ans);fsh; exit(0); return 0;}