8-1胡策题解

A

题面

小 A 同学得到了一条⻓为L米的白色绳子,但是他觉得这条绳子的颜色过于单调了,于是他决定给绳子染上色让它变成一条彩绳。小 A 一共有m种颜色,他将L米⻓的绳子平均划分成了L小段,显然,每一小段的⻓度为 1米,然后给每一小段都染上一种颜色,每种颜色都可以染无数次,不必全部使用。

但是考虑到⻢上就要举办同学聚会了,于是他决定将这条⻓为L米的绳子顺次截成n条,第i条的⻓度为lil_i米,以用来送给n个好朋友。为了让他的好朋友对他们收到的礼物很满意,小A觉得,送给每个人的单独的一条绳子中,不能出现相邻的两小段颜色相同的情况。同时,为了让同学们感觉到他收到的礼物很特殊,小 A 想让任意相邻的两条绳子的颜色种类不完全相同,相邻两条绳子颜色种类不完全相同指的是至少存在一种颜色,使得它不会同时出现在相邻两条绳子上。

那么,现在小 A 想知道,他有多少种不同的染色方案,两种染色方案不同,指的是原来在初始的L中的位置上至少存在一个小段使得它所染的颜色不相同。答案对p取膜输出

n1000000,m1000000,li5000,2p109n\le 1000000,m\le 1000000,l_i\le 5000,2\le p\le 10^9

题解

先把膜数放到一边。

S=max{li}S=\max\{l_i\}

fi,jf_{i,j}表示用i种颜色染j小段(全部用上)的方案数。

考虑最后一段的颜色在前面是否出现过。则fi,j=ifi1,j1+(i1)fi,j1f_{i,j}=if_{i-1,j-1}+(i-1)f_{i,j-1}

dpi,jdp_{i,j}表示前i-1条已经染完了,第i条恰好用j种颜色的方案数。预处理O(S2)O(S^2)

枚举第i-1条用的颜色数k,如果k=j,那么第i条颜色的选取方案会少一种(去掉重复的方案)。否则就是(mj)\binom{m}{j}

那么dpi,j=(kdpi1,k((mj)[j=k]))fj,lidp_{i,j}=(\sum\limits_k dp_{i-1,k}(\binom{m}{j}-[j=k]))f_{j,l_i}

这样就能O(LS)O(LS)转移辣!

si=jdpi,js_i=\sum\limits_{j} dp_{i,j}

那么dpi,j=(si(mj)dpi1,j)fj,lidp_{i,j}=(s_i\binom{m}{j}-dp_{i-1,j})f_{j,l_i}

时间复杂度O(L+S2)O(L+S^2)

但是遇到了两个问题:1.空间 2.(mi)\binom{m}{i}预处理

空间很好解决,可以直接滚动数组优化掉,也可以把dpi,jdp_{i,j}存进dpk=1i1lk+jdp_{\sum\limits_{k=1}^{i-1}l_k+j},空间复杂度O(L)O(L)

(mi)\binom{m}{i}预处理可以用exlucas。由于每次计算组合数p固定,很多东西可以预处理,并且由于m106m\le 10^6所以可以在一些地方优化下。

