式神守護

題目描述

紫媽有 n 個隙間排成一列，每個隙間都有一個權值 i val 。她可以選出某些隙間來召喚式神：一組隙間能成功召喚式神當且僅當他們的權值和為 m的倍數。(可以是 0 倍)現在紫媽試圖召喚 Q 次式神，每次給出一個 i i l 和r ,她試圖在第 i i l 到r 個隙間中召喚式神，她會選擇其中一些隙間（不一定需要連續的一些）召喚式神。她想知道，有多少種方案可以成功召喚式神。

題解

神犇們都容易想到線段樹（是以我沒想到），維護區間各個餘數的個數，然後每次答案就是左邊的答案+右邊的答案+左邊的 s u m [ i ] ∗ s u m [ m − i ] sum[i]*sum[m-i] sum[i]∗sum[m−i]

這樣會多一個M，考慮到我們好像重複統計了很多次，可以用一種類似整體二分的方法來分治解決。

寫一個函數 s o l v e ( l , r , q l , q r ) solve(l,r,ql,qr) solve(l,r,ql,qr)表示現在在處理 [ l , r ] [l,r] [l,r]的區間，這個區間内是屬于 [ q l , q r ] [ql,qr] [ql,qr]的詢問，那麼分治的時候暴力把在左半區間的詢問放到左邊，右邊的放到右邊讓 s o l v e ( l , m i d , q l , t l ) solve(l,mid,ql,tl) solve(l,mid,ql,tl)和 s o l v e ( m i d + 1 , r , t r , q r ) solve(mid+1,r,tr,qr) solve(mid+1,r,tr,qr)處理。

在中間的我們可以用 d p dp dp處理出 f [ i ] [ j ] f[i][j] f[i][j]表示從 m i d mid mid一直向左到 i i i的餘數為 j j j的方案數，同理處理出 g [ i ] [ j ] g[i][j] g[i][j]，對于一個區間 [ a , b ] [a,b] [a,b]答案就是枚舉 j j j的 ∑ f [ l ] [ j ] ∗ g [ r ] [ m − j ] \sum f[l][j]*g[r][m-j] ∑f[l][j]∗g[r][m−j]，複雜度 O ( m ∗ n ∗ l o g ( n ) ) O(m*n*log(n)) O(m∗n∗log(n))’

代碼

#include <bits/stdc++.h>
#define maxn 200005
#define mod 1000000007
using namespace std;
int read(){
    int res,f=1; char c;
    while(!isdigit(c=getchar())) if(c=='-') f=-1; res=(c^48);
    while(isdigit(c=getchar())) res=(res<<3)+(res<<1)+(c^48);
    return res*f;
}
struct NODE{
    int l,r,id;
}p[maxn],q[maxn];
int n,m,Q,a[maxn],ans[maxn];
int f[maxn][20],g[maxn][20];
void solve(int l,int r,int ql,int qr){
    if(l==r){
        for(int i=ql;i<=qr;i++) ans[p[i].id]=(a[l]==0)+1;
        return ;
    }
    int mid=l+r>>1,tl=ql-1,tr=qr+1;
    for(int i=ql;i<=qr;i++){
        if(p[i].r<=mid) q[++tl]=p[i];
        else if(p[i].l>mid) q[--tr]=p[i];
    }
    int tt=tl; for(int i=ql;i<=qr;i++) if(p[i].l<=mid && p[i].r>mid) q[++tt]=p[i];
    for(int i=ql;i<=qr;i++) p[i]=q[i];
    if(ql<=tl) solve(l,mid,ql,tl);
    if(tr<=qr) solve(mid+1,r,tr,qr);
    for(int j=0;j<m;j++) f[mid+1][j]=(j==0);
    for(int j=0;j<m;j++) g[mid][j]=(j==0);
    for(int i=mid;i>=l;i--)
        for(int j=0;j<m;j++)
            f[i][j]=(f[i+1][j]+f[i+1][(j-a[i]+m)%m])%mod;
    for(int i=mid+1;i<=r;i++)
        for(int j=0;j<m;j++)
            g[i][j]=(g[i-1][j]+g[i-1][(j-a[i]+m)%m])%mod;
    for(int i=tl+1;i<=tr-1;i++)
        for(int j=0;j<m;j++)
            ans[p[i].id]=(ans[p[i].id]+1ll*f[p[i].l][j]*g[p[i].r][(m-j)%m])%mod;
}
int main(){
    n=read(); m=read();
    for(int i=1;i<=n;i++) a[i]=read()%m;
    Q=read();
    for(int i=1;i<=Q;i++){
        p[i].l=read(); p[i].r=read(); p[i].id=i;
    }
    solve(1,n,1,Q);
    for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
}