[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries
时间限制:2000MS 内存限制:262144KB
难度:5.2
给定一个长度为 n 的非负整数序列 a 和一个正整数 m 。
现在有 q 组询问,每组询问给定两个正整数 l, r ,每次可以选择满足 l \leq i \leq r 的若干个 a_i (也可以一个都不选),使得这些 a_i 的和是 m 的非负整数倍,并输出满足条件的选择方案数对 10^9+7 取模后的余数。
第一行为两个正整数 n 和 m 。
第二行为序列 a ,共 n 个元素,用一个空格隔开。
第三行为询问数 q 。
接下来的 q 行,每一行都有两个正整数,分别为 l 和 r 。
共 q 行。
第 i 行为第 i 组询问的答案。
对于第一组询问 l=1, r=2 ,有 不选、选择 5, 1 ,共 2 种情况。
对于第二组询问 l=1, r=3 ,有 不选、选择 5, 1 、选择 5, 1, 3 、选择 3 ,共 4 种情况。
对于第三组询问 l=1, r=4 ,有 不选、选择 5, 1 、选择 5, 1, 3 、选择 3 、选择 1, 2 、选择 1, 3, 2 ,共 6 种情况。
对于第四组询问 l=2, r=4 ,有 不选、选择 3 、选择 1, 2 、选择 1, 3, 2 ,共 4 种情况。
对于 10\% 的数据,有 1 \leq n, q \leq 10 。
对于 40\% 的数据,有 1 \leq n, q \leq 1000 。
对于 100\% 的数据,有 1 \leq n, q \leq 2 \times 10^5,1 \leq m \leq 20,0 \leq a_i \leq 10^9 。
保证每组询问的 l, r 满足 1 \leq l \leq r \leq n 。
YZOJ P4199
Source: [2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest] J. Subsequence Sum Queries
(注:以下的取模操作均在非负整数意义下。)
最暴力的做法就是对于每一个询问的区间暴力做一遍背包计数,容量就变成 \bmod m 的余数 0 ~ (m-1) 了。转移就是 \(f_{i, j}=f_{i-1, j}+f_{i-1, (j-a_i)\%m}\) ,表示 a_i 不选和选的情况数之和。这样的复杂度可以达到 O(nmq) 是无法承受的。
还可以想到线段树进行背包合并,但是这样的复杂度为 O((n+q)m^2logn) ,会 TLE 。
所以想到进行分治。(以下所有 mid=\lfloor\frac{l+r}{2}\rfloor)
首先离线处理询问,然后考虑区间 [l, r] 如何对这个询问产生贡献。首先,如果这个询问区间完全在 [l, mid-1] 中,那么先不用处理它,在递归进 [l, mid-1] 时处理就好了(注意,区间端点 =mid 的会在下面进行处理)。同样如果这个询问区间完全在 [mid+1, r] 中也是同理。
如果这个询问区间跨过了 mid (l \leq ql \leq mid \leq qr \leq r),那么这个询问的答案就可以被处理出来。注意因为 [l, r] 被分割成了 [l, mid] 和 [mid+1, r] 这两个子区间,所以询问区间 [ql, qr] 也可以被分割成两个子区间 [ql, mid] 和 [mid+1, qr] 。要快速的合并,所以对 [mid+1, r] 中的元素做一遍正向DP设得到 f 数组,对 [l, mid] 中的元素做一遍反向DP设得到 g 数组,这样 f 和 g 合并就可以得到跨过 mid 的一段区间的完整的答案了。合并的时候就直接把 f 中的方案数和 g 中的方案数相乘即可,即 [ql, qr] 这个询问的答案是 \sum\limits_{j+k=m}{f_{qr, j} \times g_{ql, k}} 。
这样处理下去,时间复杂度只有 O(m(nlogn+q)) 足以通过本题。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
|
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define MOD 1000000007 #define MAXBFN 4194304 char buffer[MAXBFN+1],*S,*T; inline char GetChar() { if(S==T) { T=(S=buffer)+fread(buffer,1,MAXBFN,stdin); if(S==T)return EOF; } return *S++; } char pbuf[MAXBFN+1],*pp=pbuf; inline void PutChar(const char&c) { if(pp-pbuf==MAXBFN) fwrite(pbuf,1,MAXBFN,stdout),pp=pbuf; *pp++=c; } inline void PrintNum(int a) { if(a>9) PrintNum(a/10); PutChar(a%10+'0'); } inline int getnum() { register char c=GetChar(); while(!(c>='0' && c<='9')) c=GetChar(); register int a=0; while(c>='0' && c<='9') { a*=10;a+=c-'0'; c=GetChar(); } return a; } int M; int a[205050]; struct _query { int ql,qr; int idx; }query[405050]; int ans[205050]; void Divide(int l,int r,int ql,int qr) { if(l>r || ql>qr) return; register int mid=(l+r)>>1; register int nqlr=ql-1,nqrl=qr+1,nq=ql; static _query tquery[405050]; for(register int i=ql;i<=qr;i++) if(query[i].qr<mid) tquery[++nqlr]=query[i]; else if(query[i].ql>mid) tquery[--nqrl]=query[i]; else query[nq++]=query[i]; static int f[205050][21]; f[mid][0]=1; for(register int j=1;j<M;j++) f[mid][j]=0; for(register int i=mid+1;i<=r;i++) for(register int j=0;j<M;j++) f[i][j]=(f[i-1][j]+f[i-1][(j-a[i]+M)%M])%MOD; static int rf[205050][21]; rf[mid+1][0]=1; for(register int j=1;j<M;j++) rf[mid+1][j]=0; for(register int i=mid;i>=l;i--) for(register int j=0;j<M;j++) rf[i][j]=(rf[i+1][j]+rf[i+1][(j-a[i]+M)%M])%MOD; for(register int i=ql;i<nq;i++) { register int tans=0; for(register int j=0;j<M;j++) tans=(tans+(long long)f[query[i].qr][j]*rf[query[i].ql][(M-j)%M]%MOD)%MOD; ans[query[i].idx]=tans; } for(register int i=ql;i<=nqlr;i++) query[i]=tquery[i]; for(register int i=nqrl;i<=qr;i++) query[i]=tquery[i]; Divide(l,mid-1,ql,nqlr); Divide(mid+1,r,nqrl,qr); } int main() { register int N=getnum();M=getnum(); for(register int i=1;i<=N;i++) a[i]=getnum(),a[i]%=M; register int Q=getnum(); for(register int i=1;i<=Q;i++) { query[i].ql=getnum(),query[i].qr=getnum(); query[i].idx=i; } Divide(1,N,1,Q); for(register int i=1;i<=Q;i++) PrintNum(ans[i]),PutChar('\n'); fwrite(pbuf,1,pp-pbuf,stdout); return 0; } |