Post 91

考完了,并不是很好。

感觉还是垫底。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$个整数$k_1,k_2,……,k_n$,用空格隔开。表示$s_{k_1}<s_{k_2}<……<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$且任意两个相邻字符$a_i,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**iR**iX**jX**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的序列$a_i$,对这个序列进行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 b_i=k}]{1\over n^k}{k!\over \prod b_i!}\prod\limits_{i}(a_i-b_i)$

设生成函数$F_i(x)=\sum\limits_{j}{(a_i-j)x^j\over j!}$,它等于

$F_i(x)=\sum\limits_j{a_ix^j\over j!}-\sum\limits_j{x^j\over (j-1)!}\\=\sum\limits_{j}{a_ix^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\limits_i 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{c_i}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。