題目

這里寫鏈接內容

題意

給出一個最長為200000200000數列
給出一堆最多為200000200000個詢問區間，問從這些區間中取出一些數使得數字之和是m的倍數，有多少種方案。其中保證1≤m≤201≤m≤20。

題解

最容易想到的方法就是倍增+dp來做。
定義f[i][j][k]f[i][j][k]表示區間[l,l+2j)[l,l+2j)內，選取數字之和modm==kmodm==k的方案數。
這種dpdp很容易想到，轉移方程也比較容易寫，但是空間復雜度會爆炸掉，因此我們必須換一種方法。

離線分治算法：
對于最開始的區間[1,n][1,n]我們考慮它的中點mid=(1+n)/2mid=(1+n)/2，有的詢問區間包含了mid這個點，有的在mid點左邊，有的在mid點右面。
在這里我們可以用O(n)O(n)的時間復雜度內計算出所有包含mid點的詢問區間的答案，然后把剩下的詢問區間分到左右兩邊，然后再分治解決。

如何在O(n)O(n)的時間復雜度內計算出所有包含mid點的詢問區間的答案：
記錄f[i][k]f[i][k]表示區間[l,mid][l,mid]之間選取數字之和模m等于k的方案數。
記錄g[i][k]g[i][k]表示區間[mid+1,i][mid+1,i]之間選取數字之和模m等于k的方案數。
那么詢問區間[l,r](l≤mid≤r)的答案就是：∑m?10f[l][i]?g[r][(m?i)%m]詢問區間[l,r](l≤mid≤r)的答案就是：∑0m?1f[l][i]?g[r][(m?i)%m]

代碼

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> using namespace std; #define pr(x) cout<<#x<<":"<<x<<endl const int maxn = 2e5+7; int n,m,q; int query[maxn][3]; int g[maxn][22]; int f[maxn][22]; int a[maxn]; const int mod = 1e9+7; void solve(int l,int r,vector<int> qs){if(l >= r || qs.size() == 0)return ;int mid = (l + r) / 2;for(int i = l;i < r;++i) for(int j = 0;j < m;++j)g[i][j] = f[i][j] = 0;f[mid][0] = 1;for(int i = mid-1;i >= l;i--){for(int j = 0;j < m;++j){f[i][(j+a[i])%m] = (f[i][(j+a[i])%m] + (long long)f[i+1][j]) % mod;f[i][j] = (f[i][j] + f[i+1][j]) % mod;}}g[mid-1][0] = 1;for(int i = mid;i < r;++i){for(int j = 0;j < m;++j){g[i][j] = (g[i][j] + g[i-1][j]) % mod;g[i][(j+a[i])%m] = (g[i][(j+a[i])%m] + (long long)g[i-1][j]) % mod;}}vector<int> qs1,qs2;for(auto i : qs){if(query[i][1] < mid-1) qs1.push_back(i);else if(query[i][0] > mid) qs2.push_back(i);else {if(query[i][1] == mid-1){query[i][2] = f[query[i][0]][0];}else if(query[i][0] == mid){query[i][2] = g[query[i][1]][0];}else{for(int j = 0;j < m;++j){query[i][2] = (query[i][2] + (long long)f[query[i][0]][j] * g[query[i][1]][(m-j)%m])% mod;}}} }solve(l,mid,qs1);solve(mid,r,qs2); } int main(){scanf("%d%d",&n,&m);for(int i = 1;i <= n;++i){scanf("%d",&a[i]);a[i] %= m;}vector<int> qs;scanf("%d",&q);for(int i = 0; i < q;++i){scanf("%d %d",&query[i][0],&query[i][1]);qs.push_back(i);}solve(1,n+1,qs);for(int i = 0;i < q;++i){printf("%d\n",query[i][2]);}return 0; }

總結

以上是生活随笔為你收集整理的codeforces gym-101741 Subsequence Sum Queries 分治+离线的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。