Sofi received an array of integers, A , as a birthday present, and decides to cut it into segments. She wants to know how many different cuttings have segments with products divisible by her favorite number, K . Help her find the answer, and print it modulo 109+9 .
Constraints
1≤N≤105
2≤K≤1018
1≤Ai≤1018
Input Format
The first line contains two space-separated integers, N (the size of Sofi's array) and K (Sofi's favorite number).
The second line containsN space-separated integers describing Sofi's array (A ).
The second line contains
Output Format
Print the number of different cuttings with segment products that are divisible by K modulo 109+9 .
Sample Input
5 3
2 3 1 6 3
Sample Output
6
Explanation
Here are the 6 ways to cut this array so its segments have products divisible by 3 (K ):
1) [2,3,1,6,3] Product: 108.
2) [2,3,1,6] [3] Products: 36,3.
3) [2,3] [1,6,3] Products: 6,18.
4) [2,3] [1,6] [3] Products: 6,6,3.
5) [2,3,1] [6,3] Products: 6,18.
6) [2,3,1] [6] [3] Products: 6,6,3.
Note: Your printed answer must be modulo 109+9 .
------------------------editorial----------------------------------------------------
The problem is that
Let's have function:
MU(A,B,C)=
if B==0 then: 0
if B is odd then: (MU(A,B/2,C)*2+A) mod C
if B is even then: MU(A,B/2,C)*2 mod C
This will take maximum O(log2C) . Also this can be represented whithout recursion (in my code).
*****
4) Solution O(N×log22N×log2K) .
In solution above it's easy to understand that:
If[l,r] is divisible by K . segment [l−1,r] will be divisible by K too.(since we are just multiplying 1 more number in the segment )
So in previous solution we only need to find maximumy where mu=0 . Using binary search we will find answer quickly. Also we will need O(log2N) multiplication, if we construct segment using sub-segments (precalculated above).
for index say we need to find nearest index l<=r so that l to r multiply mod k==0
In solution above it's easy to understand that:
If
So in previous solution we only need to find maximum
for index say we need to find nearest index l<=r so that l to r multiply mod k==0
for that we did 2 things first we create multiplication segment tree ie query (l,r) will give
multiplication of element froml to r % k
now for index r we can have nearest l at atmost index 1 ( or not exist any l such that l tor multiply %k==0)
now we can do binary search from 1 to r to fix l suppose we find mid and mid to r multiplication
mud give 0 so la can le lie in the range mid to r so now do b_search in mid to r and so on
ex--
array -
1 ,2, 7, 5, 3 ,9 ,12 and k=6
suppose for index=5(value 3) we want to find nearest l<=r such that l to r multiply %k=0
i=1 ,r=5 , mid=(1+5)/2=3
form 3 to 5 multiply is 7*5*3=105%6!=0
so wee have to find l in 1 to mid ie 1 to 3
again mid is (1+3)/2=2,
form 2 to 5 multiply is 2*7*5*3=210%6==0
soo it is valid so now we try to shifl more right
aagain calculate mid mid=(2+3)/2=2 which is privious mid sooo for r=index 5 nearest l is at index 2
or we can use another approach
Let's have
Calculating is quite easy:
Let's have
Solutin of this is easy too.
dp[0]=1 // answer for empty array is 1.
for x in [1..N] // brute force of x
for y in [1..x] // brute froce of last segment [y,x]
mu = 1 // multiply of segment [y,x]
for z in [y,x]
mu = MU(mu,a[z],K) // "a" is given array
if mu is 0 then: // if mu is 0 that means segment is valid
dp[x] = dp[x] + dp[y-1] // so if last segment is [y,x] then we
// need variants to divide segment [1,y-1]
Just change binary search with "picking up powers of
It means:
Just have segment size of zero
Consider powers of
--------------------------------code----------------------------------------------------------
#include<iostream>
#include<bits/stdc++.h>
typedef long long int lli;
#define ull unsigned long long int
using namespace std;
lli arr[1010000];
lli seg[10100000];
lli mod =1000000009;
lli dp[10000000];
lli sfx[1000000];
lli n,k;
int in;
ull mul(ull a,ull b,ull c)
{
return (__uint128_t (a) * __uint128_t (b) % c);
if(a<=1000000000ULL && b<=1000000000ULL)
{
ull ret = ((a%c)*(b%c))%c;
return ret;
}
ull ret = 0ULL;
a=a%c;
while(b > 0ULL)
{
if(b&1ULL)
{
ret = (ret+a)%c;
}
a = (a<<1ULL)%c;
b>>=1ULL;
}
return ret%c;
}
void build(int i,int si,int sj){
if(si==sj){
seg[i] = arr[si]%k;
}
else{
int mid = (si+sj)/2;
build(2*i,si,mid);
build(2*i+1,mid+1,sj);
seg[i] = mul(seg[2*i],seg[2*i+1],k);
}
}
lli query(int index,int start,int end,int qs,int qe)
{
if(start>end || qs>end || qe<start) return 1 ;
else
{
if(start==end)
{
return seg[index];
}
else if( qs<=start && qe>=end)
{
return seg[index];
}
else
{
int mid=(start+end)/2;
lli q1=query(2*index,start,mid,qs,qe);
lli q2=query(2*index+1,mid+1,end,qs,qe);
return mul(q1,q2,k);
} }
}
int bin_search(int i,int j,int s)
{
if(i==j)
return i;
int mid = ceil((i+j)/2.0);
if(query(1,1,n,mid,s)==0)
{
return bin_search(mid,j,s);
}
else{
return bin_search(i,mid-1,s);
}
}
int main()
{
// freopen("abc.txt","r",stdin);
cin>>n>>k;
memset(seg,-1,sizeof seg);
memset(dp,-1,sizeof dp);
for(int i=1;i<=n;i++)
{
cin>>arr[i];
arr[i]%=k;
}
build(1,1,n);
dp[0]=1;
sfx[0]=1;// suffix array contain no of ways answer can be computed till i
for(int i=1;i<=n;i++)
{
in=bin_search(1,i,i);
if(query(1,1,n,in,i)!=0)
{
dp[i] = 0;
}
else
{
dp[i] = sfx[in-1];
}
sfx[i] = (dp[i] + sfx[i-1]) % mod;
}
cout<<dp[n]<<endl;
}
No comments:
Post a Comment