Post 91

Veröffentlicht am | Edited on

考完了，并不是很好。

感觉还是垫底。emm。

然后来机房随便看看，口胡两道题（键盘我都不用为啥老是黏糊糊的啊，真恶心）

CF11D A Simple Task

求简单无向图的环数

$n <= 20$

题解

一眼不会多项式算法，状压/搜索。

想了下题意，每个环只被算一次那就看那些点集构成简单环就好了。。

直接状压一个点集$S$，然后强制编号最小的点是初始走的，也就是说走的顺序是按编号排序（这是一种什么思想我也忘了，反正就是去重常用方法就是了）。枚举下一个走的点$v$，不能出现在点集$S$里，且$S$里有边可达$v$。如果这个点和最小点相同，这个点集就合法，答案加一。

代码看心情。

CF401D Roman and Numbers

将$n(n<=10^{18})$的各位数字重新排列（不允许有前导零） 求 可以构造几个$\mod m$等于0的数字

题解

状压十进制位，记录当前加入的十进制位数（真实数字是按照加入顺序来确定的）及$\mod m$的值以及方案数。

然后转移枚举接下来再加哪一位。

有重复需要去重，对于一个集合，看看$0$到$9$分别出现多少次，多重集去重即可。

CF895C Square Subsets

$Petya$又迟到了…老师给了他额外的任务。对于一个序列，$Petya$需要找到非空子集，使它们的乘积等于某个整数的平方的方法的数量。 因为结果可能很大，结果需要$mod \; 10^9+7$

输入格式：

First line contains one integer $n$ ( $1<=n<=10^{5}$ ) — the number of elements in the array.

Second line contains $n$ integers $a{i} ( 1<=a{i}<=70 )$ — the elements of the array.

输出格式：

Print one integer — the number of different ways to choose some elements so that their product is a square of a certain integer modulo $10^{9}+7$

题解

看到$a_i$这么小就知道玄妙妙。

开始想。

想出来了。

一个数是完全平方的和一个所有质因子都是偶次幂是等价的。

我们把每个数拆一下质因数，用int压位。每一位表示从小到大第$i$个质数的次幂，$i$也就最大不超过30.

设$f_{i,S}$表示前$i$个数质因子状态为$S$时的方案数。枚举状态然后加上当前数转移即可。

$S$还是太大了点，其实我们用vector来存每个$f_i$即可，复杂度不好证明但是应该没有很大的。

还有更简单的方法：其实后面的质数次数只能是1（否则后面再有一个相同质因子最少多了自身这个质因子，多了后还得小于70，比如到了37就没用了，因为$237 > 70$了），我们只需要$70/2=35$以内的质数就够了，那样只有11个。所以先把有大于31质因子的数丢掉就可以了。这一下子复杂度从2e14降到1e8….

顺便写下转移方程：

$f{i,S ~xor~ S_i} += f{i-1,S}$

$S_i$表示第$i$个数的质数幂次奇偶状态，异或和$\mod 2$下运算恰好是一样的。

需要顺推，逆推不怎么好用位运算优化转移啊。

复杂度是$2^{11}n$，1e8 CF能过吧。。

code咕。

嗑一下SNOI的一道省选题

[SNOI2019]字符串

题目描述

给出一个长度为n的由小写字母组成的字符串a，设其中第i个字符为$a_i(1≤i≤n)$

设删掉第i个字符之后得到的字符串为$s_i$，请按照字典序对$s_1,s_2,……,s_n$从小到大排序。若两个字符串相等，则认为编号小的字符串字典序更小。

输入输出格式

输入格式：

第一行一个整数$n$

第二行一个长为$n$的由小写字母组成的字符串a。

输出格式：

输出一行$n$个整数$k1,k_2,……,k_n$，用空格隔开。表示$s{k1}<s{k2}<……<s{k_n}$

输入输出样例

输入样例#1：

1
2
7
aabaaab

输出样例#1：

1
3 7 4 5 6 1 2

说明

对于所有数据，$1≤n≤10^6$

对于10%的数据，$1≤n≤2000$

对于另外20%的数据，$1≤n≤10^5$且任意两个相邻字符$ai,a{i+1}$不相等；

对于另外30%的数据，$1≤n≤10^5$

对于余下40%的数据，无特殊限制。

