分类目录归档:数学

Codeforces 102346 problem K Keep Calm and Sell Balloons

这道题重点要说矩阵快速幂,公式不会推。用了一个Berlekamp-Massey algorithm的模板。最主要想将一般情况下线性递推式怎么用矩阵快速幂优化。
本题目的递推公式是:$F(n)=6*F(n-1)-8*F(n-2)-8*F(n-3)+16*F(n-4)$。
故构造矩阵递推公式:
$$
\begin{bmatrix}
F(n) \\
F(n-1) \\
F(n-2) \\
F(n-3)
\end{bmatrix} =
\begin{bmatrix}
6 & -8 & -8 & 16 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix} *
\begin{bmatrix}
F(n-1) \\
F(n-2) \\
F(n-3) \\
F(n-4)
\end{bmatrix}
$$

$$
\begin{bmatrix}
F(n) \\
F(n-1) \\
F(n-2) \\
F(n-3)
\end{bmatrix} =
\begin{bmatrix}
6 & -8 & -8 & 16 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}^{n-4} *
\begin{bmatrix}
F(4) \\
F(3) \\
F(2) \\
F(1)
\end{bmatrix}
$$

对于一般的线性递推公式$F(n)=a_1*F(n-1)+a_2*F(n-2)+…+a_{k-1}*F(n-k+1)+a_k*F(n-k)$,
可以构造一长宽都为k的矩阵,满足:
$$
\begin{bmatrix}
F(n) \\
F(n-1) \\
… \\
F(n-k+2) \\
F(n-k+1)
\end{bmatrix} =
\begin{bmatrix}
a_1 & a_2 & … & a_{n-k+1} & a_{n-k} \\
1 & 0 & … & 0 & 0 \\
0 & 1 & … & 0 & 0 \\
… & … & … & … & … \\
0 & 0 & … & 1 & 0
\end{bmatrix} *
\begin{bmatrix}
F(n-1) \\
F(n-2) \\
… \\
F(n-k+1) \\
F(n-k)
\end{bmatrix}
$$
因此只需对该矩阵做快速幂,即可以以$O(k^3logn)$的复杂度推出任意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
#include <iostream>
using namespace std;
const long long MOD = 1e9 + 7;
const int maxtrixN=4;
struct matrix {
    long long arr[maxtrixN][maxtrixN];
    matrix operator * (matrix m2) {
        matrix result;
        long long(&arr)[maxtrixN][maxtrixN] = result.arr;
        const long long(&arr1)[maxtrixN][maxtrixN] = this->arr;
        const long long(&arr2)[maxtrixN][maxtrixN] = m2.arr;
        for (int i = 0; i < maxtrixN; i++) {
            for (int j = 0; j < maxtrixN; j++) {
                arr[i][j] = 0;
                for (int k = 0; k < maxtrixN; k++) {
                    arr[i][j] += arr1[i][k] * arr2[k][j] % MOD;
                    arr[i][j] += MOD;
                    arr[i][j] %= MOD;
                }
            }
        }
        return result;
    }
};
const matrix c = { 6,-8,-8,16,1,0,0,0,0,1,0,0,0,0,1,0 };
matrix quickpow(long long n) {
    if (n == 1)return c;
    matrix half = quickpow(n / 2);
    matrix result = half * half;
    if (n & 1)result = result * c;
    return result;
}
long long getValue(long long n) {
    matrix result = quickpow(n);
    long long(&arr)[4][4] = result.arr;
    return (arr[0][0] * 1536 % MOD + arr[0][1] * 416 % MOD + arr[0][2] * 96 % MOD + arr[0][3] * 24 % MOD +MOD) % MOD;
}
int main() {
    int n;
    long long a1[] = { 0,2,24,96,416,1536 };
    cin >> n;
    if (n < 6)cout << a1[n];
    else cout << getValue(n-5);
}

计蒜客 Random Access Iterator

