2018-8-1题解
目录:
- A
- B
- C
A
题面
小 A 同学得到了一条⻓为L米的白色绳子,但是他觉得这条绳子的颜色过于单调了,于是他决定给绳子染上色让它变成一条彩绳。小 A 一共有m种颜色,他将L米⻓的绳子平均划分成了L小段,显然,每一小段的⻓度为 1米,然后给每一小段都染上一种颜色,每种颜色都可以染无数次,不必全部使用。
但是考虑到⻢上就要举办同学聚会了,于是他决定将这条⻓为L米的绳子顺次截成n条,第i条的⻓度为\(l_i\)米,以用来送给n个好朋友。为了让他的好朋友对他们收到的礼物很满意,小A觉得,送给每个人的单独的一条绳子中,不能出现相邻的两小段颜色相同的情况。同时,为了让同学们感觉到他收到的礼物很特殊,小 A 想让任意相邻的两条绳子的颜色种类不完全相同,相邻两条绳子颜色种类不完全相同指的是至少存在一种颜色,使得它不会同时出现在相邻两条绳子上。
那么,现在小 A 想知道,他有多少种不同的染色方案,两种染色方案不同,指的是原来在初始的L中的位置上至少存在一个小段使得它所染的颜色不相同。答案对p取膜输出
\(n\le 1000000,m\le 1000000,l_i\le 5000,2\le p\le 10^9\)
题解
先把膜数放到一边。
设\(S=\max\{l_i\}\)
设\(f_{i,j}\)表示用i种颜色染j小段(全部用上)的方案数。
考虑最后一段的颜色在前面是否出现过。则\(f_{i,j}=if_{i-1,j-1}+(i-1)f_{i,j-1}\)
设\(dp_{i,j}\)表示前i-1条已经染完了,第i条恰好用j种颜色的方案数。预处理\(O(S^2)\)
枚举第i-1条用的颜色数k,如果k=j,那么第i条颜色的选取方案会少一种(去掉重复的方案)。否则就是\(\binom{m}{j}\)
那么\(dp_{i,j}=(\sum\limits_k dp_{i-1,k}(\binom{m}{j}-[j=k]))f_{j,l_i}\)
这样就能\(O(LS)\)转移辣!
记\(s_i=\sum\limits_{j} dp_{i,j}\)
那么\(dp_{i,j}=(s_i\binom{m}{j}-dp_{i-1,j})f_{j,l_i}\)
时间复杂度\(O(L+S^2)\)
但是遇到了两个问题:1.空间 2.\(\binom{m}{i}\)预处理
空间很好解决,可以直接滚动数组优化掉,也可以把\(dp_{i,j}\)存进\(dp_{\sum\limits_{k=1}^{i-1}l_k+j}\),空间复杂度\(O(L)\)。
\(\binom{m}{i}\)预处理可以用exlucas。由于每次计算组合数p固定,很多东西可以预处理,并且由于\(m\le 10^6\)所以可以在一些地方优化下。
具体见代码
/*
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,\(ans_{lca(u,v)}\)加上\(w_v=v\)
- 给定点u 如果u是关键点,让它不是关键点 否则让它是关键点
\(n,m\le 3\cdot10^5\)
题解
树链剖分假做法
我们记\(a_i\)为i子树ans和。\(b_i\)为i子树关键点w的和。
那么操作1就是对u所有祖先的\(a_i\)加上\(b_i\)
操作2就是修改u所有祖先的\(b_i\)。
暴力可以过随机数据。
然后可以树链剖分优化。
但是卡暴力的数据树链剖分很快,随机数据树链剖分很慢。
真做法
对每个点记一个时间线段树,表示每个时间的操作。
然后线段树合并就可以了。
/*
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的位置,求移动回初始状态的最小步数。
\(n\le 10\)
题解
这种题一看就是搜索。但是答案可能很大(虽然实际上不是很大 但还是存不下) 所以用IDA*。
一个很强的估价函数:除了1以外,每个数到它应该到的地方的距离和。显然不超过最优步数。
然后就能过 还跑得很快。
实际上从1开始随机走10000步它就不可能过了,然而出题的时候没有说 答案大于多少输出无解。
/*
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;
}