[Offer收割]编程练习赛30 register

Ended

Participants:188

Verdict:Accepted
Score:100 / 100
Submitted:2017-10-08 13:20:46

Lang:G++

Edit
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
#include <iostream>
#include <bits/stdc++.h>
#include <sstream>
#include <vector>
using namespace std;
typedef long long int LL;
typedef vector<long long int> vec;
typedef vector<vec> mat;
const int maxn=1000000+10;
const int MOD=1000000007;
mat mul(mat A, mat B)
{
    mat C(A.size(), vec(B[0].size()));
    for (unsigned i = 0; i < A.size(); i++)
        for (unsigned j = 0; j < B[0].size(); j++)
            for (unsigned k = 0; k < B.size(); k++)
                C[i][j] = ((C[i][j] + A[i][k] * B[k][j]%MOD) + MOD) % MOD; // +MOD
    return C;
}
mat pow(mat A, LL n)
{
    mat B(A.size(), vec(A.size()));
    for (unsigned i = 0; i < A.size(); i++)
        B[i][i] = 1;
    while (n > 0)
    {
        if (n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX