集合

时间限制: 2Sec   内存限制: 256MB
标准输入   标准输出

Description

要选一个 的子集使得假如 aabb 在所选集合里且 那么 a+b2\frac{a+b}{2} 也在所选集合里。问有多少种方案。

Input

第一行 cc 数据组数。接下来 cc 行每行一个 nn

Output

每组数据一行一个数表示方案数。由于答案可能很大,你只需要输出答案对 21282128 取模后的结果。

Sample Input

4
1
2
3
100

Sample Output

4
1
2
3
100
测试点编号 cc 的范围 nn 的范围
11 =1=1
22 =1=1
33 =1=1
44 =1=1
55 =1=1
66 =1=1
77 =1000=1000
88 =100000=100000
99 =1=1
1010 =100000=100000

数据范围 样例解释 第一组:{},{1}\{\},\{1\} 第二组:{},{1},{2},{1,2}\{\},\{1\},\{2\},\{1,2\} 第三组:除了 {1,3}\{1,3\} 以外的所有 第四组:我想到了一个绝妙的解释,可惜这里空间太小,写不下。

Solution 考试的时候上oeis找到了递推式,然后非常好奇地玩了两个小时……

递推式:an=an1+dn+1=n+i=1ndia_{n}=a_{n-1}+d_{n}+1=n+\sum_{i=1}^{n}d_{i} (其中 did_{i} 表示 的奇约数个数)

对于 dnd_{n} 的计算,在oeis上同样有一条计算公式:

然后我就这么做好像就愉快地水了70(不写数论分块因为怕挂掉)。

正如题解所说,欧拉筛可以筛 dd ,然后 O(n)O(n) 的预处理就很好做了。还了解到一种做法,考试的时候曾想过但没去做,就是用埃氏筛了,非常好写但是复杂度…… 考虑每个 dd ,统计每个奇数对它的贡献。预处理复杂度 O(n ln(n))O(n~ln(n)),好像是可以卡卡进去。

递推式正确性的证明: 显然最后构成的集合中,元素必定成等差数列,且公差为奇数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
const int N=10000000;int n,c,a[N+2];long long f[N+2];
int main(){scanf("%d",&c);for(re i=3;i<=N;i+=2)for(re j=i;j<=N;j+=i)++a[j];rep(i,1,N)a[i]+=a[i-1]+1;a[0]=1;rep(i,1,N)f[i]=f[i-1]+1+a[i-1];while(c--){scanf("%d",&n);printf("%lld\n",f[n]);}}
/**************************************************************
Problem: 3855
User: ZqlwMatt
Language: C++
Result: 正确
Time:1460 ms
Memory:118144 kb
****************************************************************/

最近公共祖先

时间限制: 1Sec   内存限制: 256MB
标准输入   标准输出

Description 给定一棵 nn 个节点的有根树,节点标号为 ,其中根节点为11号节点。每个节点都对应着一种颜色(黑/白)和一个固定的权值,初始时所有节点的颜色都为白色。现在你需要实现以下两种操作:

Modify v:将节点 vv 的颜色修改为黑色。 Query v:给定 vv,对于任意黑色节点 uu,求出 lca(u,v)lca(u,v) 的权值最大值。若不存在黑色节点,输出

Input 见输入样例

Output64 见输出样例

Sample Input

7 7
4 3 5 7 6 5 2
1 4
2 1
7 5
6 2
2 5
3 4
Query 1
Modify 2
Modify 4
Query 3
Modify 2
Modify 5
Query 6

Sample Output

-1
7
4

考虑我们将一个节点(x)染成黑色对操作二的贡献,首先对于 x(蓝色结点) 的子树,答案可能 更新为 val[x]。
同样,对于这些节点在操作二下也会产生贡献。
img

每个框对应每组更新的节点

每组更新的节点的值应该表示为 val->val[fa[x]], x->fa[x]

为了方便地表示区间节点,即使其编号连续,我们可以使用 dfs 序。
但这么操作…复杂度岂不爆炸?
不,我们发现,每个节点至多只会被更新一次,若 x 的节点 fa[x] (x->fa[x]) 已经被更新过了,那么再次更新就没意义啦,因为…每组的更新值都为其本身权值 val[x]。

