0%

题目链接

每个细菌都有一个 \(s\) 值。

最初只有一个细菌。每一天原先的细菌都会生一个孩子,且孩子的 \(s\) 值小于母体的 \(s\) 值。

给定 \(n\)\(2^n\) 个数。

判断是否存在一种情况,经过 \(n\) 天后所有细菌的 \(s\) 值为给定的数。

\(n \le 10^5,s_i \le 10^9\)

首先最大的数一定是原始细菌的 \(s\) 值。然后考虑第 \(i\) 天的细菌,它们所选择的 \(s\) 一定要尽可能的大,如果选小了会使它们的后代选择变少。

然后对于每一天产生的每个细菌都按顺序贪心地选择一个尽可能大的值。

同一天选择的顺序是无关紧要的,下面给出证明:

考虑第 \(i\) 天有两个选择的顺序上相邻的细菌 \(a, b\),记它们父亲的 s 分别为 \(A, B (A < B)\)

如果让 \(a\) 先选,且两者的 \(s\) 分别为 \(x,y(x < y)\)

\(y < A\),那么交换顺序后两者的 \(s\) 就为 \(y,x\)

由于 \(a, b\) 在同一天产生,它们在决定后续方案时的地位相同,那么选择的顺序也就无关紧要了。

\(y > A\),那么交换顺序后两者的 s 不变,选择的顺序连方案都不会影响。

为了方便,把父亲编号为 \(j(j<2^i)\) 的细菌编号为 \(j+2^i\)

然后直接按编号顺序确定 \(s\) 就行了,为了支持删除和查找前驱,可以用 multiset 来维护没被选择的 \(s\)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)

using namespace std;

int main() {
cin >> n, m = 1 << n;
multiset <int, greater <int> > s;
For(i, 0, m) s.insert(read());
vector <int> c;
c.push_back(*s.begin()), s.erase(s.begin());
For(i, 0, m) {
For(j, 0, 1 << i) {
auto it = s.upper_bound(c[j]);
if(it != s.end()) c.push_back(*it), s.erase(it);
else return puts("No") < 0;
}
}
return puts("Yes") < 0;
return 0;
}
阅读全文 »

题目链接

\(n\)小写字母和 ? 组成的字符串,问有多少种替换 ? 的方案,使得最终的字符串 \(S_1,S_2,\cdots,S_n\) 满足字典序递增。

\(n \le 50, |S_i| \le 20\)

我的解法:

在每个字符串的第一个字符被确定后发现第一个字符不同的串之间字典是关系已经确定,关系还未确定的(第一个字符相同)的串组成若干区间。

由于区间之间是独立的,将删掉所有串第一个字符后所有区间内部的合法方案数乘起来就是总方案数,而“删掉所有串第一个字符后所有区间内部的合法方案”是一个数量不多的子问题,考虑把“前多少个字符已经删掉”和“区间”作为 DP 的状态。

我们有一个状态的定义:\(f_{i,l,r}\) 表示只从每个串的第 \(i\) 个字符开始考虑,替换第 \(l\) 个到 \(r\) 个串中的 ? ,使得 \(S_l,S_{l+1},\cdots,S_r\) 满足字典序递增的方案数。

然后发现这个状态虽然描述清楚了子问题,但没有很显然的转移。为了实现高效的转移,每次转移时还需要做一个横向 DP,有点麻烦。

所有给这个状态在添加一维 \(k\) 表示第 \(l\) 个到 \(r\) 个串中第 \(i\) 个字符都必须大于等于 \(k\),然后就有很简单的递推:

枚举最小的 \(j \in [l,r]\),使得 \(S_{j}[i] > k\),也就是说 \(\forall x \in [l,j-1]\),有 \(S_x[i] = k\)\(\forall x \in [j,r]\),有 \(S_x[i] \ge k + 1\)\[ f_{i,l,r,k}=\sum\limits_{j=l}^{r+1}f_{i+1,l,j-1,'a'}\cdot f_{i,j,r,k+1} \] 为了处理较短的串提前结束而出现空字符的问题,记 \(k=-1\) 表示允许空字符出现。如果 \(S_l[i]\) 是空字符,那么它就等于 \(f_{i,l+1,r,'a'}\),否则是 \(f_{i,l,r,'a'}\),如果 \(k \ne -1\),那么 \(S_l[i]\) 就不能是空字符。

最后是边界条件:当 \(l > r\) 时值为 \(1\),当 \(l \le r \land k > 'z'\) 时值为 \(0\)

