Array
Title Description
Yukikaze received an array (a1,a2,⋯an)as a gift. She decided to play with it. The game consists of q turns. In each turn, she will perform some kind of operation (listed below) on all elements in a subarray of a.
In this problem, we define that 00=1.
Since the result of operations of the last two kinds may be large, you only have to find it modulo a small integer p.
input
Input
The first line of the input contains two integers n,p (1≤n≤105,2≤p≤30), denoting the number of elements in the array a and the modulus for the operations of type 4 and 5.
The next line contains n integers a1,a2,⋯,an (0≤ai≤109), denoting the initial elements in the array a.
The third line contains one integer q (1≤q≤105), denoting the number of operations to be performed.
Each of the following q lines contains 4 integers t,l,r,k (1≤t≤5,1≤l≤r≤n,0≤k≤109) represents an operation of kind t. Note that if t=5, it's guaranteed that k=0.
output
For each operation of type 4 or 5, output the result modulo p as an integer in a single line.
Sample Input
5 29 5 2 4 1 3 9 4 2 4 1 1 1 3 2 2 2 4 3 3 3 5 2 5 3 3 0 4 1 5 2 2 3 5 0 3 2 4 0 4 3 4 1
Sample Output
7 5 3 2
Problem solving ideas
This question is obviously a line segment tree. Let's talk about the overall idea first, and then we'll study it in detail
1. What we need to implement is query and product, but each element here is independent of each other. Then we can count their numbers first and then calculate them. Therefore, we use the following two codes in our calculation
ans += EularPow(i, k, mod) * cnt[i];
ans %= mod;
ans *= EularPow(i, cnt[i], mod);
ans %= mod;
You should be able to see the meaning at a glance
2. We need to design 30 trees to maintain, because their values are between 0-30, so we can maintain the number of elements of each tree.
3. We need to design lazy markers. Here, the lazy tag indicates the value corresponding to the current lazy tag and what value it should be converted to. Take a pen and paper here and draw it. It will be clear. For clarity, let's take an example.
For example, at present, my lazy flag is 1 2 3 4 5, but my father's lazy flag is 1 8 27 64 125. In this way, we can understand that all numbers 1 become the father's corresponding values, 1, 2 correspond to 8, 3 correspond to 27, etc
When we calculate, our current lazy tag will change the current lazy tag to modify the value.
4. Value modification is to delete from one tree and then add to another tree
5. Query and count the traversal quantity results
6. Euler power reduction is needed to calculate pow. Pro test, without Euler power reduction TLE, here is one-step optimization.
7. I / O will be stuck
8. Using longlong increases the amount of computation and will be stuck
Next, we will release the code of Euler's power reduction
a b ≡ { a b % φ ( p ) g c d ( a , p ) = 1 a b g c d ( a , p ) ≠ 1 , b < φ ( p ) a b % φ ( p ) + φ ( p ) g c d ( a , p ) ≠ 1 , b ≥ φ ( p ) ( m o d p ) a^{b}\equiv \left\{\begin{matrix} a^{b\%\varphi (p)} &gcd(a,p)=1 \\ a^{b}&gcd(a,p)\neq 1,b<\varphi(p) \\ a^{b\%\varphi (p)+\varphi (p)}&gcd(a,p)\neq 1,b\ge \varphi(p) \end{matrix}\right.\quad (mod\; p) ab≡⎩⎨⎧ab%φ(p)abab%φ(p)+φ(p)gcd(a,p)=1gcd(a,p)=1,b<φ(p)gcd(a,p)=1,b≥φ(p)(modp)
ll EularPow(ll a, ll b, ll mod) {
ll ans = 1;
if (gcd(a, mod) == 1)b = b % phi;
else if (b >= phi)b = b % phi + phi;
while (b > 0) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
The value of phi needs to be solved by Euler function, which is released here
ll eular(ll n)
{
ll ans = n;
for (ll i = 2; i * i <= n; i++)
if (n % i == 0) { ans = ans / i * (i - 1); while (n % i == 0)n /= i; }
if (n > 1)ans = ans / n * (n - 1); return ans;
}
Train of thought analysis completed
Accept Code
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<string.h>
#include <iomanip>
#include<stdio.h>
#include<vector>
#include<string>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll ll_inf = 9223372036854775807;
const int int_inf = 2147483647;
const short short_inf = 32767;
const ll less_inf = 0x3f3f3f3f;
const char char_inf = 127;
#pragma GCC optimize(2)
#pragma warning(disable:6031)
#define accelerate cin.tie(NULL);cout.tie(NULL);ios::sync_with_stdio(false)
#define PI 3.141592653589793
#define EPS 1.0e-8
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
inline ll read() {
ll c = getchar(), Nig = 1, x = 0;
while (!isdigit(c) && c != '-')c = getchar();
if (c == '-')Nig = -1, c = getchar();
while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar();
return Nig * x;
}
inline void out(ll a) {
if (a < 0)putchar('-'), a = -a;
if (a > 9)out(a / 10);
putchar(a % 10 + '0');
}
ll qpow(ll x, ll n, ll mod) {
ll res = 1;
while (n > 0) {
if (n & 1)res = (res * x) % mod;
x = (x * x) % mod;
n >>= 1;
}
return res;
}
#define read read()
const int N = 100005;
int mod;
int tree[N << 2][31];
int lazy[N << 2][31];
int temp[31];
int cnt[31];
int tot = 0;
vector<int>save;
int phi;
ll eular(ll n)
{
ll ans = n;
for (ll i = 2; i * i <= n; i++)
if (n % i == 0) { ans = ans / i * (i - 1); while (n % i == 0)n /= i; }
if (n > 1)ans = ans / n * (n - 1); return ans;
}
ll EularPow(ll a, ll b, ll mod) {
ll ans = 1;
if (gcd(a, mod) == 1)b = b % phi;
else if (b >= phi)b = b % phi + phi;
while (b > 0) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
void push_up(int rt)
{
for (int i = 0; i < mod; i++)
tree[rt][i] = tree[rt << 1][i] + tree[rt << 1 | 1][i];
}
void push_down(int rt)
{
for (int i = 0; i < mod; i++)
{
temp[i] = tree[rt << 1][i];
tree[rt << 1][i] = 0;
}
for (int i = 0; i < mod; i++)
tree[rt << 1][lazy[rt][i]] += temp[i];
for (int i = 0; i < mod; i++)
{
temp[i] = tree[rt << 1 | 1][i];
tree[rt << 1 | 1][i] = 0;
}
for (int i = 0; i < mod; i++)
tree[rt << 1 | 1][lazy[rt][i]] += temp[i];
for (int i = 0; i < mod; i++)
{
lazy[rt << 1][i] = lazy[rt][lazy[rt << 1][i]];
lazy[rt << 1 | 1][i] = lazy[rt][lazy[rt << 1 | 1][i]];
}
for (int i = 0; i < mod; i++)lazy[rt][i] = i;
}
void creat(int l, int r, int rt)
{
if (l == r)
{
tree[rt][save[tot++] % mod]++;
return;
}
for (int i = 0; i < mod; i++)
lazy[rt][i] = i;
int mid = l + r >> 1;
creat(l, mid, rt << 1);
creat(mid + 1, r, rt << 1 | 1);
push_up(rt);
}
ll change(ll num, ll val, ll ord)
{
switch (ord)
{
case 1:return (num + val) % mod;
case 2:return (num * val) % mod;
default:return EularPow(num, val, mod);
}
}
void update(int ord, int k, int L, int R, int l, int r, int rt)
{
if (L <= l && r <= R)
{
for (int i = 0; i < mod; i++)
{
temp[i] = tree[rt][i];
tree[rt][i] = 0;
}
for (int i = 0; i < mod; i++)
{
int num = change(i, k, ord);
lazy[rt][i] = change(lazy[rt][i], k, ord);
tree[rt][num] += temp[i];
}
return;
}
push_down(rt);
int mid = l + r >> 1;
if (L <= mid)update(ord, k, L, R, l, mid, rt << 1);
if (R > mid)update(ord, k, L, R, mid + 1, r, rt << 1 | 1);
push_up(rt);
}
void query(int L, int R, int l, int r, int rt)
{
if (L <= l && r <= R)
{
for (int i = 0; i < mod; i++)
cnt[i] += tree[rt][i];
return;
}
push_down(rt);
int mid = l + r >> 1;
if (L <= mid)query(L, R, l, mid, rt << 1);
if (R > mid)query(L, R, mid + 1, r, rt << 1 | 1);
}
int main()
{
int n;
scanf("%d%d", &n, &mod);
phi = eular(mod);
for (int i = 0; i < n; i++)
{
int t;
scanf("%d", &t);
save.push_back(t);
}
creat(1, n, 1);
int T;
scanf("%d", &T);
while (T--)
{
int ord, l, r, k;
scanf("%d%d%d%d", &ord, &l, &r, &k);
if (ord <= 3)
update(ord, k, l, r, 1, n, 1);
else if (ord == 4)
{
memset(cnt, 0, sizeof(cnt));
query(l, r, 1, n, 1);
int ans = 0;
for (int i = 0; i < mod; i++)
{
ans += EularPow(i, k, mod) * cnt[i];
ans %= mod;
}
printf("%d\n", ans);
}
else
{
memset(cnt, 0, sizeof(cnt));
query(l, r, 1, n, 1);
int ans = 1;
for (int i = 0; i < mod; i++)
{
ans *= EularPow(i, cnt[i], mod);
ans %= mod;
}
printf("%d\n", ans);
}
}
}