营销网站设计公司,国外专门做童装的网站,域名跳转wordpress,优搜云seoF. Copy or Prefix Sum Venice technique简要就是懒标记思想。 由于前缀和数组和原数组一一对应#xff0c;这里我们选择求aia_iai的前缀和数组的方案数#xff08;下面aia_iai表示原题数组的前缀和#xff09;
不难得知原题目的两个条件即 biai−ai−1→aibiai−1b_ia…F. Copy or Prefix Sum Venice technique简要就是懒标记思想。 由于前缀和数组和原数组一一对应这里我们选择求aia_iai的前缀和数组的方案数下面aia_iai表示原题数组的前缀和
不难得知原题目的两个条件即
biai−ai−1→aibiai−1b_ia_i-a_{i-1} \to a_ib_ia_{i-1}biai−ai−1→aibiai−1biai→aibib_ia_i \to a_ib_ibiai→aibi
状态表示fi,jf_{i,j}fi,j考虑前iii个数所求数组第iii个位置值是jjj的方案数。 答案即是∑j−∞∞fn,j\sum_{j-\infty}^{\infty}f_{n,j}∑j−∞∞fn,j
状态转移
fi,jfi−1,j−bif_{i,j}f_{i-1,j-b_i}fi,jfi−1,j−bifi,bi∑j−∞∞fi−1,j−(fi−1,0)f_{i,b_i}\sum_{j-\infty}^{\infty}f_{i-1,j}-(f_{i-1,0})fi,bi∑j−∞∞fi−1,j−(fi−1,0)
aibiai−1a_ib_ia_{i-1}aibiai−1和aibia_ib_iaibi当ai−10a_{i-1}0ai−10时是同一种情况因此需要把重复计算的去掉。
按照上述转移方式肯定不可信不难发现第一维可以用滚动数组优化掉注意第一个转移式子相当于将整个数组平移bib_ibi这里采用的懒标记的思想做一个下标映射。
对于第一种转移维护一个addfi,jfi−1,j−bifi−1,jaddf_{i,j}f_{i-1,j-b_i}f_{i-1,jadd}fi,jfi−1,j−bifi−1,jadd如果每次让add减去bib_ibi就完成了对数组的平移操作也就是第一种转移。
而下面一种转移只需要记住原来bib_ibi的位置是biaddb_iaddbiadd即可转移
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#pragma GCC optimize(2)
#includemap
#includeiostream
#includealgorithm
using namespace std;
using lllong long;
constexpr int N100010;
constexpr ll mod1e97;
int n;
mapll,ll dp;
int main()
{IO;int T1;cinT;while(T--){cinn;dp.clear();dp[0]1;ll sum1,add0;for(int i1;in;i){ll b;cinb;ll presum-dp[0add]; pre(pre%modmod)%mod;add-b;sumpre; sum%mod;dp[badd]pre; dp[badd]%mod;}coutsum\n;}return 0;
}
