算法模板

发表于 更新于 分类于 本文字数： 16k 阅读时长 ≈ 28 分钟

数据结构

并查集

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
#define MAXN 1000
int par[MAXN];
int u_rank[MAXN];

int n = 500;
void init()
{
    for(int i=0; i<n; i++)
    {
        par[i] = i;
        u_rank[i] = 0;
    }
}

int u_find(int x)
{
    if(par[x] == x)
        return x;
    else
        return par[x] = u_find(par[x]);
}

void unite(int x, int y)
{
    x = u_find(x);
    y = u_find(y);
    if(x == y)
        return;
    if(u_rank[x] < u_rank[y])
        par[x] = y;
    else
    {
        par[y] = x;
        u_rank[x]++;
    }
}

bool same(int x, int y)
{
    return u_find(x) == u_find(y);
}

BIT (树状数组)

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
/*
	计算前i项和需要从i开始，不断把当前位置i的值加入到结果中，并从i中减去i的二进制最低非0位对应的幂，直到i变为0为止。i的二进制最后一个1可以通过 i&-i 得到。
*/
int sum(int i)
{
    int s = 0;
    while(i>0)
    {
        s += BIT[i];
        i -= i&-i;
    }
    return s;
}

/*
	使第i项的值增加x需要从i开始，不断把当前位置i的值增加x，并把i的二进制最低非0位对应的幂加到i上。
*/
void add(int i, int x)
{
    while(i<=n)
    {
        BIT[i] += x;
        i += i&-i;
    }
}

线段树

单点的更新维护

敌军布阵

题目：求区间和

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<cstdio>
#include<iostream>
#include<cstring>

//#define LOCAL
//#define DEBUG
#define MAXN 50005
using namespace std;

int T, n;
int kiss = 1;
int a[MAXN];
char ope[10];
int op1, op2;
struct Tree
{
    int val;
}SegTree[MAXN<<2];

void init()
{
    memset(a, 0, sizeof a);
    memset(SegTree, 0, sizeof SegTree);
}
void PushUp(int root)
{
    SegTree[root].val = SegTree[root<<1].val + SegTree[root<<1|1].val;
}

void build(int root, int l, int r)
{
    if(l==r)
    {
        scanf("%d", &a[l]);
        SegTree[root].val = a[l];
    }
    else
    {
        int mid = l+r>>1;
        build(root<<1, l, mid);
        build(root<<1|1, mid+1, r);
        PushUp(root);
    }
}

int query(int root, int l, int r, int a, int b)
{
    if(a>r || b<l)
        return 0;
    if(a<=l && b>=r)
        return SegTree[root].val;

    int mid = l+r>>1;
    return query(root<<1, l, mid, a, b)+query(root<<1|1, mid+1, r, a, b);
}

void update(int root, int l, int r, int ind, int modifyVal)
{
    if(l==r)
    {
        SegTree[root].val += modifyVal;
        return;
    }
    int mid = l+r>>1;
    if(ind <= mid)
        update(root<<1, l, mid, ind, modifyVal);
    else
        update(root<<1|1, mid+1, r, ind, modifyVal);
    PushUp(root);
}

int main()
{
    #ifdef LOCAL
        freopen("C:\\Users\\Administrator\\Desktop\\in.txt", "r", stdin);
    #endif

    scanf("%d", &T);
    while(T--)
    {
        init();
        scanf("%d", &n);
        build(1, 1, n);
        printf("Case %d:\n", kiss++);
        while(scanf("%s",ope))
        {
            if(ope[0] =='E')
                break;
            scanf("%d%d",&op1, &op2);
            if(ope[0] == 'Q')
                printf("%d\n", query(1,1,n,op1,op2));
            else if(ope[0] == 'A')
                update(1, 1, n, op1, op2);
            else if(ope[0] == 'S')
                update(1, 1, n, op1, -op2);
        }

        #ifdef DEBUG
        for(int i=1; i<=40; i++)
            printf("%2d:%5d\n", i, SegTree[i].val);
        for(int i=1; i<=n; i++)
            printf("%d: %d\n",i, a[i]);
        int ans = query(1,1,n,1,8);
        printf("%d", ans);
        #endif

    }

    return 0;
}


区间的更新维护

Train Seats Reservation

