比赛链接
1001
签到题，给出的项除了常数以外都是不收敛的。
于是判断有 $x$ 的项是否为 $0$ 即可。
1002
签到题，暴力枚举起始点，用桶记录个数即可。
也可套用点分治做法做到 $O(n\log n)$。
1003
题意
求所有长度为 $n$ 的01字符串的最短循环节的出现次数。
$n\le 10^9,\sum n\le 10^{10}$。
题解
设 $g_n$ 表示答案，$f_i$ 表示最小循环节长度为 $i$ 的字符串个数。
有：$g_n=\sum_{i=1}^n\left \lfloor \frac{n}{i} \right \rfloor f_i$。
考虑 $f_i$ 如何求：
当 $m\le \frac{n}{2}$ 时，$2^m=\sum_{i|m} f_i$。
而当 $m>\frac{n}{2}$ 后，上式就不成立了。因为周期引理不再适用。
但可以发现，此时的 $\left \lfloor \frac{n}{i} \right \rfloor=1$ ，于是我们还是通过补集转换，转去算 $2^n-\sum_{i=1}^{\left \lfloor \frac{n}{2} \right \rfloor} f_i$ 。
于是有 $g_n=2^n+\sum _{i=1}^{\frac{n}{2}}(\left \lfloor \frac{n}{i} \right \rfloor -1)f_i$。
整除分块，又因为有 $2^n=f * 1$，杜教筛筛出 $f_i$ 的前缀和即可。发现跑一次算 $f_i$ 前缀和的杜教筛就能算出整除分块里的所有的前缀和。
这里记录一下杜教筛的过程：若有积性函数 $f$，要算 $f$ 的前缀和 $S_n=\sum_{i=1}^nf_i$找到另外两个积性函数 $h,g$ 使得 $h=f * g$。
$$
\sum_{i=1}^n h_i=\sum_{i=1}^n \sum_{j|i} f(j)g(\frac{i}{j})\
=\sum_{i=1}^n g_i \sum_{j=1}^{\left \lfloor \frac{n}{i} \right \rfloor} f_i\
=\sum_{i=1}^n g_i S_{\left \lfloor \frac{n}{i} \right \rfloor}
$$
于是就可以了。
需要预处理 $O(n^{\frac{2}{3}})$ 前的 $f_i$ 的前缀和。
程序
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
| #include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
int x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
return ans;
}
const int N=1e6;
int s[N+3],f[N+3];
inline void init(int n)
{
ll nw=1;
fo(i,1,n)
{
nw=(nw*2)%mod;
f[i]=Dec(nw,f[i]);
s[i]=Add(s[i-1],f[i]);
for(int j=i+i;j<=n;j+=i)
f[j]=Add(f[j],f[i]);
}
}
int n,n2,tot;
ll a[300000];
inline int id(int x) {return x<=n2?x:tot-n/x;}
ll calc_g(int m)
{
if(!m) return 0;
if(a[id(m)]!=-1) return a[id(m)];
ll ans=Dec(Pow(2,(m+1)),2);
for(int l=2,r;l<=m;l=r+1)
{
r=m/(m/l);
ans=Dec(ans,1ll*(r-l+1)*calc_g(m/l)%mod);
}
return a[id(m)]=ans;
}
inline ll calc_f(int _n)
{
n=_n; n2=sqrt(n+0.3); tot=1;
for(int l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
a[tot++]=((r<=N)?s[r]:-1);
}
int m=n/2;
ll ans=Pow(2,n);
for(int l=1,r;l<=m;l=r+1)
{
r=min(m,n/(n/l));
ans=Add(ans,1ll*(n/l-1)*(calc_g(r)-calc_g(l-1)+mod)%mod);
}
return ans;
}
int main()
{
init(1e6);
CASET printf("%lld\n",calc_f(read()));
return 0;
}
|
1004
题意
给出一个由小写字母组成的字符串 $S$，及每个字符的权值。一个串的价值为其每个字符的权值之和。
求 $S$ 所有不同的子串中，价值为第 $k$ 小的价值是多少。没有则输出 $-1$。
两个子串相同当且仅当他们长度相同且对应每一位字符均相等。
$n\le 10^5$。
题解
真的是，好久不写，都忘了SAM的性质了。
二分答案，建出SAM后，每个节点对应着 $len_i-len_{fa_i}$ 个子串。且长度连续，均为当中最长串的后缀。
于是在每个节点里面再二分一次找到串的个数就好了。
注意！需要记录SAM中每个串的终止位置！即right集合当中的任意一个即可。
程序
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>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
int x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=200010;
const int S=26;
namespace SAM{
int ne[N][S],fa[N],len[N],las,siz,idx[N];
inline void init()
{
for(int i=1;i<=siz;i++) memset(ne[i],0,sizeof(ne[i])),fa[i]=len[i]=0;
las=siz=1;
}
inline void extend(int c,int id)
{
int cur=++siz;
idx[cur]=id+1;
len[cur]=len[las]+1;
int p=las;
for(;p&&!ne[p][c];p=fa[p]) ne[p][c]=cur;
if(!p) fa[cur]=1;
else
{
int q=ne[p][c];
if(len[q]==len[p]+1) fa[cur]=q;
else
{
int clone=++siz;
len[clone]=len[p]+1; idx[clone]=idx[q];
memcpy(ne[clone],ne[q],sizeof(ne[q]));
fa[clone]=fa[q];
for(;p&&ne[p][c]==q;p=fa[p]) ne[p][c]=clone;
fa[cur]=fa[q]=clone;
}
}
las=cur;
}
}
int n,m,sum[N],val[30];
ll k;
char s[N];
int L[N],R[N],id[N];
inline ll get()
{
ll ss=0;
m=SAM::siz;
fo(i,2,SAM::siz) id[i]=SAM::idx[i],L[i]=SAM::len[SAM::fa[i]]+1,R[i]=SAM::len[i],ss+=SAM::len[i]-SAM::len[SAM::fa[i]];
return ss;
}
inline ll check(int x)
{
ll ss=0;
fo(i,2,m) if(sum[id[i]]-sum[id[i]-L[i]]<=x)
{
int l=L[i],r=R[i],mid;
for(;l<=r;)
{
mid=(l+r)>>1;
if(sum[id[i]]-sum[id[i]-mid]<=x) l=mid+1;
else r=mid-1;
}
ss+=(r-L[i]+1);
}
return ss;
}
int main()
{
CASET
{
n=read(); cin>>k;
scanf("%s",s);
SAM::init();
ff(i,0,strlen(s)) SAM::extend(s[i]-'a',i);
fo(i,0,25) val[i]=read();
if(get()<k)
{
puts("-1");
continue;
}
fo(i,1,n) sum[i]=sum[i-1]+val[s[i-1]-'a'];
int l=0,r=n*100,mid;
for(;l+1<r;)
{
mid=(l+r)>>1;
if(check(mid)>=k) r=mid;
else l=mid;
}
printf("%d\n",r);
}
return 0;
}
|
1008
题意
$n\times m$ 的网格图，从 $(1,1)$ 开始，每次能往上或往右走一格，走到 $(n,m)$。有 $k$ 个点不能经过。问有可能走到的格子有多少个。
$n,m,k\le 10^5$。
题解
补集转换，变为求哪些格子走不到。
对于一条斜向上的线段，不能走的格子将形成一个直角三角形或等腰梯形。
考虑斜着的扫描线，这样相当于是若干条不相交的线段组成。随着扫描线的右移，中间的线段长度将集体 $-1$，两端的线段有可能不减。
用链表维护这些线段，插入一个点时判断能否与左右两端的线段合并，或本身就在线段里面。
线段长度减一的话暴力枚举链表中的每一个元素即可，长度减到 $0$ 后将其删除。
这样做的复杂度是对的，因为线段原始的总长不会超过 $k$。
时间复杂度 $O(n+m+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
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
| #include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
int x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=200010;
struct node{
int x,y;
};
node p[N];
vector<int> adj[N];
inline void add(int x,int y){adj[x].pb(y);}
struct line{
int y,len;
};
line s[N<<1];
int n,m,k,L[N],R[N];
inline bool cmp(const int &x,const int &y)
{
return p[x].y>p[y].y;
}
int main()
{
CASET
{
n=read(); m=read(); k=read();
ll ans=1ll*n*m;
fo(i,1,n+m) adj[i].clear();
fo(i,0,n+m+1) L[i]=R[i]=0;
R[0]=n+m+1; L[n+m+1]=0;
fo(i,1,k) p[i].x=read(),p[i].y=read(),add(p[i].x+p[i].y,i);
fo(i,2,n+m) sort(all(adj[i]),cmp);
int u;
fo(i,1,n+m)
{
for(int j=R[0];j!=n+m+1;j=R[j])
{
s[j].len--;
}
if(R[0]!=n+m+1)
{
u=R[0];
if(s[u].y==i-2&&i<=m+1) s[u].len++,s[u].y=i-1;
u=L[n+m+1];
if(s[u].y==s[u].len+1&&i<=n+1) s[u].len++;
}
for(int j=R[0];j!=n+m+1;j=R[j])
{
if(s[j].len==0)
{
L[R[j]]=L[j];
R[L[j]]=R[j];
j=L[j];
}
}
int j=R[0];
s[0].y=1000000000;
for(auto v:adj[i])
{
for(;j!=n+m+1&&s[j].y>=p[v].y;j=R[j]);
j=L[j]; k=R[j];
if(!j)
{
s[v].y=p[v].y; s[v].len=1;
R[0]=L[k]=v;
L[v]=0; R[v]=k;
j=v;
if(k==n+m+1) continue;
}
else
{
if(s[j].y-s[j].len+1<=p[v].y)
{
continue;
}
else
{
if(s[j].y-s[j].len==p[v].y) s[j].len++;
else
{
s[v].y=p[v].y; s[v].len=1;
R[j]=L[k]=v;
L[v]=j; R[v]=k;
j=v;
}
}
}
if(k!=n+m+1)
{
if(s[j].y-s[j].len==s[k].y)
{
s[j].len+=s[k].len;
int t=R[k];
L[t]=j; R[j]=t;
}
}
}
ll k=0;
for(int j=R[0];j!=n+m+1;j=R[j]) ans-=s[j].len,k+=s[j].len;
}
printf("%lld\n",ans);
}
return 0;
}
|