1220模拟赛 区间积

1220模拟赛 区间积

题目大意:

给一个序列和一些限制$l,r,ans$表示需要使得

$$\prod_{i=l}^{r}a_i\equiv ans(mod \space 10)$$

询问满足条件的序列个数。序列中每个数$0\le a_i< 10$。

我们发现$10$不是个素数,很难处理,所以我们把$10$拆成$2$和$5$,分别处理。

对于每个素数,我们考虑判断每个区间中有没有$0$。

设$g_{l,r}$为区间$[l,r]$中可以有$0$时的方案数,$f_{l,r}$为没有$0$时的方案数。

对于每个$g_{l,r}$:

如果区间中没有限制,$g_{l,r}=p^{r-l+1}$。

否则我们考虑枚举区间中第一个$0$的位置。

假设这个位置为$k$。当有$ans$不为$0$的限制经过$k$,或者有$ans$为$0$的限制在$i$左边时,位置$i$不可行。

如果可行:

$$f_{l,k-1}\times g_{k+1,r}\to g_{l,r}$$

这样$g$就做完了。

对于$f_{l,r}$:

如果区间中没有限制,$f_{l,r}=(p-1)^{r-l+1}$。

否则:

我们设$sum_k$为区间中的前缀积,即$sum_k=\prod_{i=l}^{k}a_i$。

则一个限制$l,r,ans$就表示$sum_{l-1}\times ans=sum_r$。

我们发现这就相当于把$sum_{l-1}$和$sum_r$“绑定”起来,即这两个值的取值是相关的。

我们考虑用并查集来维护这个东西,并额外定义$val_i$为当$f_i$取值为$1$时$i$的取值。这可以一边$find$一边维护。

这时可以顺便判一下无解:对于一个限制$l,r,ans$,当$sum_{l-1}$与$sum_r$已经在一个并查集中时,如果${val_r\over val_{l-1}}\ne ans$则很明显不合法。

对于合法情况,$f_{l,r}$就是

$$
(p-1)^{并查集个数}
$$

这样就OK了。

代码:

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
#include <cstdio>
#include <vector>
#include <cstring>
#define int long long
#define pb push_back

struct point{int l,r,ans;};
typedef std::vector<point> V;

V orig;
int n,q,g[110][110],f[110][110],p=1000000007,fa[110],val[110],b,inv[10];

int qsm(int a,int b){
int ans=1;
while(b){
if(b&1)(ans*=a)%=p;
(a*=a)%=p;
b>>=1;
}
return ans;
}
int find(int x){
if(fa[x]==x)return x;
int t=fa[x];
fa[x]=find(fa[x]);
(val[x]*=val[t])%=b;
return fa[x];
}
bool unionn(int x,int y,int cnt){
int fx=find(x),fy=find(y);
if(fx!=fy){
fa[fx]=fy;
(val[fx]=val[y]*inv[val[x]]*inv[cnt])%=b;
return 1;
}
else return (val[y]*inv[val[x]])%b==cnt;
}
int F(int l,int r,V vec){
if(~f[l][r])return f[l][r];
if(vec.empty())return f[l][r]=qsm(b-1,r-l+1);
for(int i=l-1;i<=r;i++)fa[i]=i,val[i]=1;
for(int i=0;i<vec.size();i++){
if(!(vec[i].ans%b))return f[l][r]=0;
else if(!unionn(vec[i].l-1,vec[i].r,vec[i].ans%b))return f[l][r]=0;
}
int cnt=0;
for(int i=l-1;i<=r;i++)
if(fa[i]==i)cnt++;
return f[l][r]=qsm(b-1,cnt-1);
}
int G(int l,int r,V vec){
if(~g[l][r])return g[l][r];
if(vec.empty())return g[l][r]=qsm(b,r-l+1);
g[l][r]=F(l,r,vec);
for(int i=l;i<=r;i++){
bool cando=0;
V v1,v2;
for(int j=0;j<vec.size();j++){
if(vec[j].l<=i&&i<=vec[j].r)
if(vec[j].ans%b)cando=1;
if(vec[j].r<i)v1.pb(vec[j]);
if(vec[j].l>i)v2.pb(vec[j]);
}
if(cando)continue;
(g[l][r]+=F(l,i-1,v1)*G(i+1,r,v2))%=p;
}
return g[l][r];
}
signed main(){
scanf("%lld%lld",&n,&q);
for(int i=1;i<=q;i++){
point now;
scanf("%lld%lld%lld",&now.l,&now.r,&now.ans);
++now.l;
++now.r;
orig.pb(now);
}
inv[1]=1,inv[2]=3,inv[3]=2,inv[4]=4;

int cnt=1;
b=2;
memset(f,-1,sizeof f);
memset(g,-1,sizeof g);
cnt=G(1,n,orig);

b=5;
memset(f,-1,sizeof f);
memset(g,-1,sizeof g);
cnt*=G(1,n,orig);

printf("%lld",cnt%p);
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×