题解

想了一会突然灵机一动想到如何快速比较少一字符的字符串：倍长。

然而这样的方法在于如果有相等的就GG了，那样两个后缀$n-1$长度可能相同，那样会继续比较后面的，从而导致不能按照编号为第二关键字。（好像我能想到的只有全是$a$的字符串，那样只是最后由于长度而正好从大到小排了）。。。字符串不会构造。

也许可以考虑一下$height$数组？

假如两个后缀的lCP已经大于$n-1$了，那就让编号小的在前面。RMQ一下$Height$就不多说了。

感觉这么暴力对排序后的那$n$个后缀这样暴力判断交换，应该又有不少分2333.也许只有30分

现在我们的目标就是，如何把一个初步排好序但没处理编号问题的不通过$O(n^2)$枚举而是通过特殊方法来完成把

LCP大于n-1的将编号大的在前的调整一下。

然后发现这SB题都这个份上了直接LCP然后比较LCP后第一个字符不就行了吗？LCP比n-1大那就编号小的在前呗，cmp都有了一个归并还是事吗？

卧槽我这sb题用了1个小时半.

cmp是$O(1)$的（查询LCP得RMQ一下$Height$，最好是ST表不要带log不然只有70）。这题的关键其实是稍微灵活一点，注意到和平常的后缀排序不一样，排序的其实都是定长串（想办法忽略后面的影响）。之所以想了半天是因为平常排序可不用先SA再$height$再比较排序来干一遍通常基数排序就能搞定的东西，但这道题恰好可以这么简单的搞定。其实不一定非要用SA那个数组来排序处理答案。

时间复杂度$O(nlogn)$

这题可以写一下代码的感觉。。顺便复习ST表。不过内存有点紧，176MB。。我被这题要搞自闭了。。

当我顺利的实现它后发现我又读错题了。代码如下：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 2000005
int sa[maxn] , rk[maxn] , pos[maxn] , h[maxn] , ct , c[maxn] , n , m;
char s[maxn];

inline void Sort()
{
	for(int i = 1 ; i <= m ; ++i) c[i] = 0;
	for(int i = 1 ; i <= ct ; ++i)
		++c[rk[pos[i]]];
	for(int i = 1 ; i <= m ; ++i)
		c[i] += c[i-1];
	for(int i = ct ; i >= 1 ; --i)
		sa[c[rk[pos[i]]]--] = pos[i];
}

inline void SA()
{
	puts("SA");
	ct = n , m = 1e6;
	for(int i = 1 ; i <= n ; ++i)
		pos[i] = i , rk[i] = s[i];
	Sort();
	for(int k = 1 ; k <= n ; k <<= 1)
	{
		ct = 0;
		for(int i = n - k + 1 ; i <= n ; ++i)
			pos[++ct] = i;
		for(int i = 1 ; i <= n ; ++i)
			if(sa[i] > k)
				pos[++ct] = sa[i] - k;
		Sort();
		std::swap(rk , pos);
		rk[sa[1]] = ct = 1;
		for(int i = 2 ; i <= n ; ++i)
			rk[sa[i]] = (pos[sa[i-1]] == pos[sa[i]] && pos[sa[i-1] + k] == pos[sa[i] + k]) ? ct : ++ct;
		if((m = ct) == n) break;
	}
	int r = 0;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(r) --r;
		int p = sa[rk[i] - 1];
		while(s[i + r] == s[p + r]) ++r;
		h[rk[i]] = r;
	}
}

namespace ST
{
	int st[22][maxn] , lg[maxn];
	inline void initialize(int a)
	{
		for(int i = 1 ; i <= n ; ++i)
			lg[i] = lg[i-1] + (1 << lg[i-1] == i);
		for(int i = 1 ; i <= n ; ++i) st[0][i] = a[i];
		puts("0");
		for(int i = 1 ; i <= n ; ++i)
			printf("%d ",st[0][i]);
		putchar(10);
		int rg = std::min(lg[n] , 21);
		for(int k = 1 ; k <= rg ; ++k)
		{
			printf("NOW: %d\n",k);
			for(int j = 1 ; j + (1 << k) - 1 <= n ; ++j)
				st[k][j] = std::min(st[k-1][j] , st[k-1][j + (1 << k - 1)]);
			for(int j = 1 ; j + (1 << k) - 1 <= n ; ++j)
				printf("%d ",st[k][j]);
			putchar(10);
		}
	}
	inline int query(int l , int r)
	{
		if(l > r) std::swap(l,r); ++l;
		int k = lg[r-l+1] - 1;
		return std::min(st[k][l] , st[k][r - (1 << k) + 1]);
	}
}

