【Luogu4881】hby与tkw的基情

Source and Judge

Luogu4881

Record

30min

Analysis

请先思考后再展开

非常好推柿子
$\sum_{i=0}^{ \lfloor \frac{n-1}{2} \rfloor } (2i+1)26^{i+1}$

方法一

n非常大
显然要用快速幂和矩阵乘法
那么矩阵的设计可以参考代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const ll MOD=1e9+7;
struct mm
{
ll a[4][4];
mm() {memset(a,0,sizeof a);}
};
mm pre()
{
mm t;
for(int i=1;i<=3;i++) t.a[i][i]=1;
return t;
}
mm cheng(mm a,mm b)
{
mm c;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
c.a[i][j]+=a.a[i][k]*b.a[k][j]%MOD;
return c;
}
mm qpower(mm x,int e)
{
mm c=pre();
while(e>0)
{
if(e&1) c=cheng(c,x);
x=cheng(x,x);e>>=1;
}
return c;
}
void main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
n=(n-1)/2;
mm op;op.a[1][1]=op.a[2][1]=op.a[2][2]=26;op.a[3][1]=1;op.a[3][2]=2;op.a[3][3]=1;
op=qpower(op,n+1);
mm st;st.a[1][1]=26;
st=cheng(op,st);
printf("%lld\n",st.a[3][1]);
}
}
};
int main()
{
mine::main();
}

方法二

然鹅上面的方法很慢,因为矩阵乘法的常数达到了30
其实有高中数学常识的很容易看出是一个差比数列(看题解后学的……)
不了解的可以去定理杂烩一章

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/3729.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%