代码如下:

阅读全文 »

题目链接

输入正整数 \(A\)\(B\) \((A \le B < 2^{64})\),求有多少个整数 \(n\) 满足: \(A \le n \le B \land A \le rev(n) \le B\)\(rev(1203)=3021\)\(rev(1050)=501\)

不难看出此题是一个数位 DP,可以把以下作为状态:

  • \(i\) 位已经确定。
  • \(i\) 位与 \(A\) 的大小关系(大于或等于)。
  • \(i\) 位与 \(B\) 的大小关系(小于或等于)。
  • 从最高非零位到第 \(i\) 位共有 \(j\) 位。
  • \(j\) 位翻转后与 \(A\) 的低 \(j\) 位的大小关系(大于,小于或等于)。
  • \(j\) 位翻转后与 \(B\) 的低 \(j\) 位的大小关系(大于,小于或相等)。
  • 当前是否填了非零位。
  • DP 值是合法的填未确定位的方案数。

感觉这个 DP 非常麻烦,状态数太多,有两维还是 \(0/1/2\) 的。

考虑差分一下,记 \(\text{calc}(A, B)\) 表示有多少个整数 \(n\) 满足: \(n<A \land rev(n)<B\)

那么答案是 \(\text{calc}(B+1,B+1)-\text{calc}(A,B+1)-\text{calc}(B+1,A)+\text{calc}(A,A)\)

剩下的问题是实现 \(\text{calc}\) 函数,还是考虑数位 DP,但状态只需存:

  • \(i\) 位已经确定。
  • \(i\) 位与 \(A\) 的大小关系(大于或等于)。
  • 从最高非零位到第 \(i\) 位共有 \(j\) 位。
  • \(j\) 位翻转后与 \(B\) 的低 \(j\) 位的大小关系(小于或不小于)。
  • 当前是否填了非零位。

状态数现在少了两维,而且没有 \(0/1/2\) 的。

现在考虑转移方程:当前的状态是 \({(i,leA,j,leB,hv0)}\), 枚举第 \(i-1\) 位上填 \(s\).

阅读全文 »

给定一个长度为 \(n\) 的序列 \(A\),把 \(A\) 划分为两个非空集合,划分的价值为两个集合的异或和加起来,求可能的最大价值。

\(n \le 10^5,A_i \le 10^{18}\)

设总异或和为 \(sum\) ,若两个集合的异或和分别为 \(S_1,S_2\),由 \(S_1 \oplus S_2 = sum\) 知道,若 \(sum\)\(i\) 位为 \(1\),不管怎么划分,第 \(i\) 位一定产生一次贡献。若 \(sum\)\(i\) 位为 \(0\),那么 \(S_1,S_2\) 在第 \(i\) 位上相同。

考虑 \(sum\)\(0\) 的位,由于 \(S_1,S_2\) 在这些位上是相同的,只需要最大化 \(S_1\) 就行了,由于 \(S_1\) 为全集和空集都不会成为最优解,问题就转化为:

给定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
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
using namespace std;

int n;
long long a[100005], bas[70], su, ans;
int main() {
cin >> n;
rep(i, 1, n) scanf("%lld", &a[i]), su ^= a[i];
rep(i, 1, n) a[i] &= ~su;
rep(i, 1, n) per(j, 59, 0) if(a[i] >> j & 1) {
if(bas[j]) a[i] ^= bas[j];
else {
per(k, j - 1, 0) if(a[i] >> k & 1) a[i] ^= bas[k];
rep(k, j + 1, 59) if(bas[k] >> j & 1) bas[k] ^= a[i];
bas[j] = a[i]; break;
}
}
rep(i, 1, 59) ans ^= bas[i];
cout << su + ans * 2;
return 0;
}
阅读全文 »

给定一个长度为 \(n\) 的序列 \(a\)。有 \(q\) 次询问,每次给出区间 \([L,R]\) ,

\(\max\limits_{L\le l<r\le R}\dfrac{\sum_{i=l}^ra_i}{r-l}\)

\(n\le 10^5,q\le 3\cdot 10^4,|a_i|\le 10^6\)

先把原问题转化成斜率最大值。

\(s_i=\sum_{j=1}^ia_j,\text{点}A_i(i,s_{i-1}),\text{点}B_i(i,s_i)\)

\(\text{原式}=\max\limits_{L\le i < j\le R}\text{Slope}_{A_i,B_j}\)