int ans[maxn];

inline bool cmp(int x , int y)
{
	int lcp = ST::query(rk[x] , rk[y]);
	if(lcp >= n - 1) return x < y;
	return s[x + lcp] < s[y + lcp];
}

int main()
{
	scanf("%d\n",&n);
	scanf("%s",s+1);
	for(int i = n + 1 ; i <= n << 1 ; ++i) s[i] = s[i - n];
	n <<= 1;
	SA();
	ST::initialize(h);
//	printf("%d\n",ST::query(1 , 5));
	n >>= 1;
	for(int i = 1 ; i <= n ; ++i)
		ans[i] = i + 1 ;
	std::stable_sort(ans + 1 , ans + n + 1 , cmp);
	for(int i = 1 ; i <= n ; ++i)
		printf("%d ",ans[i] - 1);
}

我以为是从删去的地方后读再从头读。。。

我得重新想正解。。。。

说好是签到题。。

听说英语出分了，直播下载Android模拟器看看有没有上120。

哦，居然没上120我也是服了，作文分太低了吧。

看来又是一次800+名良好体验

反正潍坊数学物理出成会考一样不知道有啥意义。。

数学算了算分也成120左右了。。。。莫名算错所有大题也是够SB的。

正好这道SNOI的签到也做不出来hhhhh

终于想出了这道真·签到题

假设两个字符串$s_i,s_j , i < j$

发现$[1,i)$这个区间是没有动，不需要管的。

$(j,n]$这个区间同时往左移动一位，也是完全相同的。

也就是说只需要比较$[i,j]$这个区间？
不，注意细节。。是$(i,j)$，那两个字符不存在。

然后后缀数组对有原串求个SA，比较的时候考虑那个错开的后缀利用$LCP$（SA+RMQ）比较一下$i$和$i+1$后缀大小就行。当然LCP如果大于等于区间$(i,j)$长度，直接返回编号小的即可。

剩下就是归并排序。

试试看。

然后好像CMP恰好反了从大到小，改个符号AC了。签到题弄得我大费周折。。。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1000005
int sa[maxn] , rk[maxn] , pos[maxn] , h[maxn] , ct , c[maxn] , n , m;
char s[maxn];

inline void Sort()
{
	for(int i = 1 ; i <= m ; ++i) c[i] = 0;
	for(int i = 1 ; i <= ct ; ++i)
		++c[rk[pos[i]]];
	for(int i = 1 ; i <= m ; ++i)
		c[i] += c[i-1];
	for(int i = ct ; i >= 1 ; --i)
		sa[c[rk[pos[i]]]--] = pos[i];
}

inline void SA()
{
//	puts("SA");
	ct = n , m = 1e6;
	for(int i = 1 ; i <= n ; ++i)
		pos[i] = i , rk[i] = s[i];
	Sort();
	for(int k = 1 ; k <= n ; k <<= 1)
	{
		ct = 0;
		for(int i = n - k + 1 ; i <= n ; ++i)
			pos[++ct] = i;
		for(int i = 1 ; i <= n ; ++i)
			if(sa[i] > k)
				pos[++ct] = sa[i] - k;
		Sort();
		std::swap(rk , pos);
		rk[sa[1]] = ct = 1;
		for(int i = 2 ; i <= n ; ++i)
			rk[sa[i]] = (pos[sa[i-1]] == pos[sa[i]] && pos[sa[i-1] + k] == pos[sa[i] + k]) ? ct : ++ct;
		if((m = ct) == n) break;
	}
	int r = 0;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(r) --r;
		int p = sa[rk[i] - 1];
		while(s[i + r] == s[p + r]) ++r;
		h[rk[i]] = r;
	}
}

