Editorial for Trò chơi lò cò
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của happyboy99x
#include <bits/stdc++.h> using namespace std; int modulo; vector<vector<int> > multiply(const vector<vector<int> > &a, const vector<vector<int> > &b) { vector<vector<int> > c (a.size(), vector<int>(b[0].size())); for (int i = 0; i < (int) a.size(); ++i) { for (int j = 0; j < (int) a[0].size(); ++j) { for (int k = 0; k < (int) b[0].size(); ++k) { c[i][k] = (c[i][k] + a[i][j] * b[j][k]) % modulo; } } } return c; } vector<vector<int> > unit(int n) { vector<vector<int> > a (n, vector<int>(n)); for (int i = 0; i < n; ++i) a[i][i] = 1; return a; } vector<vector<int> > power(vector<vector<int> > a, long long n) { vector<vector<int> > result = unit(a.size()); while (n > 0) { if (n % 2 != 0) result = multiply(result, a); a = multiply(a, a); n /= 2; } return result; } int main() { ios::sync_with_stdio(false); long long n; cin >> n >> modulo; vector<vector<int> > first (3, vector<int>(1)); first[2][0] = 1; vector<vector<int> > base (3, vector<int>(3)); base[0][1] = base[1][2] = base[2][0] = base[2][1] = base[2][2] = 1; cout << multiply(power(base, n), first)[2][0] << '\n'; return 0; }
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <fstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define REP(i, a, b) for(int i = (a); i <=(b); ++i) #define FORD(i, a, b) for(int i = (a); i > (b); --i) #define REPD(i, a, b) for(int i = (a); i >=(b); --i) #define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it) #define RESET(a, v) memset(a, (v), sizeof(a)) #define SZ(a) (int(a.size())) #define ALL(a) a.begin(), a.end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> #define VII vector<II> #define endl '\n' using namespace std; struct matrix { long long a[3][3]; }; int MOD; long long n; matrix base; matrix operator * (matrix a, matrix b) { matrix c; FOR(i, 0, 3) FOR(j, 0, 3) { c.a[i][j] = 0; FOR(k, 0, 3) c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j]) % MOD; } return c; } matrix power(long long p) { if (p == 1) return base; matrix x = power(p >> 1); x = x * x; if (p & 1) return x * base; return x; } int main() { ios::sync_with_stdio(0); cin.tie(0); #ifdef _LAD_ freopen("DHLOCO.in", "r", stdin); #endif // _LAD_ cin >> n >> MOD; base.a[0][0] = base.a[0][1] = base.a[0][2] = base.a[1][0] = base.a[2][1] = 1; long long f[4]; f[1] = 1; f[2] = 2; f[3] = 4; if (n <= 3) { cout << f[n] % MOD << endl; } else { matrix M = power(n - 3); cout << (f[3] * M.a[0][0] + f[2] * M.a[0][1] + f[1] * M.a[0][2]) % MOD << endl; } return 0; }
Code mẫu của skyvn97
#include<bits/stdc++.h> #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1) #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1) using namespace std; const int sta[]={1,1,2,4}; const int tmp[][3]={{0,0,1},{1,0,1},{0,1,1}}; int mod; struct Matrix { int m,n; vector<vector<int> > d; Matrix() { m=n=0; d.clear(); } Matrix(int m,int n) { this->m=m; this->n=n; d.assign(m,vector<int>(n,0)); } Matrix operator * (const Matrix &a) const { int x=m; int y=n; int z=a.n; Matrix res(x,z); REP(i,x) REP(j,y) REP(k,z) res.d[i][k]=(res.d[i][k]+d[i][j]*a.d[j][k])%mod; return (res); } Matrix operator ^ (long long k) const { Matrix res(n,n); Matrix mul=*this; REP(i,n) REP(j,n) res.d[i][j]=i==j; while (k>0) { if (k&1) res=res*mul; mul=mul*mul; k>>=1; } return (res); } }; void process(void) { long long n; cin>>n>>mod; Matrix fst(1,3),mul(3,3); REP(i,3) fst.d[0][i]=sta[i]; REP(i,3) REP(j,3) mul.d[i][j]=tmp[i][j]; fst=fst*(mul^n); cout<<fst.d[0][0]<<endl; } int main(void) { ios::sync_with_stdio(true); process(); return 0; }
Comments