Block
这是冬训的一道关于矩阵快速幂的题目，但我硬是想不出递推式，于是只好硬推公式(同时部分参考题解)
推导过程如下图：
代码如下:
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
|
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll mod=10007;
ll (ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)
ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
ll ans=((fpow(2,n-1)-1)*fpow(2,n-1)+fpow(2,n)+mod)%mod;
cout<<ans<<endl;
}
return 0;
}
|
近期评论