DTOJ 4020 式神守護

式神守護

【題目背景】

“操縱着大結界的，是紫呢。”

“紫？就是那個一直在隙間裡睡覺的那個？”

“她可是具有式神守護着的妖怪哦。”

【題目描述】

紫媽 （尊重出題人） 有 n n n 個隙間排成一列，每個隙間都有一個權值 v a l i val_{i} vali​ 。

她可以選出某些隙間來召喚式神：一組隙間能成功召喚式神當且僅當他們的權值和為 m m m的倍數。(可以是 0 0 0 倍)

現在紫媽 試圖召喚 Q Q Q次式神，每次給出一個 l i l_{i} li​和 r i r_{i} ri​ ,她試圖在第 l i l_{i} li​和 r i r_{i} ri​個隙間中召喚式神，

她會選擇其中一些隙間（不一定需要連續的一些）召喚式神。她想知道，有多少種方案可以

成功召喚式神。

【輸入格式】

第一行兩個數， n n n 和 m m m。

第二行n 個數，表示 v a l i val_{i} vali​ 。

第三行一個數，表示 Q Q Q。

下面 Q Q Q行，每行兩個數，表示 l i l_{i} li​和 r i r_{i} ri​ 。

【輸出格式】

Q Q Q行，每行一個數，表示方案數，方案數 m o d ( 1 0 9 + 7 ) mod (10^9+ 7 ) mod(109+7)輸出。

【樣例輸入】

4 3

5 1 3 2

2

1 2

1 3

【樣例輸出】

2

4

【資料範圍與約定】

對于 100 % 100\% 100%的資料， n ≤ 200000 , Q ≤ 200000 , m ≤ 20 , 1 ≤ v a l i ≤ 1 0 9 n\leq 200000,Q\leq 200000,m\leq 20,1\leq val_{i}\leq 10^9 n≤200000,Q≤200000,m≤20,1≤vali​≤109 。

資料有梯度。

題解：

騷騷的分治（orzJyt orzSlz）

考慮暴力，設 f i , j f_{i,j} fi,j​表示前 i i i個數，構成價值是 j j j 的方案數。

于是 f 0 , 0 = 1 f_{0,0}=1 f0,0​=1 , f i , ( j + a i ) m o d m + = f i − 1 , j f_{i,(j+a_{i})modm}+=f_{i-1,j} fi,(j+ai​)modm​+=fi−1,j​

然後在考場上，我還想了個 n l o g n × m 2 nlogn\times m^2 nlogn×m2的線段樹，每個節點存下該區間從 0 0 0到 m − 1 m-1 m−1的方案數，詢問的時候将兩段區間用 m 2 m^2 m2處理出來。

成功拿到 50 p t s 50pts 50pts。

正解：

考慮分治。

将所有區間先提出來，然後對于 v a l i val_{i} vali​分治，并且帶上詢問。

考慮分治到 [ l , r ] [l,r] [l,r]，中間是 m i d mid mid。

考慮對于詢問區間，将 r ≤ m i d r\leq mid r≤mid 的區間放到 [ l , m i d ] [l,mid] [l,mid]中做，将 l ≥ m i d l\geq mid l≥mid的區間放到 [ m i d + 1 , r ] [mid+1,r] [mid+1,r]中做。

隻考慮跨過 m i d mid mid的區間。

從 m i d mid mid往兩邊跑上面的暴力 D P DP DP

然後直接合并即可。

考場 50 p t s 50pts 50pts代碼：

