题目链接:点我
题目
题意:
给周长，求能围成的战场数目，不包括矩形。
思路:
矩阵快速幂;
如果包含矩形的话，对应的则是斐波那契数列的偶数项，所以对应减去矩形的个数即可
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mod = 987654321;
struct mat{
LL a[3][3];
mat(){memset(a, 0, sizeof(a)); }
mat operator *( const mat q){
mat c;
for(int i = 1; i <= 2; ++i)
for(int k = 1; k <= 2; ++k)
if(a[i][k])
for(int j = 1; j <= 2; ++j){
c.a[i][j] += a[i][k] * q.a[k][j];
if(c.a[i][j] >= mod)
c.a[i][j] %= mod;
}return c;
}
};
mat qpow(mat x, LL n){
mat ans;
ans.a[1][1] = ans.a[2][2] = 1;
while(n){
if(n&1) ans = ans * x;
x = x * x;
n >>= 1;
}return ans;
}
int main(){
LL p;
while(scanf("%lld", &p) != EOF&& p){
if(p < 8 || p&1){
printf("0\n");
continue;
}mat ans;
ans.a[1][1] = ans.a[2][1] = ans.a[1][2] = 1;
ans = qpow(ans, p-4);
LL sum = (ans.a[1][1] - p/2 + 1 + mod) % mod;
printf("%lld\n",sum);
}return 0;
}
|