考虑 \(L=1,R=n\) 时怎么做。

  • 从左往右依次扫描,同时维护 \(A\) 类点的下凸包,每次二分求出 \(B_i\) 过当前凸包上的切点。

    时间复杂度 \(O(n\log n)\)

  • 线性做法:单调队列维护 \(A\) 类点的下凸包,一旦发现队首不是当前 \(B_i\) 过当前凸包上的切点,就将队首弹出。

    这样做可能会导致之后的一些 \(B_i\) 的切点被弹出而失去这些 \(B_i\) 的最优解,但可以证明这样做不会错过全局最优解

    如图,扫描到 \(E\) 时切点已经不是 \(A\) 了,弹出 \(A\) 后会导致扫到 \(F\) 时失去最优解。

    但因为 \(F\) 的切线是 \(AF\), 所以 \(\text{Slope}_{AF}<\text{Slope}_{AB}<\text{Slope}_{BE}\)

    \(AF\) 劣于 \(BE\), \(A\) 已经不可能更新最优解。

考虑分块,令 \(sz=\sqrt n\),每次查询分两类:

  • \(A_i,B_j\) 都在边角(在同一个块或不同块)中时,直接对所有边角使用线性做法求出这类最优解。

  • \(A_i,B_j\) 至少有一个在大块中时。

    预处理 \(pre_{i,j}=\max\limits_{sz\cdot i\le I< J \le j}\text{Slope}_{A_I,B_J},suf_{i,j}=\max\limits_{j\le I<J\le sz\cdot i}\text{Slope}_{A_I,B_J}\)

    预处理方式也使用线性做法。

    \(pre_{\lceil\frac L{sz}\rceil,R},suf_{\lfloor\frac R{sz}\rfloor,L}\) 更新答案。

综上,时间复杂度 \(O(n\sqrt n)\)

代码:

阅读全文 »

题目链接

原题题意:给你三个正整数 \(a\)\(b\)\(c\),问多少个非负整系数多项式 \(F\), 满足 \(F(a)=b \land F(b)=c\)

\(1 \le a, b, c \le 10^{18}\)

\(a=1,b=1\) 答案显然。

否则因为非负整系数的限制,多项式系数是 \(\log\) 级别的。

我们考虑一个更一般的问题:问多少个非负整系数多项式 \(F\), 满足 \[ F(a)=x \land F(b)=y \land x \le b \]\(F\) 的常数项为 \(V\)

根据 \(F(a)=x\)\(F(b)=y\) 知道 \(V \le x, V \equiv y\ (mod\ b)\)

分两种情况。

  1. \(x=b \land b\ |\ y\) 时,则 \(V=0 \lor V=x\)

    \(V=x\),因为 \(F(a)=x\), 所以 \(F\) 只能是常函数 \(F(x)=V\),当 \(x \ne y\) 时无解。

    另一种情况,因为 \(F(a)-V=x-V\),所以 \(a\) 要能整除 \(x-V\),如果不整除就无解。

    否则令 \(G(x)=\dfrac{F(x)-V}x\),有 \(G(a)=\dfrac{x-V}a,G(b)=\dfrac{y-V}b\)

    显然 \(\dfrac{x-V}a \le x \le b\),因此就转化为了一个子问题。

  2. \(x < b \lor b \not |\ y\) 时,显然 \(V=y \mod b\),可以转化为子问题。

边界条件是 \(xy=0\), 这意味着无解(\(F(x)=0\) 不算合法)。

然后就可以求出多项式的数量了。

1
2
3
4
5
6
7
8
9
10
11
typedef long long ll;
ll a, b, c;
find(ll x, ll y) {
if(!x || !y) return 0; ll v = y % b;
return ((x - v) % a ? 0 : find((x - v) / a, (y - v) / b)) + (x == y);
}
main() {
scanf("%lld%lld%lld", &a, &b, &c);
if(a == 1 && b == 1) puts(c > 1 ? "0" : "inf");
else printf("%d", find(b, c));
}
阅读全文 »

读入输出非负整数版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int read() {
const int M = 1e6;
static streambuf* in = cin.rdbuf();
#define gc (p1 == p2 && (p2 = (p1 = buf) + in -> sgetn(buf, M), p1 == p2) ? -1 : *p1++)
static char buf[M], *p1, *p2;
int c = gc, r = 0;
while(c < 48) c = gc;
while(c > 47) r = r * 10 + (c & 15), c = gc;
return r;
}
void wrt(int x) {
static streambuf* out = cout.rdbuf();
#define pc out -> sputc
static char c[11]; int sz = 0;
do c[++sz] = x % 10, x /= 10; while(x);
while(sz) pc(c[sz--] + 48);
pc(10);
}

