題面翻譯
從序列 \(\{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<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cmath>
namespace 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];
template<class T>inline 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;}
}
template<class T>inline 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 1000000
const int mod=1e9+7;
#define P(A) A=-~A
#define fione(i,a,b) for(register int i=a;i<=b;P(i))
#define fdone(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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/552986.html
標籤：其他
上一篇：小白如何理解軟體自動化介面測驗
下一篇：返回列表