【Reading comprehension】题意:Fi满足:if (i & 1)ans = (ans * 2 + 1) % m;
else ans = ans * 2 % m;
,给出n,m，问Fn为多少。
当i为奇数时,Fi=4F(i-1)+1,当j为偶数时，Fj=4F(j-1)+2.我们可以得到这样一个关系：
文章图片
#include
#include
#include
#includeusing namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int arr[N];
ll mod;
struct matrix {
ll rix[5][5];
}ans,test;
ll quick_pow(ll a,ll b) {
ll ans = 1;
a %= mod;
while (b) {
if (b & 1) ans = (ans + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return ans;
}matrix mul(int n,matrix rix1,matrix rix2) {
matrix temp;
memset(temp.rix, 0, sizeof(temp.rix));
for (int i = 1;
i <= n;
i++) {
for (int j = 1;
j <= n;
j++) {
for (int k = 1;
k <= n;
k++) {
temp.rix[i][j] = (temp.rix[i][j] + rix1.rix[i][k] * rix2.rix[k][j])%mod;
}
}
}
return temp;
}void quick_rix(int n,int k) {
memset(ans.rix, 0, sizeof(ans.rix));
for (int i = 1;
i <= n;
i++) ans.rix[i][i] = 1;
while (k) {
if (k & 1) ans = mul(n,ans,test);
test = mul(n, test, test);
k >>= 1;
}
//return ans;
}int main() {
ios::sync_with_stdio(false);
matrix rax;
int n;
while (cin >> n >> mod) {
memset(rax.rix, 0, sizeof(rax.rix));
memset(test.rix, 0, sizeof(test.rix));
rax.rix[1][1] = 1;
rax.rix[2][1] = 2;
rax.rix[1][2] = 1;
rax.rix[2][2] = 2;
test.rix[1][1] = 4;
test.rix[2][1] = 1;
test.rix[1][2] = 0;
test.rix[2][2] = 1;
if (n == 1) {
cout << (rax.rix[1][1] + mod) % mod << endl;
}
else if (n == 2) {
cout << (rax.rix[2][1] + mod) % mod << endl;
}
else {
quick_rix(2, (n - 1) / 2);
ans = mul(2, rax, ans);
if (n & 1) {
cout << (ans.rix[1][1] + mod) % mod << endl;
}
else {
cout << (ans.rix[2][1] + mod) % mod << endl;
}
}
}
} 推荐阅读
- 题解|【HNOI2017】大佬-dalao
- 2019 GDUT Rating Contest #II 这是群题解，七篇！！！
- # 2019 GDUT Rating Contest #I H. Mixing Milk
- # 2019 GDUT Rating Contest #I A. The Bucket List
- # 2019 GDUT Rating Contest #I G. Back and Forth
- 2019 GDUT Winter Personal Training Contest III (Div. 2) A题 QAQ 题解
- 2019 GDUT Winter Personal Training Contest I (Div. 2) A. Protect Sheep
- 题解|题解 | K-ary Heap-2019牛客暑期多校训练营第六场F题
- ACM|[dsu] codeforces 375D. Tree and Queries
- 题解|[BZOJ3817] Sum