题目：求区间最大值

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define MAXN 100010
#define INF 0x3f3f3f3f
//#define DEBUG
#define DataIn
typedef long long LL;

using namespace std;

int n;
int start, endd, num;

struct Tree
{
    int val;
    int modify;
} SegTree[MAXN<<2];

void PushUp(int root)
{
    SegTree[root].val = max(SegTree[root<<1].val, SegTree[root<<1|1].val);
}

void PushDown(int root, int l, int r)
{
    if(SegTree[root].modify)
    {
        SegTree[root<<1].val += SegTree[root].modify;
        SegTree[root<<1|1].val += SegTree[root].modify;

        SegTree[root<<1].modify += SegTree[root].modify;
        SegTree[root<<1|1].modify += SegTree[root].modify;

        SegTree[root].modify = 0;
    }
}

void build(int root, int l, int r)
{
    if(l==r)
        SegTree[root].val = SegTree[root].modify = 0;
    else
    {
        int mid = l+r>>1;
        build(root<<1, l, mid);
        build(root<<1|1, mid+1, r);
        PushUp(root);
    }
}

void update(int root, int l, int r, int a, int b, int modify)
{
    if(a>r || b<l)
        return;
    if(a<=l && b>=r)
    {
        SegTree[root].val += modify;
        SegTree[root].modify += modify;
        return;
    }
    PushDown(root, l, r);
    int mid = l+r>>1;
    update(root<<1, l, mid, a, b, modify);
    update(root<<1|1, mid+1, r, a, b, modify);
    PushUp(root);
}

int query(int root, int l, int r, int a, int b)
{
    if(a>r || b<l)
        return 0;
    if(a<=l && b>=r)
        return SegTree[root].val;
    PushDown(root, l, r);
    int mid = l+r>>1;
    return max(query(root<<1, l, mid, a, b), query(root<<1|1, mid+1, r, a, b));
}

void init()
{
    memset(SegTree, 0, sizeof(SegTree));
}
int main()
{
#ifdef DataIn
    freopen("C:\\Users\\Administrator\\Desktop\\in.txt", "r", stdin);
#endif

    while(scanf("%d", &n) == 1 && n)
    {
        init();
        //build(1, 1, 100);


        for(int i=1; i<=n; i++)
        {
            scanf("%d%d%d",&start, &endd, &num);
            update(1, 1, 100, start, endd-1, num);
#ifdef DEBUG
            for(int i = 1; i<=100; i++)
            {
                printf("%-4d", SegTree[i].val);
            }
#endif // DEBUG
        }
        printf("%d\n", SegTree[1].val);
    }

    puts("*");
    return 0;
}

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0; i<(n<<1); i++)
{
    // l<r表示队列非空
    while(l<r && sum[i] < sum[que[r-1]])	//入队操作，参照引用中的1
        r--;
    que[r++] = i;

    if(i>=n && sum[que[l]] - sum[i-n] >= 0)
        ans++;
    while(l<r && que[l] <= i-n+1)	//出队操作，将超出区间的出队
        l++;
}

数论

组合数初始化

1
2
3
4
5
6
C[0][0] = 1;
for(int i=1; i<MAXN; i++)
    C[i][0] = 1;
for(int i=1; i<MAXN; i++)
    for(int j=1; j<MAXN; j++)
        C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;

矩阵快速冪

取模 (数组实现)

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
const int MOD = 998244353;

typedef struct
{
    long long m[2][2];
}matrix;
matrix I={1,0,0,1};
matrix P={0,1,1,1};
matrix mul(matrix a,matrix b)
{
    int i,j,k;
    matrix c;
    for(i=0;i<2;i++)
      for(j=0;j<2;j++)
      {
          c.m[i][j]=0;
          for(k=0;k<2;k++)
            c.m[i][j]+=(a.m[i][k]*b.m[k][j])%MOD;
          c.m[i][j]%=MOD;
      }
    return c;
}

matrix qpow_MOD(int n)
{
    matrix a=P,b=I;
    while(n>0)
    {
        if(n&1)
          b=mul(b,a);
        n=n>>1;
        a=mul(a,a);
    }
    return b;
}

不取模 (Vector 实现)

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
typedef vector<int> vec;
typedef vector<vec> mat;

