5.3日以考试为主
T1签
小 D 对细胞分裂很感兴趣，现在小 D 发现了一种魔法细胞，一个魔法细胞在第二天会分裂出 x−1 个新的细胞（同时原细胞依然存在）。
初始容器中有 0 个魔法细胞，现在小 D 会在第 i 天往容器中加入 i 个魔法细胞，现在小 D 想知道，在第 n 天，培养皿中会有多少个细胞。
你只需要输出答案 modp 后的结果即可。
易得递推式 $T_n=xT_n-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
| #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define maxn 10
using namespace std;
int n,mo,x;
struct ahaha{
ll a[maxn][maxn];
ahaha(){
memset(a,0,sizeof a);
}
}a;
ahaha operator *(const ahaha &x,const ahaha &y){
ahaha z;
for(int k=1;k<=3;++k)
for(int i=1;i<=3;++i)
for(int j=1;j<=3;++j)
z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%mo)%mo;
return z;
}
int main(){
cin >> n >> x >> mo;
ahaha ans;
ans.a[1][1] = 0;
ans.a[1][2] = 0;
ans.a[1][3] = 1;
a.a[1][1] = x;
a.a[2][1] = 1;
a.a[3][1] = 1;
a.a[2][2] = 1;
a.a[3][2] = 1;
a.a[3][3] = 1;
do{
if(n&1)ans=ans*a;
a=a*a;n>>=1;
}while(n);
cout << ans.a[1][1];
return 0;
}
|
T2到
傻逼题 直接数位dp(然鹅我更傻逼 考场写不出来)
T3题
正解不会qwq
但其实是个结论题
迭代加深搜索即可qwq
