[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\) 组询问的答案。
-
样例输入
1 2 3 4 5 6 7 |
4 3 5 1 3 2 4 1 2 1 3 1 4 2 4 |
-
样例输出
1 2 3 4 |
2 4 6 4 |
-
样例说明
对于第一组询问 \(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; } |