const int MOD = 1e9+7;
mat mul(mat &A, mat &B)
{
    mat C( A.size(),  vec( B[0].size() ) );
    for(int i=0; i<A.size(); i++)
        for(int k=0; k<B.size(); k++)
            for(int j=0; j<B[0].size(); j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;

    return C;

}


mat qpowmod(mat A, LL n)
{
    mat B( A.size(), vec( A.size() ) );
    for(int i=0; i<A.size(); i++)
        B[i][i] = 1;

    while(n)
    {
        if(n & 1)
            B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }

    return B;
}

求组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MOD 10000
const int MAXN = 100; // 组合上限
int c[MAXN][MAXN];    // 组合数
 
void GetGroup()
{
    c[0][0] = c[1][0] = c[1][1] = 1;
    for (int i=2; i<MAXN; ++i)
    {
        c[i][0] = 1;
        for (int j=1; j<=i; ++j) 
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD;  // 求模，防止结果过大
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 200000 + 5;
const int MOD = (int)1e9 + 7;
int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘
void init(){
    inv[1] = 1;
    for(int i = 2; i < N; i ++){
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
    F[0] = Finv[0] = 1;
    for(int i = 1; i < N; i ++){
        F[i] = F[i-1] * 1ll * i % MOD;
        Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;
    }
}
int comb(int n, int m){//comb(n, m)就是C(n, m)
    if(m < 0 || m > n) return 0;
    return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
}

Lucas 定理

代码未曾用过，正确性与否待测试

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
#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;

LL n,m,p=1e9+7;

LL quick_mod(LL a, LL b)
{
    LL ans = 1;
    a %= p;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % p;
            b--;
        }
        b >>= 1;
        a = a * a % p;
    }
    return ans;
}

LL C(LL n, LL m)
{
    if(m > n) return 0;
    LL ans = 1;
    for(int i=1; i<=m; i++)
    {
        LL a = (n + i - m) % p;
        LL b = i % p;
        ans = ans * (a * quick_mod(b, p-2) % p) % p;
    }
    return ans;
}

LL Lucas(LL n, LL m)
{
    if(m == 0) return 1;
    return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%I64d%I64d", &n, &m);
        printf("%I64d\n", 2*Lucas(n-1,m)%p);
    }
    return 0;
}
//Lucas定理，解决C(n,m)%p问题

图论

Dijkstra 算法

使用优先权队列优化

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
struct edge
{
    int to, cost;
};

int V;
int d[MAXN];
vector<edge> G[MAXN];
typedef pair<int, int> P;

void Dijkstra()
{
    fill(d, d+V, INF);

    priority_queue<P, vector<P>, greater<P> > que;

    d[s] = 0;
    que.push( P(0, s) );

    while(!que.empty())
    {
        P p = que.top();
        que.pop();

        int v = p.second;
        if(d[v] < p.first)
            continue;

        for(int i=0; i<G[v].size(); i++)
        {
            edge e = G[v][i];

            if(d[e.to] > d[v] + e.cost)
            {
                d[e.to] = d[v]+e.cost;
                que.push( P(d[e.to], e.to));
            }
        }
    }
}

A* 求第 K 短路

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
using namespace std;
#define INF 0xffffff
#define MAXN 100010
struct node
{
    int to;
    int val;
    int next;
};
struct node2
{
    int to;
    int g,f;
    bool operator<(const node2 &r ) const  
    {  
        if(r.f==f)  
            return r.g<g;  
        return r.f<f;  
    }   
};
node edge[MAXN],edge2[MAXN];
int n,m,s,t,k,cnt,cnt2,ans;
int dis[1010],visit[1010],head[1010],head2[1010];
void init()
{
    memset(head,-1,sizeof(head));
    memset(head2,-1,sizeof(head2));
    cnt=cnt2=1;
}
void addedge(int from,int to,int val)
{
    edge[cnt].to=to;
    edge[cnt].val=val;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
void addedge2(int from,int to,int val)
{
    edge2[cnt2].to=to;
    edge2[cnt2].val=val;
    edge2[cnt2].next=head2[from];
    head2[from]=cnt2++;
}
bool spfa(int s,int n,int head[],node edge[],int dist[])  
{  
    queue<int>Q1;  
    int inq[1010];  
    for(int i=0;i<=n;i++)  
    {  
        dis[i]=INF;  
        inq[i]=0;  
    }  
    dis[s]=0;  
    Q1.push(s);  
    inq[s]++;  
    while(!Q1.empty())  
    {  
        int q=Q1.front();  
        Q1.pop();  
        inq[q]--;  
        if(inq[q]>n)
            return false;  
        int k=head[q];  
        while(k>=0)  
        {  
            if(dist[edge[k].to]>dist[q]+edge[k].val)  
            {  
                dist[edge[k].to]=edge[k].val+dist[q];  
                if(!inq[edge[k].to])  
                {  
                    inq[edge[k].to]++;  
                    Q1.push(edge[k].to);  
                }  
            }  
            k=edge[k].next;  
        }  
    }  
    return true;  
}
int A_star(int s,int t,int n,int k,int head[],node edge[],int dist[]) 
{  
    node2 e,ne;  
    int cnt=0;  
    priority_queue<node2>Q;  
    if(s==t)
        k++;  
    if(dis[s]==INF)  
        return -1;  
    e.to=s;  
    e.g=0;  
    e.f=e.g+dis[e.to];  
    Q.push(e);  

    while(!Q.empty())  
    {  
        e=Q.top();  
        Q.pop();  
        if(e.to==t)//找到一条最短路径  
        {  
            cnt++;  
        }  
        if(cnt==k)//找到k短路  
        {  
            return e.g;  
        }  
        for(int i=head[e.to]; i!=-1; i=edge[i].next)  
        {  
            ne.to=edge[i].to;  
            ne.g=e.g+edge[i].val;  
            ne.f=ne.g+dis[ne.to];  
            Q.push(ne);  
        }  
    }  
    return -1;  
}  
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
            addedge2(b,a,c);
        }
        scanf("%d%d%d",&s,&t,&k);
        spfa(t,n,head2,edge2,dis);
        ans=A_star(s,t,n,k,head,edge,dis);
        printf("%d\n",ans);
    }

    return 0;
}

