计蒜客第三场总结
A题
思路
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
| #include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
int dp[2001];
int cal(int s[] , int n, int x)
{
dp[1] = s[1];
int len = 1;
for(int i = 2; i <= n ; i++)
{
if(i == x) continue;
if(s[i] > dp[len])
{
dp[++len] = s[i];
}
else
{
int m = lower_bound(dp + 1,dp + len + 1, s[i]) - dp;
dp[m] = s[i];
}
}
return len;
}
int main()
{
int n, s[2001], a[2001], b[2001];
cin >> n;
if(n == 1)
cout << 1 << '\n';
else{
for(int i = 1; i <= n; ++i)
{
scanf("%d",&s[i]);
if(i >= 2)
a[i - 1] = s[i];
}
int tot = 0;
int len = cal(s, n , 0);
b[++tot] = cal(a, n - 1, 0);
for(int i = 2; i <= n; ++i)
{
b[++tot] = cal(s, n ,i);
}
int cnt = 0;
for(int i = 1; i <= n; ++i)
{
if(b[i] < len)
cnt++;
}
cout << cnt << '\n';
}
}
|
B题及C题
思路
请移步题解
D题
思路
早早做完前三个题就开始在这个题自闭了，完全没有遇到过N这么大的情况。后来听师哥说是欧拉降幂。
挡在指数爆炸的时候我们就用这个，求$a^b\mod c$ 时，可以转化为：
下面给出欧拉降幂公式
$$
a^{(\ b \mod \phi(c)) + \phi(c)} \mod c
$$
$\phi（x）$ 指的是 欧拉函数 ，可以参考我记录的。 然后套用费马小定理，就可以过 。 虽说这里是普通的快速幂降幂公式，但是应用到矩阵似乎也是可以的。
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
71
72
73
74
75
76
77
78
| #include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
struct Matrix{
ll m[4][4];
};
const ll mod = 1000000007;
Matrix mul(Matrix A,Matrix B)
{
Matrix tmp;
memset(tmp.m,0,sizeof(tmp.m));
for(int i = 1; i <= 3 ;i++)
for(int j = 1; j <= 3 ;j++)
for(int k = 1; k <= 3 ;k++)
{
tmp.m[i][j] = (tmp.m[i][j] + A.m[i][k] * B.m[k][j]) % mod;
tmp.m[i][j] %= mod;
}
return tmp;
}
Matrix pow(Matrix A,ll n)
{
int i;
Matrix res;
memset(res.m,0,sizeof(res.m));
for(i = 1; i <= 3 ;i++)
res.m[i][i] = 1;
while(n)
{
if(n & 1)
res = mul(res,A);
A = mul(A,A);
n >>= 1;
}
return res;
}
long long quyu(string s)
{
long long sum1 = 0;
for(int i = 0; i < s.size(); ++i)
{
sum1 = (sum1 * 10 + s[i] - '0') % (mod - 1);
}
return sum1;
}
int main()
{
int T;
string s;
long long n;
while(cin >> s )
{
if(s[0] == '0')
break;
n = quyu(s);
n = n + mod - 1;
Matrix A;
A.m[1][1] = 2;
A.m[1][2] = 1;
A.m[1][3] = 0;
A.m[2][1] = 2;
A.m[2][2] = 2;
A.m[2][3] = 2;
A.m[3][1] = 0;
A.m[3][2] = 1;
A.m[3][3] = 2;
A = pow(A,n - 1);
Matrix C;
C.m[1][1] = 2;
C.m[2][1] = 2;
C.m[3][1] = 0;
C = mul(A,C);
cout << C.m[1][1] << endl;
}
}
|