直接构造生成函数然后乘起来f(x)=∏i=1n(1+x+x2+...+xtimei)f(x)=\prod_{i=1}^n(1+x+x^2+...+x^{time_i})f(x)=∏i=1n(1+x+x2+...+xtimei)然后求出系数即可。
由于模数是1e61e61e6无法nttnttntt,考虑到数据很小可以直接用dpdpdp来转移(分组背包) 代码:#include#include #include #define ri register intusing namespace std;const int mod=1e6;#define add(a,b) ((a)+(b)>=mod?(a)+(b)-mod:(a)+(b))inline int read(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans;}int ans=0,T,a,L,R,cnt[1005],f[100005];int main(){ T=read(),a=read(),L=read(),R=read(),f[0]=1; for(ri i=1;i<=a;++i)++cnt[read()]; for(ri i=1;i<=T;++i)for(ri k=R;~k;--k)for(ri j=min(cnt[i],k);j;--j)f[k]=add(f[k-j],f[k]); for(ri i=L;i<=R;++i)ans=add(ans,f[i]); cout<