2018.8.5 正睿暑期集训营 Day2

2018.8.5 正睿暑期集训营 Day2

时间：4h(实际)

期望得分：100+20+40~60

实际得分：80+20+40=140

总结

A.占领地区(前缀和)

计算覆盖的格子，如果不考虑交叉，单独算主对角线(向右斜的统称主对角线了)与副对角线(所有向左斜的)的话很容易。那先算出这个的答案。

考虑主次对角线交叉的部分，我们枚举每条次对角线，看它与哪些主对角线有交点，这是一个区间，那么好像可以二分。

而如果以x=y这条对角线为边界的话，确实可以二分两次来确定这个区间。

但是交点是指在格点上相交。这相当于两条直线的交点有整数解。但是可以发现每相邻两条副对角线，它们在格点上有交点的主对角线是正好互斥的。

再观察下，然后可以分奇偶性，求前缀和就行了。

但是不需要二分，因为我们可以O(1)计算出区间位置，然后前缀和。

分奇偶性的话前缀和从i-2转移就行了。

把坐标系旋转45°找规律会更方便些。

//19ms	1820kb

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 400000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=1e5+7;

int n,m,sum[N<<1];

bool vis2[N<<1];

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

int main()

{

//	freopen("A.in","r",stdin);

	n=read(), m=read();

	for(int i=1,x,y; i<=m; ++i)

		x=read(), y=read(), sum[x+y]=1, vis2[x-y+n]=1;

	LL ans=0; int lim=n<<1;

	for(int i=2; i<=lim; ++i)//先枚举主对角线好麻烦啊

	{

		if(sum[i]) ans+=n-std::abs(n-i+1);

		sum[i]+=sum[i-2];

	}

	for(int i=1; i<lim; ++i)

		if(vis2[i])

		{

			ans+=n-std::abs(n-i);

			ans-=sum[lim-std::abs(n-i)]-sum[std::abs(n-i)];//2+|n-i|~2n-|n-i|

		}

	printf("%lld\n",1ll*n*n-ans);

	return 0;

}

B.配对(组合)

题目链接

$Solution$

　　有一个只有一条边有权值的部分分，对于某种位置分布情况，我们肯定是在这条边两侧尽量配对。

　　这样扩展到每一条边，如果它两边能配对，我们应尽量让两边的配对，多走这条边的路，即$dis$一定会增加。

　　那么我们可以对每一条边计算其贡献。$O(m^2)$枚举它一边男女生人数就可以得到所有情况。设它某一边连通块点数为$x$，则边$now$的贡献为：$$w_{now}\times\sum_{i=0}^m\sum_{j=1}m(\min(i,m-j)+\min(m-i,j))C_m^iC_mjx^i(n-x){m-j}x^j(n-x){m-i}$$

　　把前面只与$i,j$有关的放到前面，枚举边：$$\sum_{i=0}^m\sum_{j=0}m(\min(i,m-j)+\min(m-i,j))C_m^iC_mj\sum_{edge}w_{edge}x^{i+j}(n-x){2m-(i+j)}$$

　　这样就只与$i+j$有关了，预处理所有边在$i+j$的贡献。复杂度$O(nm)$。

　　还有对min进行处理的容斥方法，不管了。

　　为什么跑7000+ms。。哪看都没有问题。。组合数啥的都是O(m)的啊

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 400000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

#define mod (1000000007)

typedef long long LL;

const int N=2504,M=N<<1;

int n,m,Enum,H[N],nxt[M],to[M],len[M],sz[N],X[M],val[M],inv[N],C[N];

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline void AddEdge(int w,int u,int v)

{

	to[++Enum]=v, nxt[Enum]=H[u], len[Enum]=w, H[u]=Enum;

	to[++Enum]=u, nxt[Enum]=H[v], len[Enum]=w, H[v]=Enum;

}

inline LL FP(LL x,int k)

{

	LL t=1;

	for(; k; k>>=1, x=x*x%mod)

		if(k&1) t=t*x%mod;

	return t;

}

void DFS(int x,int f)

{

	sz[x]=1;

	for(int i=H[x],v; i; i=nxt[i])

		if((v=to[i])!=f)

		{

			DFS(v,x), sz[x]+=sz[v];

			X[i]=X[i^1]=sz[v];

		}

}

int main()

