计蒜客第三场总结

发表于 | 更新于 | 分类于 | 阅读次数：

计蒜客第三场总结

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;
       }
}