那么查询点 x 的时候只需在包含其区间的 tag 中取最大值即可。

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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
const int N = 100002;
inline void read(int &x) {
x=0;
int f=1;char ch=getchar();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
int cnt=0, nxt[N<<1], head[N], to[N<<1];
inline void add(int u, int v)
{nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v;}
int n, m, w[N], fa[N], id[N], skd, vis[N];
int L[N], R[N], siz[N];
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
int tag[N<<2];
void dfs(int u, int f=0) {
fa[u]=f, L[u]=++skd, siz[u]=1;
int v;
for(int i=head[u];i;i=nxt[i]) {
v = to[i];
if(v==f) continue;
dfs(v, u), siz[u]+=siz[v];
}
R[u] = L[u]+siz[u]-1;
}
void modify(int x, int l, int r, int ll, int rr, int val) {
if(tag[x]>=val) return ;
if(l==ll && r==rr) { tag[x]=val;return ;}
int mid = (l+r)>>1;
if(rr<=mid) modify(lson(x), l, mid, ll, rr, val);
else if(ll>mid) modify(rson(x), mid+1, r, ll, rr, val);
else {
modify(lson(x), l, mid, ll, mid, val);
modify(rson(x), mid+1, r, mid+1, rr, val);
}
}
void update(int u) {
modify(1, 1, n, L[u], R[u], w[u]);
while(!vis[u]&&fa[u]) {
int p = fa[u]; vis[u]=1;
if(L[p]<L[u]) modify(1, 1, n, L[p], L[u]-1, w[p]);
if(R[p]>R[u]) modify(1, 1, n, R[u]+1, R[p], w[p]);
u = p;
}
}
int query(int x, int l, int r, int z) {
if(l==r) return tag[x];
int mid = (l+r)>>1;
if(z<=mid) return std::max(tag[x], query(lson(x), l, mid, z));
else return std::max(tag[x], query(rson(x), mid+1, r, z));
}
int main() {
read(n), read(m);
int u, v;
rep(i,1,n) read(w[i]);
rep(i,2,n)
read(u), read(v), add(u, v), add(v, u);
dfs(1);
memset(tag, -1, sizeof tag);
static char opt[10];
while(m--) {
scanf("%s", opt), read(v);
if(*opt=='M') update(v);
else printf("%d\n", query(1, 1, n, L[v]));
}
return 0;
}
/**************************************************************
Problem: 4235
User: ZqlwMatt
Language: C++
Result: 正确
Time:236 ms
Memory:11588 kb
****************************************************************/

降雷皇

时间限制: 1Sec   内存限制: 512MB
标准输入   标准输出

Description

题意:给定 nn 个数的数列,请求出最长不下降子序列长度,和方案数对 123456789123456789 取模的结果。

Input

第一行两个整数 nntypetypetypetype 表示数据类型
第二行 nn 个整数。

Output

第一行一个整数表示最长不下降子序列的长度。
如果 type=1type=1 则需要输出第二行,表示方案数,对 123456789123456789 取模。

Sample Input

5 1
1 3 2 5 4

Sample Output

3
4

数据范围

对于 20%20\% 的数据
对于 40%40\% 的数据
对于另外 20%20\% 的数据 type=0type=0,对于另外 20%20\% 的数据保证最长不下降子序列长度
对于 100%100\% 的数据 , 每个数不超过 100000100000

Solution

第一问有大家熟悉的 O(log n)O(log~n) 的做法。

对于第二问,可以用dp转移,总复杂度 O(n2)O(n^{2})

1
2
3
4
5
6
7
f[], g[] // f表示长度 g表示方案数
for(int i=1;i<=n;++i)
for(int j=1;j<i;++j)
if(a[i]>=a[j]) {
if(f[i]==f[j]+1) d[i]+=d[j];
else if(f[i]<f[j]+1) f[i]=f[j]+1, d[i]=d[j];
}

继续优化,注意到每个数不小于 100000100000,我们用线段树维护区间最大值和最大值方案数。
那么总复杂度O(n log n)O(n~log~n)

详见代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define drep(i,a,b) for(re i=(a);i>=(b);--i)
#define pii pair<int,int>
#define fi first
#define se second
typedef long long ll;
const int N = 100002, M = N<<2;
const ll p = 123456789;
int n, a[100002], f[100002];
int getlis();
pair<int, ll> v[M]; // Max s
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
inline void update(int x) {
v[x].fi = max(v[lson(x)].fi, v[rson(x)].fi);
v[x].se = 0;
if(v[lson(x)].fi==v[x].fi) v[x].se+=v[lson(x)].se;
if(v[rson(x)].fi==v[x].fi) v[x].se+=v[rson(x)].se;
if(v[x].se>=p) v[x].se-=p;
}
void modify(int x, int l, int r, int z, int Max, int s) {
if(l==r) {
if(Max>v[x].fi) v[x]=make_pair(Max, s);
else if(Max==v[x].fi) {
v[x].se+=s;
if(v[x].se>=p) v[x].se-=p;
}
return ;
}
int mid = (l+r)>>1;
if(z<=mid) modify(lson(x), l, mid, z, Max, s);
else modify(rson(x), mid+1, r, z, Max, s);
update(x);
}
pii query(int x, int l, int r, int ll, int rr) {
if(l==ll && r==rr) return v[x];
int mid = (l+r)>>1;
if(rr<=mid) return query(lson(x), l, mid, ll, rr);
else if(ll>mid) return query(rson(x), mid+1, r, ll, rr);
else {
pii tmp1 = query(lson(x), l, mid, ll, mid);
pii tmp2 = query(rson(x), mid+1, r, mid+1, rr);
int Max = max(tmp1.fi, tmp2.fi);
int num=0;
if(tmp1.fi==Max) num+=tmp1.se;
if(tmp2.fi==Max) num+=tmp2.se;
if(num>=p) num-=p;
return make_pair(Max, num);
}
}
int res, ans, type;
int main() {
scanf("%d%d", &n, &type);
rep(i,1,n) scanf("%d", a+i);
cout << getlis() << endl;
if(type!=1) return 0;
modify(1, 1, 100000, a[1], 1, 1);
rep(i,2,n) {
if(a[i]==1) {
modify(1, 1, 100000, 1, 1, 1);
continue;
}
pii tmp = query(1, 1, 100000, 1, a[i]-1);
if(tmp.se==0) modify(1, 1, 100000, a[i], 1, 1);
else modify(1, 1, 100000, a[i], tmp.fi+1, tmp.se);
}
cout << v[1].se << endl;
return 0;
}
int getlis() {
int len=1;
f[1]=a[1];
rep(i,2,n) {
if(a[i]>f[len]) f[++len]=a[i];
else f[lower_bound(f+1,f+len+1,a[i])-f]=a[i];
}
return len;
}
/**************************************************************
Problem: 4228
User: ZqlwMatt
Language: C++
Result: 正确
Time:80 ms
Memory:7008 kb
****************************************************************/

幻魔皇

时间限制: 1Sec   内存限制: 512MB
标准输入   标准输出

Description

幻魔皇拉比艾尔很喜欢斐波那契树,他想找到神奇的节点对。
所谓斐波那契树,根是一个白色节点,每个白色节点都有一个黑色节点儿子,而每个黑色节点则有一个白色和一个黑色节点儿子。 神奇的节点对则是指白色节点对。
请问对于深度为 nn 的斐波那契树,其中距离为 ii 的神奇节点对有多少个? 拉比艾尔需要你对于 的所有 ii 都求出答案。

Input

一行一个正整数 nn

Output

一行 2n2n 个整数表示答案,对 123456789123456789 取模。

Sample Input

5

Sample Output

0 2 3 3 1 1 0 0 0 0

Hint

对于 20%20\% 的数据 .
对于 40%40\% 的数据 .
对于 60%60\% 的数据 .
对于 80%80\% 的数据 .
对于 100%100\% 的数据

Solution

不会

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
#include <iostream>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define max(a,b) ((a)>(b)?(a):(b))
typedef long long ll;
const int N = 5002, p = 123456789;
int w[N]={0,1,0,1}, sum[N]={0,1,1,2};
long long ans[N<<1];
int n;
int main() {
cin >> n;
rep(i,4,n) {
w[i] = w[i-1]+w[i-2];
if(w[i]>=p) w[i]-=p;
sum[i] = sum[i-1]+w[i];
if(sum[i]>=p) sum[i]-=p;
}
rep(i,1,n) ans[i] = (ll)sum[n-i]*w[i+1]%p;
rep(i,1,n)
rep(j,1,n)
(ans[i+j]+=(ll)(sum[n-max(i,j)+1]-1)*w[i]%p*w[j+1])%=p;
rep(i,1,2*n) printf("%lld ", ans[i]);
return 0;
}
/**************************************************************
Problem: 4229
User: ZqlwMatt
Language: C++
Result: 正确
Time:664 ms
Memory:1652 kb
****************************************************************/