PROBLEM LINK:
Author & Editoralist: Jafar Badour
Tester: Teja Reddy
PROBLEM EXPLANATION
Please refer to the problem statement.
PREREQUISITES:
probabilities
EXPLANATION:
The solution is much easier than the problem looks like.
First of all let’s do some preprocessing. Let’s calculate all values of the table:
prob[s][x][y] which denotes the probability to reach y from x through s transformations. This can be done in O(M^4) which is around 10^8. The DP approach here is very straight forward so I am not going to write every detail.
It’s easy to handle very large K because the powers x^0,x^1,x^2,... of some integer x modulo M would have a period (cycle) with a length of at most M. So calculating coefficients for moving 1 step forward in the DP table won’t be hard, just find the cycle.
Since the last query cannot have a timestamp larger than 10^6, let’s break the time line into buckets of M timestamps. First bucket for queries with a timestamp in the range [0,M-1], second for queries with a timestamp in range [M,2*M-1] and so on.
Let’s denote with exp[T][x] the expected value of number of elements equal to x at timestamp T. Let’s calculate the table values only for every T which is a multiple of M.
We initially have the values of exp[0][anything].
If we have the values of exp[T][x] for every x we can calculate the values for exp[T+M][y] easily using a straight forward convolution with an assist from table prob.
for each x,y:
exp[T+M][y]+=exp[T][x]*prob[M][x][y]
This is of course correct due to linearity of expectation. Of course, we are still ignoring all types of queries, but probably if you have good understanding of what’s been happening above you can continue on your own.
Let’s assume first that we don’t have type 2 queries. To answer a query of type 1 we look at the nearest bucket to its left. More formally if the query was issued at time tq let’s get back to the table exp[tq - tq \%M][]. Let’s assume that the number the query is asking for is equal to tar, and for simplicity let’s have tl=tq - tq \%M
for each x:
answer += exp[tl][x]*prob[tq-tl][x][tar]
Queries of type 2 won’t make the problem anyhard. Just add each query to the first bucket to its right so from there and afterwards, it will be affected by transformations.
Also, type2 queries may affect type1. We are recording the effects of type2 since we are augmenting each query to the next bucket. What we are still lacking is the effect of type2 query on a type1 query within the same bucket. For handling this we can just loop over all type2 queries to the left (within same bucket) when handling any type1 query and the contribution of the insertion query can be calculated easily with table prob help.
Complexity: max(O(M^4),O(M*maxT)) which are numerically the same.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MX = (1<<20) , MOD = 1e9 + 7;
typedef long long ll;
int POW(int x , int y){
if(y == 0) return 1;
ll ret = POW(x , y/2);
ret *= ret; ret %= MOD;
if(y % 2) ret *= x;
return ret % MOD;
}
int inv(int x){
return POW(x , MOD - 2);
}
int n , Q , K , M;
int prob[102][102][102];
int dp[102] , dp2[102];
int tran[102];
int cmd[1<<20] , num[1<<20] , ans[1<<20];
int main(){
// freopen("exptree.in","r",stdin);
cin>>n>>Q>>K>>M;
for(int x = 1 ; x < M ; x++){
prob[0][x][x] = 1;
set < int > S;
int cur = x , cyc = 0;
vector < int > v;
while(1){
if(S.count(cur)) break;
++cyc;
v.push_back(cur);
S.insert(cur);
cur *= x;
cur %= M;
}
memset(tran , 0 , sizeof(tran));
int rem = K % cyc;
int tot = 0;
for(int j = 0 ; j < v.size() ; j++){
if(j < rem) ++tran[v[j]];
tran[v[j]] += K / cyc;
tot += tran[v[j]];
}
for(int y = 1 ; y < M ; y++){
prob[1][x][y] = (1ll * tran[y] * POW(tot , MOD - 2))%MOD;
//if(x == 1) cout<<tran[y]<<' '<<tot<<' '<<prob[1][x][y]<<endl;
}
}
for(int step = 2 ; step <= 100 ; step++){
for(int x = 1 ; x < M ; x++){
for(int y = 1 ; y < M ; y++){
for(int z = 1 ; z < M ; z++){
prob[step][x][y] += (1ll * prob[step-1][x][z] * prob[1][z][y])%MOD;
prob[step][x][y] %= MOD;
}
}
}
}
for(int j = 1 ; j <= n ; j++){
int x; scanf("%d",&x);
++dp[x % M];
}
int mxT = 0;
for(int j = 1 ; j <= Q ; j++){
int cc , tt , xx;
scanf("%d %d %d",&cc,&tt,&xx);
cmd[tt] = cc;
num[tt] = xx;
mxT = max(mxT , tt);
}
for(int curT = 0 ; curT <= mxT ;){
for(int q1 = curT ; q1 < curT + 100 ; q1++){
if(cmd[q1] == 2){
for(int q2 = q1 ; q2 < curT + 100 ; q2++){
if(cmd[q2] == 1)
ans[q2] += prob[q2 - q1][num[q1]][num[q2]] , ans[q2] %= MOD;
}
}
if(cmd[q1] == 1){
for(int x = 1 ; x < M ; x++){
ans[q1] = (ans[q1] + ( (1ll * dp[x] * prob[q1 - curT][x][num[q1]]) % MOD ) ) % MOD;
}
}
}
int t2 = curT + 100;
memset(dp2 , 0 , sizeof(dp2));
for(int x = 1 ; x < M ; x++){
for(int y = 1 ; y < M ; y++){
dp2[y] = (dp2[y] + ( (1ll * dp[x] * prob[100][x][y]) % MOD ) ) % MOD;
}
}
for(int j = 1 ; j < M ; j++)
dp[j] = dp2[j];
for(int q1 = curT ; q1 < t2 ; q1++){
if(cmd[q1] == 2){
for(int x = 1 ; x < M ; x++){
dp[x] = (dp[x] + prob[t2 - q1][num[q1]][x])%MOD;
}
}
}
curT = t2;
}
for(int j = 1 ; j <= mxT ; j++){
if(cmd[j] == 1)
cout<<ans[j]<<endl;
}
}