注:main 函数开头请加入这 \(3\) 句话

1
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

其实后两句可以选择性添加,见文末。

不可与 cin, cout, scanf, printf, gets, puts, getchar, putchar 等其他读入输出方式同时使用

其实也不是全部不能同时使用,见文末。

read 函数只能通过文件输入或者标准输入完后按 Ctrl + Z (仅 WIN 10)。

读入输出整数版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int read() {
const int M = 1e6;
static streambuf* in = cin.rdbuf();
#define gc (p1 == p2 && (p2 = (p1 = buf) + in -> sgetn(buf, M), p1 == p2) ? -1 : *p1++)
static char buf[M], *p1, *p2;
int c = gc, r = 0, f = 1;
while(c < 48) { if(c == 45) f = -1; c = gc; }
while(c > 47) r = r * 10 + (c & 15), c = gc;
return r * f;
}
void wrt(int x) {
static streambuf* out = cout.rdbuf();
#define pc out -> sputc
static char c[11]; int sz = 0;
if(x < 0) pc(45), x = -x;
do c[++sz] = x % 10, x /= 10; while(x);
while(sz) pc(c[sz--] + 48);
pc(10);
}
阅读全文 »

给定一棵 \(n\) 个节点的树,每个节点 \(u\) 上有一个可容纳 \(k_u\) 个球的桶,\(m\) 次操作:给一个节点到根路径上的所有节点的桶内放一个有颜色的球,如果节点的桶满了则不能放进这个节点,\(q\) 次询问某节点的桶内的球有多少种颜色。

\(n, m, q \le 10^5\)

因为节点上的桶有容量,所以只有某时刻前的操作会对该节点产生影响。

\(Max_u\) 表示\(u\)号节点上的桶恰好装满的时刻,考虑求出每个节点的 \(Max\),将所有询问以 \(Max\) 为关键字升序排序,问题就转化为单点加球,子树查询颜色数的问题。

  • \(Max\)

    \(Max_u\) 按照定义是所有覆盖 \(u\) 节点的操作的时间第 \(k_u\) 小,而所有覆盖 \(u\) 节点的操作是下端点在 \(u\) 子树内的操作,如果能将这些操作放到同一区间上,就可以用主席数实现区间第 \(k\) 小。

    如果对每个点都至多有一次操作以它为下端点,将这个节点的 dfs 序作为对应操作的下标,操作的时间为值,问题就转化成了区间第 \(k\) 小。

    但对每个点都可能作为多次操作的下端点,需要将每个结点扩充成一个区间,区间长度为这个节点对应操作的数量,然后就可以类别上一段所说的方法求出 \(Max\)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    rep(i, 1, m) {
    scanf("%d%d", &x[i], &c[i]);
    tim[dfn[x[i]]].push_back(i);
    }
    rep(i, 1, n) {
    R[i] = R[i-1]; //R[i] 是 dfs 序为 i 的节点对应区间的右端点
    for(int t : tim[i]) SegTree::upd(t, R[i]), R[i]++;
    }
    rep(i, 1, n) Max[i] = SegTree::qry(k[i], R[dfn[i]-1], R[suf[i]]);
  • 单点加球,子树查询颜色数的问题:

    考虑静态查询子树查询颜色数的问题,做法是每个有颜色的结点处 \(+1\),每个结点和同种颜色, dfs 序小于这个结点且 dfs 序最大的结点的 lca\(-1\)

    如图

    .jpg

    \(4,5\) 号结点的 lca\(1\) 号结点处 \(-1\)

    \(5,6\) 号结点的 lca\(1\) 号结点处 \(-1\)

    ...

    然后查询子树和就是子树颜色数。

    再考虑单点加球,子树查询颜色数的问题。其实只需要加一个 set 数组和树状数组,set 数组维护当前每种颜色结点的 dfs 序,单点加球时在 set 中找出前驱和后继,这个点处 \(+1\),它和前驱的 lca\(-1\),和后继的 lca\(-1\),前驱和后继的 lca\(+1\),然后查询子树和。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int ci = c[i], dfnx = dfn[x[i]];
    if(s[ci].count(dfnx)) return;
    s[ci].insert(dfnx), add(dfnx, 1);
    auto it = s[ci].find(dfnx);
    int pre = 0, suf = 0;
    if(it != s[ci].begin()) pre = *(--it), it++;
    if(it != --s[ci].end()) suf = *(++it), it--;
    if(pre) upd(pre, dfnx, -1);
    if(suf) upd(suf, dfnx, -1);
    if(pre && suf) upd(pre, suf, 1);