{

	n=read(), m=read(), Enum=1;

	for(int i=1; i<n; ++i) AddEdge(read(),read(),read());

	DFS(1,1);

	for(int i=0,lim=m<<1; i<=lim; ++i)

	{

		LL tmp=0;

		for(int j=1; j<=Enum; j+=2)

			tmp+=1ll*len[j]*FP(X[j],i)%mod*FP(n-X[j],lim-i)%mod;

		val[i]=(int)(tmp%mod);

	}

	C[0]=inv[1]=1;

	for(int i=2; i<=m; ++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

	for(int i=1; i<=m; ++i) C[i]=1ll*C[i-1]*(m-i+1)%mod*inv[i]%mod;

	LL ans=0;

	for(int i=0; i<=m; ++i)

		for(int j=0; j<=m; ++j)

		ans+=1ll*(std::min(i,m-j)+std::min(m-i,j))*C[i]%mod*C[j]%mod*val[i+j]%mod;

	printf("%lld\n",ans%mod);

	return 0;

}

C 导数卷积(NTT)

题目链接

　　先令$n-1$。

\[g(x)=\sum_{i=0}^nf^{(i)}(x)f^{(n-i)}(x)
\]

　　肯定不能是$n$次卷积求。。我们尝试直接一次求出$g(x)$的各项系数。

　　用$G_i$表示$g(x)$的$x^i$的系数，$F_i$表示$f(x)$的$x^i$的系数。

　　首先$f(x)$经过$i$次求导后，$x^j$的系数为$F_{i+j}\frac{(i+j)!}{j!}$。

　　则$$G_d=\sum_{i=0}^d\sum_{j=0}nF_{i+j}\frac{(i+j)!}{i!}F_{n-j+d-i}\frac{(n-j+d-i)!}{(d-i)!}$$（先枚举左边多项式的$x$的次数$i$，再枚举它是经过$j$次求导后的，然后确定右边多项式的系数）

　　令$F(i)=F(i)\times i!$，则$$G_d=\sum_{i=0}^d\sum_{j=0}nF_{i+j}F_{n-j+d-i}\frac{1}{i!(d-i)!}$$

　　两个$F()$都有$i+j$，为了不动后面的$i$，令$j=i+j$，则$$G_d=\sum_{j=0}^{{n+d}F_jF_{n+d-j}\sum_{i=0}}d\frac{1}{i!(d-i)!}\times[i\leq j]\times[d-i\leq n+d-j]$$（$i$的枚举当然和$j$有关系啊。这里只要满足前面阶乘中的 $i\leq i+j$ 和 $d-i\leq n+d-(i+j)$ 就可以了）

　　后面小于等于的限制比较烦人。可以发现，当 $j<d$ 时，$n+d-j>n$，而$F$只有$F_{0,\cdots,n}$不为$0$，即$F_{n+d-j}=0$，可以忽略$[i\leq j]$。

　　同理，$n+d-j<d$ 时，$F_j=0$，后一项也可以忽略。

　　所以有$$G_d=\sum_{j=0}^{{n+d}F_jF_{n+d-j}\sum_{i=0}}d\frac{1}{i!(d-i)!}$$

　　其中$$\sum_{i=0}^{d\frac{1}{i!(d-i)!}=\frac{2}d}{d!}$$

　　NTT，然后乘上后面那个求和就行了。

//311ms	7632kb

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 300000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

#define G (3)

#define inv_G (332748118)

#define mod (998244353)

typedef long long LL;

const int N=(1<<18)+5;

int n,rev[N];

LL fac[N],inv[N],F[N];

char IN[MAXIN],*SS=IN,*TT=IN;

inline LL read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline LL FP(LL x,int k)

{

	LL t=1;

	for(; k; k>>=1, x=x*x%mod)

		if(k&1) t=t*x%mod;

	return t;

}

void NTT(LL *a,int lim,int type)

{

	for(int i=1; i<lim; ++i) if(i<rev[i]) std::swap(a[i],a[rev[i]]);

	for(int i=2; i<=lim; i<<=1)

	{

		int mid=i>>1;

		LL Wn=FP(~type?G:inv_G,(mod-1)/i);

		for(int j=0; j<lim; j+=i)

		{

			LL w=1,t;

			for(int k=0; k<mid; ++k,w=w*Wn%mod)

				a[j+k+mid]=(a[j+k]-(t=w*a[j+k+mid]%mod)+mod)%mod,

//				a[j+k+mid]=a[j+k]-(t=w*a[j+k+mid]%mod), a[j+k+mid]<0&&(a[j+k+mid]+=mod),

				a[j+k]+=t, a[j+k]>=mod&&(a[j+k]-=mod);

		}

	}

	if(type==-1) for(int i=0,inv=FP(lim,mod-2); i<lim; ++i) a[i]=a[i]*inv%mod;

}

int main()

{

	n=read()-1, fac[0]=1;

	for(int i=1; i<=n; ++i) fac[i]=fac[i-1]*i%mod;

	inv[n]=FP(fac[n],mod-2);

	for(int i=n-1; ~i; --i) inv[i]=inv[i+1]*(i+1)%mod;

	for(int i=0; i<=n; ++i) F[i]=read()*fac[i]%mod;

	int l=-1, lim=1;

	while(lim<=n<<1) ++l, lim<<=1;

	for(int i=1; i<lim; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<l);

	NTT(F,lim,1);

	for(int i=0; i<lim; ++i) F[i]=F[i]*F[i]%mod;

	NTT(F,lim,-1);

	for(int i=n,pw2=1; i<=(n<<1); ++i) printf("%d ",(int)(F[i]*pw2%mod*inv[i-n]%mod)), pw2<<=1, pw2>=mod&&(pw2-=mod);

	return 0;

}

考试代码

T1

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 400000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=1e5+7;

int n,m,cnt,val[N],X[N],Y[N],sum1[N],sum2[N];

bool vis1[N<<2],vis2[N<<2],vis3[N<<2];

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

namespace Spec

{

	bool vis[3003][3003];

	void Main()

	{

		int ans=0;

		for(int i=1,x,y; i<=n; ++i)

		{

			x=read(), y=read();

			if(x+y<=m+1)

			{

				for(int x0=x+y-1,y0=1; x0&&y0<=m; --x0,++y0)

					if(!vis[x0][y0]) ++ans, vis[x0][y0]=1;

			}

			else

			{

				for(int x0=m,y0=x+y-m; x0&&y0<=m; --x0,++y0)

					if(!vis[x0][y0]) ++ans, vis[x0][y0]=1;

			}

			if(x-y<=0)

			{

				for(int x0=1,y0=1-x+y; x0<=m&&y0<=m; ++x0,++y0)

					if(!vis[x0][y0]) ++ans, vis[x0][y0]=1;

			}

			else

			{

				for(int x0=x-y+1,y0=1; x0<=m&&y0<=m; ++x0,++y0)

					if(!vis[x0][y0]) ++ans, vis[x0][y0]=1;

			}

		}

		printf("%d\n",m*m-ans);

	}

}

inline bool Check()

{

	for(int i=1; i<=n; ++i) if(X[i]+Y[i]==m+1) return 1;

	return 0;

}

int QueryL(int v,int r)

{

//	if(v==m+1) return 1;

	int l=1,mid,ans=r;

	while(l<=r)

	{

		mid=l+r>>1;

		if((v<m+1&&v-1>=1-val[mid])||(v>m+1&&v-m<=val[mid]+m)) ans=mid, r=mid-1;//cross

		else l=mid+1;

	}

	return ans;

}

int QueryR(int v,int l)

{

//	if(v==m+1) return cnt;

	int r=cnt,mid,ans=l;

	while(l<=r)

	{

		mid=l+r>>1;

		if((v<m+1&&v-1>=val[mid]+1)||(v>m+1&&v-m<=m-val[mid])) ans=mid, l=mid+1;

		else r=mid-1;

	}

	return ans;

}

int main()

{

//	freopen("A.in","r",stdin);

	m=read(), cnt=n=read();

//	if(n<=3000&&m<=3000) {Spec::Main(); return 0;}

	bool f=0; LL Ans=0;

	for(int i=1; i<=n; ++i)

	{

		X[i]=read(), Y[i]=read(), val[i]=X[i]-Y[i];

		if(!val[i]) f=1;

		if(!vis1[X[i]-Y[i]+m]) Ans+=m-std::abs(X[i]-Y[i]), vis1[X[i]-Y[i]+m]=1;

		if(!vis2[X[i]+Y[i]]) Ans+=m-std::abs(X[i]+Y[i]-m-1), vis2[X[i]+Y[i]]=1;

	}

	if(!f) val[++cnt]=0;

	std::sort(val+1,val+1+cnt); int c=1;

	for(int i=2; i<=cnt; ++i)

		if(val[i]!=val[i-1]) val[++c]=val[i];

	cnt=c;

	int p=1;

	for(int i=2; i<=cnt; ++i) if(!val[i]) {p=i; break;}

	int t=0;

	if(Check())//exist i:xi+yi==m+1

	{

		for(int i=1; i<=cnt; ++i) if(!((m+1+val[i])&1)) ++t;

		vis3[m+1]=1, Ans-=t;

	}

	for(int i=1; i<=cnt; ++i)

		sum1[i]=sum1[i-1]+(val[i]&1), sum2[i]=sum2[i-1]+((val[i]&1)^1);

	t=0;

	for(int i=1,s,L,R; i<=n; ++i)

	{

		if(vis3[s=X[i]+Y[i]]) continue;

		vis3[s]=1, t+=(s&1)^1;//WA：不一定与主对角线相交！

		R=QueryR(s,p), L=QueryL(s,p);

		if(s&1) Ans-=sum1[R]-sum1[L-1];

		else Ans-=sum2[R]-sum2[L-1];

	}

	if(!f) Ans+=t;

	printf("%lld\n",1ll*m*m-Ans);

	return 0;

}

T2

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

#define mod (1000000007)

typedef long long LL;

const int N=2505;

int n,m,Enum,H[N],nxt[N<<1],to[N<<1],len[N<<1],pos[N<<1],fa[N],dep[N];

LL Ans,dis[N];

bool match[N];

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline void AddEdge(int w,int u,int v)

{

	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;

	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;

}

void T_DFS(int x)

{

	for(int i=H[x],v; i; i=nxt[i])

		if((v=to[i])!=fa[x])

			fa[v]=x, dep[v]=dep[x]+1, dis[v]=dis[x]+len[i], T_DFS(v);

}

inline int LCA(int u,int v)

{

	while(u!=v) dep[u]>dep[v]?u=fa[u]:v=fa[v];

	return u;

}

inline LL Dis(int x,int y){

	return dis[x]+dis[y]-(dis[LCA(x,y)]<<1);

}

void DFS2(int x,LL now,LL &mx)

{

	if(x>m)

	{

		mx=std::max(mx,now);

		return;

	}

	for(int i=1; i<=m; ++i)

		if(!match[i]) match[i]=1, DFS2(x+1,now+Dis(pos[x],pos[i+m]),mx), match[i]=0;

}

void Calc()

{

	LL mx=0;

	DFS2(1,0,mx);

	Ans+=mx%mod, Ans>=mod&&(Ans-=mod);

}

void DFS(int x)

{

	if(x>m<<1) {Calc(); return;}

	for(int i=1; i<=n; ++i) pos[x]=i, DFS(x+1);

}

int main()

{

//	freopen(".in","r",stdin);

	n=read(), m=read();

	for(int i=1; i<n; ++i) AddEdge(read(),read(),read());

	T_DFS(1), DFS(1);

	printf("%lld\n",Ans%mod);

	return 0;

}

T3

早就忘了NTT怎么写。。

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 400000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

#define G (3)

#define inv_G (332748118)

#define mod (998244353)

typedef long long LL;

const int N=5003,M=8300;

int n,A[N][M],B[M],C[M],len[N],rev[M];

LL g[N],inv_lim;

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline LL FP(LL x,int k)

{

	LL t=1;

	for(; k; k>>=1, x=x*x%mod)

		if(k&1) t=t*x%mod;

	return t;

}

void NTT(int *a,int lim,int type)

{

	for(int i=1; i<lim; ++i) if(i<rev[i]) std::swap(a[i],a[rev[i]]);

	for(int i=2; i<=lim; i<<=1)

	{

		int mid=i>>1;

		LL Wn=FP(~type?G:inv_G,(mod-1)/i),t,w;

		for(int j=0; j<lim; j+=i)

		{

			LL w=1;

			for(int k=0; k<mid; ++k, w=w*Wn%mod)

				a[j+k+mid]=(a[j+k]-(t=w*a[j+k+mid]%mod)+mod)%mod,

				a[j+k]=(a[j+k]+t)%mod;

		}

	}

	if(type==-1) for(int i=0; i<lim; ++i) a[i]=1ll*a[i]*inv_lim%mod;

}

void P_Mul(int *b,int *c,int l1,int l2)

{

	int L=-1, lim=1;

	while(lim<=l1+l2) lim<<=1, ++L;

	inv_lim=FP(lim,mod-2);

	for(int i=1; i<lim; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<L);

	for(int i=0; i<lim; ++i) B[i]=b[i], C[i]=c[i];

	NTT(B,lim,1), NTT(C,lim,1);

	for(int i=0; i<lim; ++i) B[i]=1ll*B[i]*C[i]%mod;

	NTT(B,lim,-1);

}

int main()

{

//	freopen("C.in","r",stdin);

//	freopen("my.out","w",stdout);

	n=read()-1;

	for(int i=0; i<=n; ++i) A[0][i]=read();

	len[0]=n+1;

	for(int x=1; x<=n; ++x)

	{

		int *a=A[x], *b=A[x-1]; len[x]=n-x+1;

		for(int i=0,lim=n-x; i<=lim; ++i) a[i]=1ll*(i+1)*b[i+1]%mod;

	}

	for(int i=0,lim=(n+1)>>1; i<lim; ++i)

	{

		P_Mul(A[i],A[n-i],len[i],len[n-i]);

		for(int i=0; i<=n; ++i) g[i]+=B[i]<<1;

	}

	if(!(n&1))

	{

		P_Mul(A[n>>1],A[n>>1],len[n>>1],len[n>>1]);

		for(int i=0; i<=n; ++i) g[i]+=B[i];

	}

	for(int i=0; i<=n; ++i) printf("%d ",(int)(g[i]%mod));

	return 0;

}

巴特西

8.5 正睿暑期集训营 Day2

2018.8.5 正睿暑期集训营 Day2

总结

A.占领地区(前缀和)

B.配对(组合)

C 导数卷积(NTT)

考试代码

T1

T2

T3

最新文章

热门文章