原题链接:https://nanti.jisuanke.com/t/41392
竟然做出来一道这么复杂的概率+DFS+逆元题,开心到爆炸,特此发题解一篇^v^

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#define MOD 1000000007
#define ll long long
using namespace std;
int n;
int MDep;
vector<int> edges[1000005];
bool visited[1000005];
ll quickpow(ll a, ll b) {
    if (b == 0)return 1;
    ll re = quickpow(a, b / 2) % MOD;
    re = (re * re) % MOD;
    if (b % 2 == 1)re *= a % MOD;
    return re % MOD;
}
inline ll inv(ll x) {
    return quickpow(x, MOD - 2) % MOD;
}
inline ll chance1(ll TotNode) {
    ll ch = (inv(TotNode)) % MOD;
    return ch;
}
inline ll chance2(ll onceCh,ll TotNode) {
    ll onceNonch = (1ll-onceCh+MOD) % MOD;
    ll nonch = quickpow(onceNonch, TotNode);
    ll fin = (1ll - nonch + MOD) % MOD;
    return fin;
}
int dfsMaxDep(int node) {
    int maxDep = 1;
    bool hasChild = false;
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (visited[edges[node][i]])continue;
        hasChild = true;
        maxDep = max(maxDep, dfsMaxDep(edges[node][i]) + 1);
    }
    return maxDep;
}
ll dfsChance(int depth,int node){
    if (depth == MDep)return 1;
    ll ch = 0,sCh=chance1(node==1?edges[node].size(): edges[node].size()-1);
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (visited[edges[node][i]])continue;
        ll CurCH = dfsChance(depth + 1, edges[node][i]);
        if (CurCH) {
            ch += (CurCH * sCh) % MOD;
            ch %= MOD;
        }
    }
    return chance2(ch, node == 1 ? edges[node].size() : edges[node].size() - 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    MDep = dfsMaxDep(1);
    memset(visited, false, sizeof(visited));
    ll ch = dfsChance(1, 1);
    cout << ch;
}

洛谷 P2320 [HNOI2006]鬼谷子的钱袋

想不出来:参考题解:
https://www.luogu.org/blog/user50514/solution-p2320
https://www.luogu.org/blog/user26625/solution-p2320

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll ans,n,z[70];
int main(){
    cin>>n;
    while(n){
        z[++ans]=(n+1)/2;
        n/=2;
    }
    sort(z+1,z+ans+1);
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++)cout<<z[i]<<" ";
}

洛谷 P2261 [CQOI2007]余数求和

新学的知识点:除法分块。
题解:https://www.luogu.org/blog/Capella/solution-p2261

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#define ll long long
using namespace std;
ll n,k,ans;
int main(){
    cin>>n>>k;
    for(ll l=1,t,r;l<=n;l=r+1){
        t=k/l;
        if(t==0)r=n;
        else r=min(k/t,n);
        ans-=t*(l+r)*(r-l+1)/2;
    }
    cout<<ans+n*k;
}

洛谷 P2327 [SCOI2005]扫雷

还以为是搜索,写了半天之后懒得写了看看题解才发现出问题了。。
题解:https://www.luogu.org/blog/user31898/solution-p2327

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstring>
using namespace std;
int n;
int arr1[10005],arr2[10005];
bool f(){
    for(int i=2;i<=n+1;i++){
        arr2[i]=arr1[i-1]-arr2[i-1]-arr2[i-2];
        if(arr2[i]!=1&&arr2[i]!=0)return false;
        if(i==n+1&&arr2[i]!=0)return false;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>arr1[i];
    int num=0;
    arr2[1]=0;
    if(f())num++;
    arr2[1]=1;
    if(f())num++;
    cout<<num;
}

洛谷 P1984 [SDOI2008]烧水问题

有意思的一道数学题,就是找规律嘛。

1
2
3
4
5
6
7
8
9
10
11
#include<cstdio>
using namespace std;
int main(){
    double v=420000;
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        v*=1.0*(2*i-1)/2/i;
    }
    printf("%.2lf",v);
}

洛谷 P3383 【模板】线性筛素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
bool prime[10000005];

int main(){
    memset(prime, true, sizeof(prime));
    cin >> n >> m;
    prime[0] = prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (!prime[i])continue;
        for (int j = 2 * i; j <= n; j += i) {
            prime[j] = false;
        }
    }
    for (int i = 1; i <= m; i++) {
        int tmp;
        cin >> tmp;
        cout << (prime[tmp]?"Yes":"No") << endl;
    }
}

洛谷 P1338 末日的传说

可以说是超难的一道题了。。。。
全程题解:
https://www.luogu.org/blog/user11765/solution-p1338

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>
using namespace std;
long long n, m, a[50005];
int main() {
    cin >> n >> m;
    long long s = 1, e = n;
    for (long long i = 1; i <= n; i++) {
        long long t = (n - i)*(n - i - 1) / 2;
        if (t >= m)a[s++] = i;
        else {
            a[e--] = i;
            m -= e - s + 1;
        }
    }
    for (int i = 1; i <= n; i++)cout << a[i] << " ";
}

洛谷 P1147 连续自然数和

需要用到等差数列的性质,再稍微减减枝就可以了。只要能想到这些,写出来没难度。
令 $a < b$ ,a为首项,b为末项,为等差数列,公差为1。 则有 $(a+b)*(b-a+1)/2=n$。 即 $(a+b)*(b-a+1)=2*n$。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int main() {
    long long n;
    cin >> n;
    for (long long a = 1; a <= n/2; a++) {
        for (long long b = a; b <= n/2+1; b++) {
            long long l = (a + b)*(b - a + 1);
            if (l == 2 * n)cout << a << " " << b << endl;
            if (l > 2 * n)break;
        }
    }
}