具体见代码

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
/*
Author: CNYALI_LK
LANG: C++
PROG: a.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
ll p;
namespace exlucas{
ll a[102424],b[102424],c[102424],d[102424],t;
ll sp;
vector<ll> f[128];
ll fpm(ll a,ll b,ll p){
ll c;
for(c=1;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
return c;
}
void fac(ll n,ll t,ll &x,ll &y){
x=1;y=0;
ll p=c[t],pp=a[t];
while(n){
x=x*((n/pp)?fpm(f[t][pp],n/pp,pp):1)%pp*f[t][n%pp]%pp;
n/=c[t];
y+=n;
}
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1,y=0;
}
else{
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
}
ll inv(ll a,ll p){
ll x,y;
exgcd(a,p,x,y);
return (x%p+p)%p;
}
void C(ll n,ll m,ll t){
ll xa,ya,xb,yb,xc,yc;
fac(n,t,xa,ya);
fac(m,t,xb,yb);
fac(n-m,t,xc,yc);
ll xx,yy;
yy=ya-yb-yc;
xx=xa*inv(xb*xc%a[t],a[t])%a[t];
while(yy){
xx=xx*c[t]%a[t];
--yy;
}
b[t]=xx;
}
ll CRT(ll t,ll mul){
ll ans=0,iv,is;
for(ll i=1;i<=t;++i){
is=mul/a[i];
iv=inv(is,a[i]);
ans=(ans+is*iv%mul*b[i])%mul;
}
return ans;
}
void init(ll t){
f[t].push_back(1LL);
for(ll i=1;i<=a[t]&&i<=1000000;++i){
f[t].push_back(f[t][i-1]);
if(i%c[t])f[t][i]=f[t][i]*i%a[t];
}
}
void Set(ll p){
sp=p;
t=0;
for(ll i=2;i*i<=p;++i)
if(!(p%i)){
c[++t]=i;
a[t]=1;
d[t]=0;
while(!(p%i)){
a[t]*=i;
++d[t];
p/=i;
}
init(t);
}
if(p>1){
c[++t]=p;
a[t]=p;
d[t]=1;
init(t);
}
}
ll exlucas(ll n,ll m){
for(ll i=1;i<=t;++i){
C(n,m,i);
}
return CRT(t,sp);
}
}
ll C[1024242];
ll l[1024242],qz[1024242],f[10242424],su[1024242];
ll spm[5005][5005];
ll ff(ll x,ll y){return y<=l[x]?f[qz[x]+y]:0;}
ll fpm(ll a,ll b,ll p){
ll c=1;
for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
return c;
}
ll prime(ll x){
for(ll i=2;i*i<=x;++i)if(!(x%i))return 0;
return 1;
}
int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
ll n,m;
n=read();m=read();p=read();
exlucas::Set(p);
for(ll i=0;i<=m&&i<=5000;++i){C[i]=exlucas::exlucas(m,i);}
spm[1][1]=1;
for(ll i=2;i<=5000;++i){
for(ll j=1;j<=5000;++j)spm[i][j]=((i-1)*spm[i][j-1]+i*spm[i-1][j-1])%p;
}

for(ll i=1;i<=n;++i){
l[i]=read();
qz[i]=l[i-1]+qz[i-1];
}
su[0]=1;
for(ll i=1;i<=n;++i){
su[i]=0;
for(ll j=1;j<=l[i]&&j<=m;++j){
f[qz[i]+j]=(su[i-1]*C[j]%p-ff(i-1,j)+p)%p*spm[j][l[i]]%p;
su[i]=(su[i]+f[qz[i]+j])%p;
}
}
printf("%lld\n",su[n]);
return 0;
}

B

题意

一棵以1为根的树,其中一些点是关键点。

两个操作:

  • 给定点u,对于所有关键点v,anslca(u,v)ans_{lca(u,v)}加上wv=vw_v=v
  • 给定点u 如果u是关键点,让它不是关键点 否则让它是关键点

n,m3105n,m\le 3\cdot10^5

题解

树链剖分假做法

我们记aia_i为i子树ans和。bib_i为i子树关键点w的和。

那么操作1就是对u所有祖先的aia_i加上bib_i

操作2就是修改u所有祖先的bib_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
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
/*
Author: CNYALI_LK
LANG: C++
PROG: b.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define aint(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
int s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}

int a[302424],to[602323],lst[602323],beg[302423],e,b[302424],fa[302424];
void add(int u,int v){
to[++e]=v;
lst[e]=beg[u];
beg[u]=e;
}
ll asum[19982443],bsum[19982443],ans[302423];
int l[19982443],r[19982443],t,rt[302423];
void adda(int rt,int ls,int rs,int id,int w){
asum[rt]+=w;
if(ls==rs)return;
int mid=((ls+rs)>>1);
if(id<=mid){
if(!l[rt])l[rt]=++t;
adda(l[rt],ls,mid,id,w);
}
else{
if(!r[rt])r[rt]=++t;
adda(r[rt],mid+1,rs,id,w);
}
}

void addb(int rt,int ls,int rs,int id){
++bsum[rt];
if(ls==rs)return;
int mid=((ls+rs)>>1);
if(id<=mid){
if(!l[rt])l[rt]=++t;
addb(l[rt],ls,mid,id);
}
else{
if(!r[rt])r[rt]=++t;
addb(r[rt],mid+1,rs,id);
}
}
int merge(int u,int v,int x){
if(!v)return u;
if(!u)return v;
ans[x]+=asum[l[u]]*bsum[r[v]];
ans[x]+=asum[l[v]]*bsum[r[u]];
int mg=++t;
asum[mg]=asum[u]+asum[v];
bsum[mg]=bsum[u]+bsum[v];
l[mg]=merge(l[u],l[v],x);
r[mg]=merge(r[u],r[v],x);
return mg;
}
void dfs(int u,int f){
for(int i=beg[u];i;i=lst[i])if(to[i]!=f){
dfs(to[i],u);
rt[u]=merge(rt[u],rt[to[i]],u);
}
}
int main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
int n,m,u,v;
n=read();m=read();
for(int i=1;i<=n;++i){
a[i]=read();
rt[i]=++t;
}
for(int i=1;i<=n;++i)
if(a[i])adda(rt[i],0,m,0,i);
for(int i=1;i<n;++i){
u=read();v=read();
add(u,v);
add(v,u);
}
for(int i=1;i<=m;++i){
if((read())==1){
u=read();
addb(rt[u],0,m,i);
if(a[u])ans[u]+=u;
}
else{
u=read();
if(a[u])adda(rt[u],0,m,i,-u);
else adda(rt[u],0,m,i,u);
a[u]^=1;
}
}
dfs(1,0);
for(int i=1;i<=n;++i)printf("%lld\n",ans[i]);
return 0;
}

C

题意

有一个n行4列的环形棋盘(第1列和第4列相连)。

定义一个初始状态为,把1到4n从上到下 从左到右放进棋盘的状态

例如n=2时:

1 2 3 4

5 6 7 8

现在把它打乱了,每次可以移动1的位置,求移动回初始状态的最小步数。

n10n\le 10

题解

这种题一看就是搜索。但是答案可能很大(虽然实际上不是很大 但还是存不下) 所以用IDA*。

一个很强的估价函数:除了1以外,每个数到它应该到的地方的距离和。显然不超过最优步数。

然后就能过 还跑得很快。

实际上从1开始随机走10000步它就不可能过了,然而出题的时候没有说 答案大于多少输出无解。

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
/*
Author: CNYALI_LK
LANG: C++
PROG: c.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__) #define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
int s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
int a[15][6];
int n,x,y;
int g(){
int ans=0,xx,yy;
for(int i=1;i<=n;++i)for(int j=1;j<=4;++j)if(a[i][j]!=1){
yy=(a[i][j]-1)%4+1;
xx=(a[i][j]-yy)/4+1;
// printf("%d,%d->%d,%d %d\n",i,j,xx,yy,abs(i-xx)+min(abs(yy-j),4-abs(yy-j)));
ans+=abs(i-xx)+min(abs(yy-j),4-abs(yy-j));
}
return ans;
}
int idastar(int up,int f,int pre){
int hg=g();
if(!hg){
return 1;
}
if(f+hg>up)return 0;
if(x!=1 && pre!=2){
swap(a[x][y],a[x-1][y]);
--x;
if(idastar(up,f+1,1)){
return 1;
}
++x;
swap(a[x][y],a[x-1][y]);
}
if(x!=n&&pre!=1){
swap(a[x][y],a[x+1][y]);
++x;
if(idastar(up,f+1,2)){
return 1; } --x;
swap(a[x][y],a[x+1][y]);
}
if(pre!=4){
swap(a[x][y],a[x][y%4+1]);
y=y%4+1;
if(idastar(up,f+1,3)){
return 1;
}
y=(y+2)%4+1;
swap(a[x][y],a[x][y%4+1]);
}
if(pre!=3){
swap(a[x][y],a[x][(y+2)%4+1]);
y=(y+2)%4+1;
if(idastar(up,f+1,4)){
return 1;
}
y=y%4+1;
swap(a[x][y],a[x][(y+2)%4+1]);
}
return 0;
}
int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
n=read();
for(int i=1;i<=n;++i)for(int j=1;j<=4;++j)if(1==(a[i][j]=read())){x=i,y=j;};
int ans=g();
while(!idastar(ans,0,0))++ans;
printf("%d\n",ans);
return 0;
}
文章目录
  1. 1. A
    1. 1.1. 题面
    2. 1.2. 题解
  2. 2. B
    1. 2.1. 题意
    2. 2.2. 题解
      1. 2.2.1. 树链剖分假做法
      2. 2.2.2. 真做法
  3. 3. C
    1. 3.1. 题意
    2. 3.2. 题解
|

博客使用Disqus作为评论系统