1.2万

AKStream
Dionysus.

MrYFX
Jared_McDs

-猴不猴-
Scott
17uk
Jiangly_fan

ly123
l_y_f
Tequila

throwsException

// Problem: 阅读理解
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4827/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//

#include<bits/stdc++.h>
#define endl '\n'
#define Carol MyWife^=^
#define pb push_back
#define pp pop_back
#define debug1(x) cout << #x << " = " << (x) << '\n'
#define debug2(x) cout << #x << " = " << (x) << ' '
//#define x first
//#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e6+5, M = 1e6+5;
const int INF = 0x3f3f3f3f;
int n, MOD;
int nmod(int x) {
if(x < 0) x += MOD;
if(x >= MOD) x -= MOD;
return x;
}
template<class T>
T qpow(T a, LL b, LL p) {
T res = 1;
while(b) {
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
struct Mint {
int x;
Mint(int x = 0) : x(nmod(x)) {}
Mint(LL x) : x(nmod(x % MOD)) {}
int val() const {
return x;
}
Mint operator-() const {
return Mint(nmod(MOD - x));
}
Mint inv() const {
return qpow(*this, MOD - 2, MOD);
}
Mint &operator*=(const Mint &rhs) {
x = LL(x) * rhs.x % MOD;
return *this;
}
Mint &operator+=(const Mint &rhs) {
x = nmod(x + rhs.x);
return *this;
}
Mint &operator-=(const Mint &rhs) {
x = nmod(x - rhs.x);
return *this;
}
Mint &operator/=(const Mint &rhs) {
return *this *= rhs.inv();
}
friend Mint operator*(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res *= rhs;
return res;
}
friend Mint operator+(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res += rhs;
return res;
}
friend Mint operator-(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res -= rhs;
return res;
}
friend Mint operator/(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res /= rhs;
return res;
}
friend istream &operator>>(istream &is, Mint &a) {
LL v;
is >> v;
a = Mint(v);
return is;
}
friend ostream &operator<<(ostream &os, const Mint &a) {
return os << a.val();
}
} ;
const int MN = 5;
struct Matrix {
int n, m;
Mint v[MN][MN];
Matrix (int t = 0) {
memset(v, 0, sizeof v);
if(t == 1) {
for(int i = 0; i <= n + 1; i ++)
v[i][i] = 1;
}
}
Matrix operator*(const Matrix& b) const {
Matrix res;
res.n = n, res.m = b.m;
for(int k = 1; k <= m; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= b.m; j ++)
res.v[i][j] += this->v[i][k] * b.v[k][j];
return res;
}
Matrix operator^(LL b) {
Matrix res = *this, a = *this;
b --;
while(b) {
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
} ;
void solve() {
while(cin >> n >> MOD) {
if(n == 1) {
cout << 1 << endl;
continue;
}
Matrix a, base;
a.n = 1, a.m = 2;
a.v[1][1] = 0, a.v[1][2] = 2;
base.n = 2, base.m = 2;
base.v[1][1] = 4, base.v[1][2] = 0;
base.v[2][1] = 1, base.v[2][2] = 1;
a = a * (base^(n/2));
if(n % 2 == 0) cout << a.v[1][1] << endl;
else if(n % 2 == 1) cout << a.v[1][1] * 2 + 1 << endl;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t --) solve();

return 0;
}


// Problem: 233矩阵
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/228/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//

#include<bits/stdc++.h>
#define endl '\n'
#define Carol MyWife^=^
#define pb push_back
#define pp pop_back
#define debug1(x) cout << #x << " = " << (x) << '\n'
#define debug2(x) cout << #x << " = " << (x) << ' '
//#define x first
//#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e6+5, M = 1e6+5;
const int MOD = 10000007, INF = 0x3f3f3f3f;
int nmod(int x) {
if(x < 0) x += MOD;
if(x >= MOD) x -= MOD;
return x;
}
template<class T>
T qpow(T a, LL b, LL p) {
T res = 1;
while(b) {
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
struct Mint {
int x;
Mint(int x = 0) : x(nmod(x)) {}
Mint(LL x) : x(nmod(x % MOD)) {}
int val() const {
return x;
}
Mint operator-() const {
return Mint(nmod(MOD - x));
}
Mint inv() const {
return qpow(*this, MOD - 2, MOD);
}
Mint &operator*=(const Mint &rhs) {
x = LL(x) * rhs.x % MOD;
return *this;
}
Mint &operator+=(const Mint &rhs) {
x = nmod(x + rhs.x);
return *this;
}
Mint &operator-=(const Mint &rhs) {
x = nmod(x - rhs.x);
return *this;
}
Mint &operator/=(const Mint &rhs) {
return *this *= rhs.inv();
}
friend Mint operator*(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res *= rhs;
return res;
}
friend Mint operator+(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res += rhs;
return res;
}
friend Mint operator-(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res -= rhs;
return res;
}
friend Mint operator/(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res /= rhs;
return res;
}
friend istream &operator>>(istream &is, Mint &a) {
LL v;
is >> v;
a = Mint(v);
return is;
}
friend ostream &operator<<(ostream &os, const Mint &a) {
return os << a.val();
}
} ;
const int MN = 105;
struct Matrix {
int n, m;
Mint v[MN][MN];
Matrix (int t = 0) {
memset(v, 0, sizeof v);
if(t == 1) {
for(int i = 0; i <= n + 1; i ++)
v[i][i] = 1;
}
}
Matrix operator*(const Matrix& b) const {
Matrix res;
res.n = n, res.m = b.m;
for(int k = 1; k <= m; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= b.m; j ++)
res.v[i][j] += this->v[i][k] * b.v[k][j];
return res;
}
Matrix operator^(LL b) {
Matrix res = *this, a = *this;
b --;
while(b) {
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
} ;
int n, m;
void solve() {
while(cin >> n >> m) {
Matrix a, base;
a.n = 1, a.m = n + 2;
for(int i = 2; i <= n + 1; i ++) {
cin >> a.v[1][i];
}
a.v[1][1] = 23, a.v[1][n + 2] = 1;
base.n = n + 2, base.m = n + 2;
for(int i = 1; i <= n + 1; i ++) base.v[1][i] = 10;
for(int i = 2; i <= n + 1; i ++)
for(int j = 2; j <= n + 1; j ++)
if(j >= i) base.v[i][j] = 1;
for(int i = 1; i <= n + 1; i ++) base.v[n + 2][i] = 3;
base.v[n + 2][n + 2] = 1;
Matrix b = (base^m);
cout << (a * b).v[1][n + 1] << endl;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
//cin >> t;
while(t --) solve();

return 0;
}


#include <iostream>
using namespace std;

const int N = 200010;
const int _l = -1e9, _r = 1e9;
struct Node {
int l, r;
int cnt;
} tr[N * 35];
int root[N], idx;
int w[N], n, q, x;
void insert(int p, int &q, int l, int r, int pos, int v) {
tr[q = ++ idx] = tr[p];
tr[q].cnt += v;
if(l == r) return ;
int mid = l + r >> 1;
if(pos <= mid) insert(tr[p].l, tr[q].l, l, mid, pos, v);
else insert(tr[p].r, tr[q].r, mid + 1, r, pos, v);
}
int query(int p, int q, int l, int r, int k) {
if(l == r) return l;
int lcnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
if(lcnt >= k) return query(tr[p].l, tr[q].l, l, mid, k);
else return query(tr[p].r, tr[q].r, mid + 1, r, k - lcnt);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i ++) {
cin >> x;
insert(root[i - 1], root[i], _l, _r, x, 1);
}
while(q --) {
int l, r, k;
cin >> l >> r >> k;
cout << query(root[l - 1], root[r], _l, _r, k) << endl;
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int _l = -1e9, _r = 1e9;
const int N = 100010;
struct Node {
int l, r;
int mx;
}tr[N * 32];
int idx, root;
int n, a[N], ans[N];
void insert(int& p, int l, int r, int x, int v) {
if (!p) p = ++idx;
tr[p].mx = max(tr[p].mx, v);
if (l == r) return;
int mid = l + r >> 1;
if (x <= mid) insert(tr[p].l, l, mid, x, v);
else insert(tr[p].r, mid + 1, r, x, v);
}

int query(int p, int l, int r, int ql, int qr) {
if (!p) return 0;
if (l >= ql && r <= qr) return tr[p].mx;
int mid = l + r >> 1, res = 0;
if (ql <= mid) res = max(res, query(tr[p].l, l, mid, ql, qr));
if (qr > mid) res = max(res, query(tr[p].r, mid + 1, r, ql, qr));
return res;
}

int main() {
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
}
for(int i = n; i; i --) {
int x = query(root, _l, _r, 1, a[i] - 1);
if(x > i) ans[i] = x - i - 1;
else ans[i] = -1;
insert(root, _l, _r, a[i], i);
}
for(int i = 1; i <= n; i ++) {
cout << ans[i] << " \n"[i == n];
}

return 0;
}


#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

typedef long long LL;

const int N = 101000;
int n, m, p;
LL a[N];
struct Seg {
LL val;
LL siz;
} tr[N<<2];
void pushup(int u) {
tr[u].val = (tr[u << 1].val + tr[u << 1 | 1].val) % p;
}
void update(Seg &t, LL add, LL mul) {
t.mul = (t.mul * mul) % p;
t.val = (t.val * mul + add * (t.siz)) % p;
}
void pushdown(int u) {
tr[u].mul = 1;
}
void build(int u, int l, int r) {
tr[u] = {a[l], 0, 1, r - l + 1};
if(l == r) {
return ;
} else {
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
LL query(int u, int l, int r, int ql, int qr) {
if(l >= ql && r <= qr) return tr[u].val;
else {
pushdown(u);
int mid = l + r >> 1;
LL sum = 0;
if(ql <= mid) sum += query(u << 1, l, mid, ql, qr);
if(qr > mid) sum += query(u << 1 | 1, mid + 1, r, ql, qr);
return sum % p;
}
}
LL modify(int u, int l, int r, int ql, int qr, int add, int mul) {
if(l >= ql && r <= qr) {
} else {
pushdown(u);
int mid = l + r >> 1;
if(ql <= mid) modify(u << 1, l, mid, ql, qr, add, mul);
if(qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, add, mul);
pushup(u);
}
}
signed main() {
cin >> n >> p;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
}
build(1, 1, n);
cin >> m;
while(m --) {
int opt, l, r, x;
cin >> opt >> l >> r;
if(opt <= 2) {
cin >> x;
if(opt == 1) modify(1, 1, n, l, r, 0, x);
else modify(1, 1, n, l, r, x, 1);
} else {
cout << query(1, 1, n, l, r) % p << endl;
}
}

return 0;
}


#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+5;

int nxt[N], n;
char s[N];

int main() {
while(cin >> s + 1) {
n = strlen(s + 1);
for(int i = 2; i <= n; i ++) {
int j = nxt[i - 1];
while(j && s[i] != s[j + 1]) j = nxt[j];
if(s[i] == s[j + 1]) j ++;
nxt[i] = j;
}
vector<int> ans;
for(int i =  n; i; i = nxt[i]) {
ans.push_back(i);
}
for(int i = ans.size() - 1; ~i; i --)
cout << ans[i] << " \n"[i == 0];
}
}


#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n, nxt[N];
char s[N];
int main() {
while(cin >> s + 1) {
n = strlen(s + 1);
if(n == 1 && s[1] == '.') break;
for(int i = 2; i <= n; i ++) {
int j = nxt[i - 1];
while(j && s[i] != s[j + 1]) j = nxt[j];
if(s[i] == s[j + 1]) j ++;
nxt[i] = j;
}
for(int i = n; i; i = nxt[i]) {
if(n % (n - nxt[i]) == 0) {
cout << n / (n - nxt[i]) << endl;
break;
}
}
}

return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int nxt[N], n;
char s[N];
int main() {
while(cin >> s + 1) {
n = strlen(s + 1);
for(int i = 2; i <= n; i ++) {
int j = nxt[i - 1];
while(j && s[i] != s[j + 1]) j = nxt[j];
if(s[i] == s[j + 1]) j ++;
nxt[i] = j;
}
cout << n  - nxt[n] << endl;
}

return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n, nxt[N], Case;
string s;
vector<int> v;
int main() {
while(cin >> n && n) {
cin >> s;
s = " " + s;
for(int i = 2; i <= n; i ++) {
int j = nxt[i - 1];
while(j && s[i] != s[j + 1]) j = nxt[j];
if(s[i] == s[j + 1]) j ++;
nxt[i] = j;
}
cout << "Test case #" << ++ Case << endl;
for(int i = 1; i <= n; i ++) {
int t = i - nxt[i];
if(i % t == 0 && i / t > 1) {
cout << i << ' ' << i / t << endl;
}
}
cout << endl;
}

return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
string s;
int nxt[N];
int main() {
int T;
cin >> T;
while(T --) {
cin >> s;
int n = s.size();
s =  " " + s;
nxt[1] = 0;
for(int i = 2; i <= n; i ++) {
int j = nxt[i - 1];
while(j && s[i] != s[j + 1]) j = nxt[j];
if(s[i] == s[j + 1]) j ++;
nxt[i] = j;
}
int ans = n;
for(int i = nxt[n]; i; i = nxt[i]) {
int p = n - i;
if(n % p == 0) ans = 0;
ans = min(ans, p - n%p);
}
cout << ans << endl;
}

return 0;
}