Prim 算法

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
int cost[MAX_V][MAX_V];
int mincost[MAX_V];
bool used[MAX_V];
int V;

int prim()
{
	for(int i=0; i<V; i++)
    {
        mincost[i] = INF;
        used[i] = false;
    }
    
    mincost[0] = 0;
    int res = 0;
    
    while(true)
    {
        int v = -1;
        //从不属于X的顶点中选取从X到其权值最小的点
        for(int u=0; u<V; u++)
        {
			if( !used[u] && (v==-1 || mincost[u] < mincost[v]) )
                v = u;
        }
        
        if(v == -1)
            break;
        used[v] = true;
        res += mincost[v];
        
        for(int u=0; u<V; u++)
			mincoust[u] = min(mincost[u], cost[v][u]);
    }
    
    return res;
}

Kruskal 算法

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
struct edge
{
    int u, v, cost;
}

bool cmp(const edge& e1, const edge& e2)
{
    return e1.cost < e2.cost;
}

edge es[MAX_E];
int V, E;

int kruskal()
{
	sort(es, es+E, cmp);
    init_ufs(V);
    int res = 0;
    for(int i=0; i<E; i++)
    {
        edge e = es[i];
        if( !same(e.u, e.v) )
        {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    
    return res;
}

常用

离散化

1
2
3
4
sort(a, a+tot);
tot = unique(a, a+tot) - a;
for(int i=0; i<n; i++)
    node[i].y = lower_bound(a, a+tot, node[i].y)-a+1;

数位 dp

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
int dfs(int pos, int state, bool lead, bool limit)
{
    if(pos == -1)
        return 1;	//按题目返回
    if(!limit && !lead && ~dp[pos][state])
        return dp[pos][state];
    
    int up = limit ? a[pos] : 9;
    int ans = 0;
    
    for(int i=0; i<=up; i++)
    {
    	if()
            ans += dfs(pos-1, /*状态表示*/, lead && i==0, limit && i==up);
        else
            ans += dfs.....
    }
    
    if(!limit && !lead)
        dp[pos][state] = ans;
    return ans;
}

int go(int x)
{
    int pos = 0;
    while(x)
    {
        a[pos++] = x%10;
        x /= 10;
    }
    return dfs(pos-1, /*状态*/, true, true);
}

SG 函数 sg (x)=mex {sg (y) | y 是 x 的后继 }

打表法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//f[]：可以取走的石子个数
//sg[]:0~n的SG函数值
//hash[]:mex{}
int f[K],sg[N],hash[N];
void getSG(int n)
{
    memset(sg,0,sizeof(sg));
    for(int i=1; i<=n; i++)
    {
        memset(hash,0,sizeof(hash));
        for(int j=0; f[j]<=i && j < k; j++) //k是f[]的有效长度
            hash[sg[i-f[j]]]=1;
        for(int j=0; ; j++)     //求mes{}中未出现的最小的非负整数
        {
            if(hash[j]==0)
            {
                sg[i]=j;
                break;
            }
        }
    }
}

dfs 法

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

//注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍
//n是集合s的大小 S[i]是定义的特殊取法规则的数组
int s[110],sg[10010],n;
int SG_dfs(int x)
{
    int i;
    if(sg[x]!=-1)
        return sg[x];
    bool vis[110];
    memset(vis,0,sizeof(vis));
    for(i=0;i<n;i++)
    {
        if(x>=s[i])
        {
            SG_dfs(x-s[i]);
            vis[sg[x-s[i]]]=1;
        }
    }
    int e;
    for(i=0;;i++)
        if(!vis[i])
        {
            e=i;
            break;
        }
    return sg[x]=e;
}

黑科技

杜教 BM

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
namespace linear
{
    ll mo=1000000009;
    vector<ll> v;
    double a[105][105],del;
    int k;
    struct matrix
    {
        int n;
        ll a[50][50];
        matrix operator * (const matrix & b)const
        {
            matrix c;
            c.n=n;
            rep(i,0,n)rep(j,0,n)c.a[i][j]=0;
            rep(i,0,n)rep(j,0,n)rep(k,0,n)
            c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%mo)%mo;
            return c;
        }
    }A;
    bool solve(int n)
    {
        rep(i,1,n+1)
        {
            int t=i;
            rep(j,i+1,n+1)if(fabs(a[j][i])>fabs(a[t][i]))t=j;
            if(fabs(del=a[t][i])<1e-6)return false;
            rep(j,i,n+2)swap(a[i][j],a[t][j]);
            rep(j,i,n+2)a[i][j]/=del;
            rep(t,1,n+1)if(t!=i)
            {
                del=a[t][i];
                rep(j,i,n+2)a[t][j]-=a[i][j]*del;
            }
        }
        return true;
    }
    void build(vector<ll> V)
    {
        v=V;
        int n=(v.size()-1)/2;
        k=n;
        while(1)
        {
            rep(i,0,k+1)
            {
                rep(j,0,k)a[i+1][j+1]=v[n-1+i-j];
                a[i+1][k+1]=1;
                a[i+1][k+2]=v[n+i];
            }
            if(solve(n+1))break;
            n--;k--;
        }
        A.n=k+1;
        rep(i,0,A.n)rep(j,0,A.n)A.a[i][j]=0;
        rep(i,0,A.n)A.a[i][0]=(int)round(a[i+1][A.n+1]);
        rep(i,0,A.n-2)A.a[i][i+1]=1;
        A.a[A.n-1][A.n-1]=1;
    }
    void formula()
    {
        printf("f(n) =");
        rep(i,0,A.n-1)printf(" (%lld)*f(n-%d) +",A.a[i][0],i+1);
        printf(" (%lld)\n",A.a[A.n-1][0]);
    }
    ll cal(ll n)
    {
        if(n<v.size())return v[n];
        n=n-k+1;
        matrix B,T=A;
        B.n=A.n;
        rep(i,0,B.n)rep(j,0,B.n)B.a[i][j]=i==j?1:0;
        while(n)
        {
            if(n&1)B=B*T;
            n>>=1;
            T=T*T;
        }
        ll ans=0;
        rep(i,0,B.n-1)ans=(ans+v[B.n-2-i]*B.a[i][0]%mo)%mo;
        ans=(ans+B.a[B.n-1][0])%mo;
        while(ans<0)ans+=mo;
        return ans;
    }
}

int main()
{
    int abcdefg[] = {3,9,20,46,106,244,560,1286,2956,6794,15610,35866,82416,189384};
    vector<ll> V(abcdefg, abcdefg+14);//<-----
    linear::build(V);
    linear::formula();
    ll n;
    while(~scanf("%lld",&n))
    {
        printf("%lld\n",linear::cal(n-1));
    }
    return 0;
}