namespace ST
{
	int st[22][maxn] , lg[maxn];
	inline void initialize(int* a)
	{
		for(int i = 1 ; i <= n ; ++i)
			lg[i] = lg[i-1] + (1 << lg[i-1] == i);
		for(int i = 1 ; i <= n ; ++i) st[0][i] = a[i];
//		puts("0");
//		for(int i = 1 ; i <= n ; ++i)
//			printf("%d ",st[0][i]);
//		putchar(10);
		int rg = std::min(lg[n] , 21);
		for(int k = 1 ; k <= rg ; ++k)
		{
//			printf("NOW: %d\n",k);
			for(int j = 1 ; j + (1 << k) - 1 <= n ; ++j)
				st[k][j] = std::min(st[k-1][j] , st[k-1][j + (1 << k - 1)]);
//			for(int j = 1 ; j + (1 << k) - 1 <= n ; ++j)
//				printf("%d ",st[k][j]);
//			putchar(10);
		}
	}
	inline int query(int l , int r)
	{
		if(l > r) std::swap(l,r); ++l;
		int k = lg[r-l+1] - 1;
		return std::min(st[k][l] , st[k][r - (1 << k) + 1]);
	}
}

int ans[maxn];

int abs(int x){
	return x > 0 ? x : -x;
}

inline bool cmp(int x , int y)
{
	if(x > y) std::swap(x,y);
	int lcp = ST::query(rk[x] , rk[x + 1]);
	if(lcp >= abs(y-x)) return y < x;
	return s[x + lcp] < s[x + lcp + 1];
}

int main()
{
	scanf("%d\n",&n);
	scanf("%s",s+1);
	SA();
	ST::initialize(h);
//	printf("%d\n",ST::query(1 , 5));
	for(int i = 1 ; i <= n ; ++i)
		ans[i] = i ;
	std::stable_sort(ans + 1 , ans + n + 1 , cmp);
	for(int i = 1 ; i <= n ; ++i)
		printf("%d ",ans[i]);
}

[SNOI2019]数论

题目描述

给出正整数P,Q,TP大小为m整数集A大小为m整数集B请你求出：