时间复杂度 \(O(n\log 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
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
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)

using namespace std;
const int N = 1e5 + 5;
int n, m, q, k[N];

namespace Seg {
int sz, T[N], c[N*20], ls[N*20], rs[N*20];
#define mid ((l + r) >> 1)
#define lch l, mid, ls[o]
#define rch mid + 1, r, rs[o]
void upd(int oo, int p, int l, int r, int& o) {
c[o = ++sz] = c[oo] + 1, ls[o] = ls[oo], rs[o] = rs[oo];
if(p > mid) upd(rs[oo], p, rch);
else if(l ^ r) upd(ls[oo], p, lch);
}
int qry(int k, int l, int r, int o, int oo) {
if(l == r) return k > 1 ? m : l;
int cnt = c[ls[o]] - c[ls[oo]];
return k <= cnt ? qry(k, lch, ls[oo]) : qry(k - cnt, rch, rs[oo]);
}
void upd(int p, int t) {
upd(T[t], p, 0, m, T[t+1]);
}
int qry(int k, int l, int r) {
return qry(k, 0, m, T[r], T[l]);
}
};
namespace Tree {
int idx, dfn[N], suf[N], rnk[N], d[N], fa[20][N];
vector <int> G[N];
void dfs(int u) {
rnk[dfn[u] = ++idx] = u;
rep(i, 1, 19) fa[i][u] = fa[i-1][fa[i-1][u]];
for(int v : G[u]) if(v ^ fa[0][u])
fa[0][v] = u, d[v] = d[u] + 1, dfs(v);
suf[u] = idx;
}
int lca(int u, int v) {
if(d[u] < d[v]) swap(u, v);
per(i, 19, 0) if(d[u] - (1 << i) >= d[v]) u = fa[i][u];
if(u == v) return u;
per(i, 19, 0) if(fa[i][u] ^ fa[i][v]) u = fa[i][u], v = fa[i][v];
return fa[0][u];
}

int Max[N], R[N], x[N], c[N], g[N];
vector <int> tim[N];
void pretreat() {
cin >> m;
rep(i, 1, m) {
scanf("%d%d", &x[i], &c[i]), g[i] = c[i];
tim[dfn[x[i]]].push_back(i);
}
sort(g + 1, g + m + 1);//离散化颜色
rep(i, 1, m) c[i] = lower_bound(g + 1, g + m + 1, c[i]) - g;
rep(i, 1, n) {
R[i] = R[i-1];//R[i] 是 dfs 序为 i 的节点对应区间的右端点
for(int t : tim[i]) Seg::upd(t, R[i]), R[i]++;
}
rep(i, 1, n) Max[i] = Seg::qry(k[i], R[dfn[i]-1], R[suf[i]]);
}

int C[N];
void add(int i, int v) {
for(; i <= n; i += i & -i) C[i] += v;
}
int qry(int i, int r = 0) {
for(; i; i &= i - 1) r += C[i];
return r;
}
int Qry(int u) {
return qry(suf[u]) - qry(dfn[u] - 1);
}

set <int> s[N];
void upd(int u, int v, int x) {
add(dfn[lca(rnk[u], rnk[v])], x);
}
void ins(int i) {//单点加球
int ci = c[i], dfnx = dfn[x[i]];
if(s[ci].count(dfnx)) return;
s[ci].insert(dfnx), add(dfnx, 1);
auto it = s[ci].find(dfnx);
int pre = 0, suf = 0;
if(it != s[ci].begin()) pre = *(--it), it++;
if(it != --s[ci].end()) suf = *(++it), it--;
if(pre) upd(pre, dfnx, -1);
if(suf) upd(suf, dfnx, -1);
if(pre && suf) upd(pre, suf, 1);
}
};

int x[N], u, v, ans[N]; vector <int> id[N];
int main() {
cin >> n;
rep(i, 2, n) {
scanf("%d%d", &u, &v);
Tree::G[u].push_back(v);
Tree::G[v].push_back(u);
}
Tree::dfs(1);
rep(i, 1, n) scanf("%d", &k[i]);
Tree::pretreat();
cin >> q;
rep(i, 1, q) scanf("%d", &x[i]), id[Tree::Max[x[i]]].push_back(i);
rep(i, 1, m) {
Tree::ins(i);
for(int j : id[i]) ans[j] = Tree::Qry(x[j]);
}
rep(i, 1, q) printf("%d\n", ans[i]);
return 0;
}
阅读全文 »

题目链接

给定 \(n, k\)

求出从 \(0,1,2,\cdots,n-1\) 中选出 \(k\) 个总和能被 \(n\) 整除的数的方案数,模 \(10^9+7\)

\(n \le 10^9, k \le 1000\)

我们先确定 \(k - 1\) 个数的值,再解出最后一个数,这样可能导致最后一个数被选 \(2\) 次。

考虑容斥,减去钦定它选了 \(2\) 次的方案数,加上钦定它选了 \(3\) 次的方案数,\(\cdots\)

钦定最后一个数 \(x\) 出现了至少 \(t\) 次,那么设另外 \(k - t\) 个数的和为 \(S\),则方程: \[ tx + S \equiv 0\pmod n \]\([0, n)\) 范围内,方程有解条件为 \[ \gcd(t,n)|S \] 解的个数为 \[ \gcd(t,n) \]\(f_{i,S}\) 表示 \(i\) 个数的和被 \(S\) 整除的方案数,则 \[ f_{i,S} = \frac 1i \sum_{j = 1}^i (-1)^{j+1} \frac nS\gcd(j,S) f_{i-j,\gcd(j,S)} \]\(\frac nS\) 是因为我们是要求 \([0,\ n)\) 中解的个数, \(\frac 1i\) 是因为我们相当于钦定最后一个数为特殊数,而实际要求的是无序方案。 观察转移方程,显然除了 \(S=n\) 的情况,一定有 \(S|(k-i)\),故总状态数为 \(k\log k\),即复杂度为 \(O(k^2\log 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
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;
using ll = long long;
const int N = 1005;
const ll P = 1e9 + 7;

ll inv[N], f[N][N];

struct TheCowDivOne {
int find(int n, int k) {
inv[1] = 1;
rep(i, 2, k) inv[i] = (P - P / i) * inv[P % i] % P;
rep(s, 1, k) f[0][s] = 1;
rep(i, 1, k) rep(s, 1, k) if((k - i) % s == 0) {
ll& re = f[i][s];
rep(j, 1, i) {
int g = __gcd(j, s);
(re += (j & 1 ? 1 : -1) * n / s * g * f[i - j][g]) %= P;
}
re = re * inv[i] % P;
}
ll as = 0;
rep(j, 1, k) {
int g = __gcd(j, n);
(as += (j & 1 ? 1 : -1) * g * f[k - j][g]) %= P;
}
return (as + P) * inv[k] % P;
}
};

阅读全文 »

Play

生命游戏中,对于任意细胞,规则如下:

  • 每个细胞有两种状态 - 存活或死亡,每个细胞与以自身为中心的周围八格细胞产生互动

  • 当前细胞为存活状态时,当周围的存活细胞低于2个时(不包含2个),该细胞变成死亡状态。(模拟生命数量稀少)

  • 当前细胞为存活状态时,当周围有2个或3个存活细胞时,该细胞保持原样。

  • 当前细胞为存活状态时,当周围有超过3个存活细胞时,该细胞变成死亡状态。(模拟生命数量过多)

  • 当前细胞为死亡状态时,当周围有3个存活细胞时,该细胞变成存活状态。(模拟繁殖)

    按规则处理当前的细胞图,可以得到下一代的细胞图,周而复始。

我的一些发现。 1. 核心元件:结构简单,演变 230 轮。

1
2
3
  ■   ■
■ ■ ■ ■
■ ■

  1. 循环周期优美的元件:

    1
    2
    3
      ■   ■          ■   ■
    ■ ■ ■ ■ 3 格 ■ ■ ■ ■
    ■ ■ ■ ■

  2. 演变 650 轮(放 4 个滑翔机)的元件:

    1
    2
    3
      ■   ■          ■   ■
    ■ ■ ■ ■ 7 格 ■ ■ ■ ■
    ■ ■ ■ ■

  3. 演变 2500 轮(放 20 个滑翔机)的元件:

    1
    2
    3
      ■   ■          ■   ■
    ■ ■ ■ ■ 10 格 ■ ■ ■ ■
    ■ ■ ■ ■

  4. 有点长的循环周期:

    1
    2
    3
    ■    ■           ■   ■
    ■ ■ ■ ■ 2 格 ■ ■ ■ ■
    ■ ■ ■ ■

阅读全文 »