#include<bits/stdc++.h>
using namespace std;
#define in inline
#define re register
#define rep(i,a,b) for(re int i=a;i<=b;i++)
#define repd(i,a,b) for(re int i=a;i>=b;i--)
#define For(i,a,b) for(re int i=a;i<b;i++)
#define _(d) while(d(isdigit(ch=getchar())))
#define shenben puts("orzlkw");
template<class T>in void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;}
typedef long long ll;
const int mod=1e9+7;
const int N=200004;
int n,m,val[N];
struct seg{int v[23];}t[N<<2];
in void mer(seg &x,seg le,seg ri){
	For(i,0,m) x.v[i]=(1ll*le.v[i]+ri.v[i])%mod;
	For(i,0,m){
		For(j,0,m){
			x.v[(i+j)%m]=(x.v[(i+j)%m]+1ll*le.v[i]*ri.v[j]%mod)%mod;
		}
	}
}
in void build(int x,int l,int r){
	if(l==r){t[x].v[val[l]%m]++;return;}
	int mid=l+r>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	mer(t[x],t[x<<1],t[x<<1|1]);
}
in seg Q(int x,int l,int r,int L,int R){
	if(l>=L&&r<=R) return t[x];
	int mid=l+r>>1;
	if(R<=mid) return Q(x<<1,l,mid,L,R);
	else if(L>mid) return Q(x<<1|1,mid+1,r,L,R);
	else{
		seg t1=Q(x<<1,l,mid,L,mid);
		seg t2=Q(x<<1|1,mid+1,r,mid+1,R);
		seg res;mer(res,t1,t2);
		return res;
	}
}
int main(){
	freopen("yukari.in","r",stdin);freopen("yukari.out","w",stdout);
	g(n),g(m);
	rep(i,1,n) g(val[i]);
	build(1,1,n);
	int T;g(T);
	while(T--){
		int l,r;g(l),g(r);
		if(l>r) swap(l,r);
		seg tmp=Q(1,1,n,l,r);
		//For(i,0,m) cout<<tmp.v[i]<<endl;
		printf("%d\n",(1ll*tmp.v[0]%mod+1)%mod);
	}
	return 0;
}
           

正解：

#include<bits/stdc++.h>
using namespace std;
#define in inline
#define re register
#define rep(i,a,b) for(re int i=a;i<=b;i++)
#define repd(i,a,b) for(re int i=a;i>=b;i--)
#define For(i,a,b) for(re int i=a;i<b;i++)
#define _(d) while(d(isdigit(ch=getchar())))
#define shenben puts("orzlkw");
template<class T>in void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;}
const int N=200004,M=30,mod=1e9+7;
struct Q{
	int l,r,id;
}q[N],tmp[N];
int a[N],n,m,T,f[N][M],h[N][M],ans[N];
in void mer(int l,int r,int ql,int qr){
	if(ql>qr) return;
	if(l==r){
		rep(i,ql,qr) ans[q[i].id]++;
		return;
	}
	int mid=l+r>>1;
	int t1=0,t2=0,t3=0;
	rep(i,ql,qr) if(q[i].r<=mid) tmp[++t1]=q[i]; 
	t2=t1; rep(i,ql,qr) if(q[i].l<=mid&&q[i].r>mid) tmp[++t2]=q[i];
	t3=t2; rep(i,ql,qr) if(q[i].l>mid) tmp[++t3]=q[i];
	for(int i=ql,j=1;i<=qr,j<=t3;i++,j++) q[i]=tmp[j];
	mer(l,mid,ql,ql+t1-1);mer(mid+1,r,ql+t2,qr);
	rep(i,l,mid+1) rep(j,0,m) f[i][j]=0;
	rep(i,mid,r) rep(j,0,m) h[i][j]=0;
	f[mid+1][0]=1;h[mid][0]=1;
	repd(i,mid,l){
		For(j,0,m) 
			f[i][(j+a[i])%m]=(f[i+1][j]+f[i][(j+a[i])%m])%mod;
		For(j,0,m) f[i][j]+=f[i+1][j],f[i][j]%=mod;
	}
		
	rep(i,mid+1,r){
		For(j,0,m) 
			h[i][(j+a[i])%m]=(h[i-1][j]+h[i][(j+a[i])%m])%mod; 
		For(j,0,m) h[i][j]+=h[i-1][j],h[i][j]%=mod;
	}
		
	rep(i,ql+t1,ql+t2-1)
		For(j,0,m) 
			ans[q[i].id]=(ans[q[i].id]+1ll*f[q[i].l][j]*h[q[i].r][((m-j)%m+m)%m]%mod)%mod;
}
int main(){
	//freopen(".in","r",stdin);freopen(".out","w",stdout);
	g(n);g(m);
	rep(i,1,n) g(a[i]);
	g(T); rep(i,1,T) g(q[i].l),g(q[i].r),q[i].id=i;
	mer(1,n,1,T);
	rep(i,1,T){
		printf("%d\n",(1ll*(ans[i])%mod+mod)%mod);
	}
	return 0;
}