发表更新数据结构与算法3 分钟读完 (大约522个字)

杜教BM模板

用于求线性递推式第n项，扔进前k+x项即可

Code

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 <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<ll> VI;
typedef pair<ll, ll> PII;
const ll mod = 10000;
ll powmod(ll a, ll b) {
  ll res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
ll _, n;
namespace linear_seq {
const ll N = 10010;
ll res[N], base[N], _c[N], _md[N];
vector<ll> Md;
void mul(ll *a, ll *b, int k) {
  rep(i, 0, k + k) _c[i] = 0;
  rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] =
      (_c[i + j] + a[i] * b[j]) % mod;
  for (ll i = k + k - 1; i >= k; i--)
    if (_c[i])
      rep(j, 0, SZ(Md)) _c[i - k + Md[j]] =
          (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
  rep(i, 0, k) a[i] = _c[i];
}
ll solve(ll n, VI a, VI b) {
  ll ans = 0, pnt = 0;
  ll k = SZ(a);
  assert(SZ(a) == SZ(b));
  rep(i, 0, k) _md[k - 1 - i] = -a[i];
  _md[k] = 1;
  Md.clear();
  rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);
  rep(i, 0, k) res[i] = base[i] = 0;
  res[0] = 1;
  while ((1ll << pnt) <= n) pnt++;
  for (ll p = pnt; p >= 0; p--) {
    mul(res, res, k);
    if ((n >> p) & 1) {
      for (ll i = k - 1; i >= 0; i--) res[i + 1] = res[i];
      res[0] = 0;
      rep(j, 0, SZ(Md)) res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
    }
  }
  rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;
  if (ans < 0) ans += mod;
  return ans;
}
VI BM(VI s) {
  VI C(1, 1), B(1, 1);
  ll L = 0, m = 1, b = 1;
  rep(n, 0, SZ(s)) {
    ll d = 0;
    rep(i, 0, L + 1) d = (d + (ll)C[i] * s[n - i]) % mod;
    if (d == 0)
      ++m;
    else if (2 * L <= n) {
      VI T = C;
      ll c = mod - d * powmod(b, mod - 2) % mod;
      while (SZ(C) < SZ(B) + m) C.pb(0);
      rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
      L = n + 1 - L;
      B = T;
      b = d;
      m = 1;
    } else {
      ll c = mod - d * powmod(b, mod - 2) % mod;
      while (SZ(C) < SZ(B) + m) C.pb(0);
      rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
      ++m;
    }
  }
  return C;
}
ll gao(VI a, ll n) {
  VI c = BM(a);
  c.erase(c.begin());
  rep(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod;
  return solve(n, c, VI(a.begin(), a.begin() + SZ(c)));
}
};  // namespace linear_seq
int main() {
  while (~scanf("%lld", &n) && n != -1) {
    vector<ll>v;
       v.push_back(0);
       v.push_back(1);
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(5);
        v.push_back(8);
        v.push_back(13);
        v.push_back(21);
        v.push_back(34);
      printf("%lld\n", linear_seq::gao(v, n));
  }
  return 0;
}
发表更新每日一题3 分钟读完 (大约411个字)

每日一题：皇家烈焰（线性dp）

题意

现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种

对于一个格子，里面会有以下几种字符：

0：这个格子没有烈焰，且其左右两个格子均没有烈焰

阅读更多
发表更新每日一题2 分钟读完 (大约247个字)

每日一题：Two Graphs（暴力）

题意

给一个小图和一个大图，问大图有多少个子图形状和小图一样。

solution

最多只有8个点，因为每个点标号可能不一样，因此可以全排列枚举所有点的位置，然后判断小图有的边大图是否也有（因为原来边的属性还在），并通过hash进行去重。

阅读更多
发表更新每日一题4 分钟读完 (大约586个字)

每日一题：Different Integers（树状数组/莫队）

题意

给定长度为 $n$ 的数组，$q$ 次询问 $[1,l]+[r,n]$ 组成的新数组中不相同的元素个数。$(1<=n,q<=1e5)$

solution1

一眼莫队题，主要是要想怎么样把它变成一个连续的区间。其实只要把整个数组再复制一遍接上就可以了，则原来查询的 $r$ 变为 $l$，$l$ 变为 $l+n$，区间连续。

阅读更多
发表更新每日一题2 分钟读完 (大约304个字)

课程安排（状压dp）

题意：让你安排课程，保证每学期的课不能冲突，问最少需要几个学期。

solution：

因为 n 只有15，可以考虑状压dp。用二进制每位的1/0表示当前是否学习该课程，可以得到 n 个二进制位，那么所有的可能性有 1<<n 种，预处理 g[s] 表示 s 所代表课程的是否可以在一个学期内学完（对于当前要学的所有课程的学时进行标记，若有重复标记则不可能在一学期学完），f[s] 维护学完当前课程所花费的最少学期，枚举子集进行转移。
答案的状态应该是所有课全部修完，即 $f[(1<<n)-1]$。时间复杂度 $O(2^n m n)$。

阅读更多
发表更新C++21 分钟读完 (大约3109个字)

C++11新特性

nullptr

nullptr 出现的目的是为了替代 NULL。传统 C++ 会把 NULL, 0 视为同一种东西，有些编译器会将 NULL 定义为 ((void*)0)，有些则会直接将其定义为 0。C++ 不允许直接将 void 隐式转换到其他类型，但如果 NULL 被定义为 **((void)0)，那么当编译 char ch = NULL;* 时，NULL 只好被定义为 0。而这依然会产生问题，将导致了 C++ 中重载特性会发生混乱，考虑：

1
2
void foo(char *);
void foo(int);

对于这两个函数来说，如果 NULL 又被定义为了 0 那么 foo(NULL); 这个语句将会去调用 foo(int)，从而导致代码违反直观。为了解决这个问题，C++11 引入了 nullptr 关键字，专门用来区分空指针、0。nullptr 的类型为 nullptr_t，能够隐式的转换为任何指针或成员指针的类型，也能和他们进行相等或者不等的比较。

阅读更多
发表更新每日一题3 分钟读完 (大约392个字)

每日一题：粉刷匠（背包dp）

题意

n 条木板，每条木板都被分成 m 段且每一段都有要涂的颜色，有 t 次机会涂色，每次可以选择一条木板的连续一段涂成同一种颜色，问最多可以涂对多少段。

solution

考虑四维dp的做法。$dp[i][j][k][0/1]$ 代表到第 $i$ 条第 $j$ 段时涂 $k$ 次，当前段涂红或蓝$(0/1)$的最大正确数，可以得到转移方程：

阅读更多
发表更新每日一题4 分钟读完 (大约546个字)

每日一题：滑雪与时间胶囊（最小生成树）

题意

给定一个 $n$ 个点 $m$ 条边图，只能从点权高的点走到低的，且可以不计路程的瞬移至之前走过的某个点，求经过最多点的最短路径。

solution

求经过最多点显然直接bfs，建图的时候建高到低的单向边即可，（值得注意的是，若点权相同，则为相互可达的，需要建双向边）。然后根据bfs遍历可以走到的点，将走过的边加入边集，建一个新图出来。为了使路径最短，考虑最小生成树，但需要满足题目的条件，因此我们对新的图进行排序，以高度为第一关键字从大到小排，再以路径长度为第二关键字从小到大排，这样可以保证点最多的同时路径最短。

阅读更多
发表更新每日一题2 分钟读完 (大约352个字)

每日一题：换个角度思考（树状数组）

题意

给定一个长度为 $(1<=n<=1e5)$ 的数组，$(1<=q<=1e5)$ 次询问查询区间 $[l,r]$ 内 $<=k$ 的元素个数。

solution

考虑树状数组。我们在查询区间 $<=k$ 的个数时，为了更好计数，这个区间应该不包含 $>k$ 的元素才行。因此我们不妨离线，将询问的 $k$ 从小到大排序，将数组也从小到大排序，这样从小到大处理询问，每次处理时只将 $<=k$ 的数挂到树的对应下标上（因为询问的 $k$ 是从小到大的，因此之前树上的数一定比当前询问的 $k$ 要小），维护答案为 $query(r) - query(l-1)$。

阅读更多

链接

分类

最新文章

归档

标签

C++内存管理1
C++基础3
C++面向对象3
DFS1
JVM3
Java反射1
Java基础2
Java多线程1
Makefile1
MySQL1
RMQ1
STL7
Vim1
二分2
动态规划14
区间dp3
博弈论1
回文1
图论2
多校训练3
字典树1
并查集4
思维15
操作系统2
数学7
最小生成树1
树2
树形dp2
树状数组5
状压dp3
线性dp1
网络编程1
背包dp2
计数dp5
计算机网络1
记忆化搜索2
设计模式2
贪心10
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×