$\sum_{i=0}^{T-1}[(i \in A (mod P) \wedge (i \in B (mod Q)]$

换言之，就是问有多少个小于T的非负整数x 足：x除以P的余数属于A且x除以Q 余数属于B

输入输出格式

输入格式：

第一行55个用空格隔开的整数P,Q,n,m,T

第二行n 用空格隔开的整数，表示集合$A={A_1,A_2,……,A_n}$……, 保证$A_i$两不同，且$0 \leq A_i<P$

第三行m 用空格隔开的整数，表示集合$B={B_1,B_2,……,B_m}$……, 保证$B_i$两不同，且$0 \leq B_i<Q$

输出格式：

输出一行一个整数表示答案。

输入输出样例

输入样例#1：

1
2
3
4 6 3 3 14
0 1 3
2 4 5

输出样例#1：

1
4

说明

对于所有数据，$1 \leq n,m \leq 10^6 , 1 \leq P,Q \leq 10^6 , 1 \leq T \leq 10^{18}$

对于10%的数据，$T \leq 10^6$

对于另外20%的数据，$P,Q \leq 1000

对于另外10%的数据，$P,Q$互质，且$P,Q \leq 10^5

对于另外10%的数据，P,Q质。

对于另外10%的数据，$P,Q \leq 10^5$

对于余下30%的数据，无特殊限制。

题解

挺妙的题，而且容易看出是图论而不是数论。。。

抄题解.jpg

暂时咕一下。

[SNOI2017]炸弹

SNOI2017

题目描述

在一条直线上有 $N$ 个炸弹，每个炸弹的坐标是 $X_i$，爆炸半径是 $R_i$，当一个炸弹爆炸时，如果另一个炸弹所在位置 $X_j$ 满足： X_i-R_i≤Xj≤X_i+R_iX**i−R**i≤X**j≤X**i+R**i ，那么，该炸弹也会被引爆。 现在，请你帮忙计算一下，先把第 $i$ 个炸弹引爆，将引爆多少个炸弹呢？

答案对$1000000007$取模

输入输出格式

输入格式：

第一行，一个数字 $N$ ，表示炸弹个数。 第$ 2 ∼ N+1$行，每行$ 2$ 个数字，表示 $X_i$，$R_i$，保证 $X_i$ 严格递增。

输出格式：

一个数字，表示 $\sum \limits_{i=1}^n i\times ans_i$

输入输出样例

输入样例#1：

1
2
3
4
5
4
1 1
5 1
6 5
15 15

输出样例#1：

1
32

说明

$N≤500000， -10^{18}≤X_i≤10^{18}， 0≤R_i≤2 \times 10^{18}$

题解

有明显的相互关系。

一个$O(n^2)$的做法是使用权值线段树，我们直接建一颗权值线段树，然后就可以$O(n)$获得半径范围内的所有点并连边。

这时我突然突发奇想，如果我把权值线段树一个权值区间直接和当前点相连（这个权值区间包含在当前点影响区间内），这样只连了$O(logn)$条边？那我最后只有不到$2n+nlogn$条边，连的时候只需要从被影响到影响连，直接DP。这不会就是树形结构优化建图吧？Idea这么简单的吗？

好像不大对，因为最终图里可能有环。。不是DAG？那就SCC Tarjan！SCC内每个点都加上SCC的大小，对外就是一个点权为其大小的点，直接拓扑排序加上就行。

我就这么20分钟切了NOI+？快来把我打醒别让我做春秋大梦。

很懒，改天写代码。感觉非常科学，这道题真好！

【CF891E】Lust

题意

给你一个长度为n的序列$ai$，对这个序列进行k次操作，每次随机选择一个1到n的数x，令$res+=\prod\limits{i!=x}a_i$（一开始res=0），然后$a_i$—。问最终res的期望值。答案在模意义下对$10^9+7$取模。

$n\le 5000,k\le 10^9$

题意

首先需要发现，假如第$i$个数被减的次数为$b_i$，则$res=\prod\limits_i a_i-\prod\limits_i (a_i-b_i)$。这个用归纳法容易证明。

于是问题就变成了求$[{\sum bi=k}]{1\over n^k}{k!\over \prod b_i!}\prod\limits{i}(a_i-b_i)$

设生成函数$Fi(x)=\sum\limits{j}{(a_i-j)x^j\over j!}$，它等于

$Fi(x)=\sum\limits_j{a_ix^j\over j!}-\sum\limits_j{x^j\over (j-1)!}\\=\sum\limits{j}{aix^j\over j!}-x\sum\limits{j}{x^j\over j!}\\=\sum\limits_j{(a_i-x)x^j\over j!}=(a_i-x)e^j$

所以$\prod\limitsi F_i(x)=e^{nj}\prod\limits_i (a_i-x)$。我们可以暴力求出$\prod\limits_i (a_i-x)$的每一项系数，设其为$c_i$。剩下的就是求$e^{nj}$的第$k-n,k-n+1…k$项系数。显然第i项系数是$n^i\over i!$，再乘上前面的${k!\over n^k}$就变成了$\sum\limits{i=0}^n{ci}n^{-i}\prod\limits{j=k-i}^kj$

看了半天题解。。。数学是好东西

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=5010;
typedef long long ll;
const ll P=1000000007;
ll ine[maxn],v[maxn],f[maxn];
int n;
ll k,ans;
int main()
{
    int i,j;
    scanf("%d%lld",&n,&k);
    for(ans=i=1;i<=n;i++)    scanf("%lld",&v[i]),ans=ans*v[i]%P;
    f[0]=1;
    for(i=1;i<=n;i++)
    {
        for(j=i;j>=1;j--)
        {
            f[j]=(f[j]*v[i]-f[j-1])%P;
        }
        f[0]=f[0]*v[i]%P;
    }
    ine[0]=ine[1]=1;
    for(i=2;i<=n;i++)    ine[i]=P-(P/i)*ine[P%i]%P;
    ll t=1,tmp=1;
    for(i=0;i<=n&&i<=k;i++)
    {
        ans=(ans-f[i]*t%P*tmp)%P;
        t=t*ine[n]%P,tmp=tmp*(k-i)%P;
    }
    printf("%lld",(ans+P)%P);
    return 0;
}

假装看懂了上面的内容后，来告诉各位一个好东西。

如何避免复制markdown令人讨厌的重复？我已经对删除重复markdown厌恶不已。

http://tool.chinaz.com/htmlfilter

markdown源码网页查看源码，复制，粘贴，过滤，OK。