考虑$i$之后（不包括$i$）的所有面额，必然都整除$prod_{t=1}^{i}a_{i}$，因此对于$i$以及$i$之前的金币所取的面额总和要与$m$关于$prod_{t=1}^{i}a_{i}$同余，即其一定可以被表示为$kprod_{t=1}^{i}a_{i}+m mod prod_{t=1}^{i}a_{i}$（其中$kin N$）
对于暴力的背包，即用$f_{i,j}$表示前$i$种金币面额和为$j$的方案数，但利用$j=kprod_{t=1}^{i}a_{i}+m mod prod_{t=1}^{i}a_{i}$，不妨将$k$作为下标，即令$f'_{i,k}$表示前$i$种金币面额和为$kprod_{t=1}^{i}a_{i}+m mod prod_{t=1}^{i}a_{i}$的方案数
对于转移方程，枚举第$i$种金币的数量，即有$f'_{i,k}=sum_{j=0}^{b_{i}}f'_{i-1,ka_{i}-j+c}$
（其中$c=frac{m mod prod_{t=1}^{i}a_{t}-m mod prod_{t=1}^{i-1}a_{t}}{prod_{t=1}^{i-1}a_{t}}$，显然为整数）
关于这个转移，用前缀和优化即可做到$o(1)$，因此复杂度即状态数
下面，考虑$i$时的状态数（即$k$的范围），为$lfloorfrac{sum_{j=1}^{i}b_{j}prod_{t=1}^{j-1}a_{t}}{prod_{t=1}^{i}a_{t}} floor$
接下来，不妨将下取整去掉，并对所有$i$累加，总状态数即$sum_{i=1}^{n}frac{sum_{j=1}^{i}b_{j}prod_{t=1}^{j-1}a_{t}}{prod_{t=1}^{i}a_{t}}$
调换$i$和$j$的枚举顺序，即$sum_{j=1}^{n-1}b_{j}sum_{i=j}^{n}frac{1}{prod_{t=j}^{i}a_{t}}$
关于后者，分类讨论：
如果不存在$a_{i}=1$，即至多为$1+frac{1}{2}+frac{1}{4}+...le 2$，即为$o(1)$
对于$a_{i}=1$，记$K$为连续最多的1，相当于每一项项至多重复$K$次，总和即为$o(K)$
综上，总状态数（也即复杂度）为$o(Ksum_{i=1}^{n}b_{i})$，由于$Kle 20$，可以通过
还有一个高精度的问题，唯一需要高精度计算的即每一项中的$c$，显然这个式子计算复杂度过高
关于这个式子，感性理解一下，也即等于$lfloorfrac{m}{prod_{t=1}^{i-1}a_{t}} floor mod a_{i}$，且由于从前往后计算，每一次只需要将$m$对$a_{i}$下取整并得到余数即可，复杂度为$o(nlog m)$
注意到当$prod_{i=1}^{n}a_{i}ge m$时除法复杂度变为$o(1)$，且只需要$o(log m)$个非1的数即可，而当$a_{i}=1$时显然可以直接得到结果，因此复杂度为$o(log^{2}m)$，压位可以通过
总复杂度为$o(log^{2}m+Ksum_{i=1}^{n}b_{i})$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 300005 4 #define M 10005 5 #define ll long long 6 #define mod 1000000007 7 #define base 1000000000 8 int n,a[N],b[N],f[2][N]; 9 char s[M]; 10 struct num{ 11 int len,a[M]; 12 void read(){ 13 scanf("%s",s); 14 int l=strlen(s),ss=base; 15 for(int i=l-1;i>=0;i--){ 16 if (ss==base){ 17 len++; 18 ss=1; 19 } 20 a[len]+=ss*(s[i]-'0'); 21 ss*=10; 22 } 23 } 24 int div(int x){ 25 int s=0; 26 for(int i=len;i;i--){ 27 ll ss=1LL*s*base+a[i]; 28 a[i]=ss/x; 29 s=ss%x; 30 } 31 if ((len)&&(!a[len]))len--; 32 return s; 33 } 34 }m; 35 int main(){ 36 scanf("%d",&n); 37 for(int i=1;i<n;i++)scanf("%d",&a[i]); 38 for(int i=1;i<=n;i++)scanf("%d",&b[i]); 39 m.read(); 40 int lst=0; 41 f[0][0]=1; 42 for(int i=1;i<=n;i++){ 43 int p=(i&1),c=0; 44 if (i==n){ 45 if (m.len>1)c=base; 46 else c=m.a[1]; 47 } 48 else{ 49 if (a[i]>1)c=m.div(a[i]); 50 } 51 for(int j=1;j<=lst;j++)f[p^1][j]=(f[p^1][j]+f[p^1][j-1])%mod; 52 if (i==n){ 53 int l=max(c-b[i],0),r=min(c,lst); 54 if (l>r)printf("0"); 55 else{ 56 if (!l)printf("%d",f[p^1][r]); 57 else printf("%d",(f[p^1][r]-f[p^1][l-1]+mod)%mod); 58 } 59 continue; 60 } 61 for(int j=0;j*a[i]+c-b[i]<=lst;j++){ 62 int l=max(j*a[i]+c-b[i],0),r=min(j*a[i]+c,lst); 63 if (!l)f[p][j]=f[p^1][r]; 64 else f[p][j]=(f[p^1][r]-f[p^1][l-1]+mod)%mod; 65 } 66 if (lst+b[i]-c<0){ 67 printf("0"); 68 return 0; 69 } 70 lst=(lst+b[i]-c)/a[i]; 71 } 72 }