2018.11.6 正睿停课训练 Day17

虽然题都改了但还是咕了无数天的博客...
期望得分：忘了
实际得分：55+(80->60)+20

A chinese(思路计数)

考虑(sum i*f[i])的意义，即所有方案中炼字的个数和。
考虑枚举每个数(i∈[1,k])作为炼字时出现在哪些方案中（不是算一种方案有哪些炼字，不会算重啊）。
值(i)在某一个位置作为炼字时，它的方案数为((i-1)^{n-1+m-1}*k^{(n-1)*(m-1)})。同时每个位置是等价的，最后乘(n*m)就好了。
枚举(i)就行了。复杂度(O(klog v))。

//587ms	512kb
#include <cstdio>
#define mod 1000000007
typedef long long LL;

inline int FP(int x,int k)
{
	int t=1;
	for(; k; k>>=1,x=1ll*x*x%mod)
		if(k&1) t=1ll*t*x%mod;
	return t;
}

int main()
{
	int n,m,K; scanf("%d%d%d",&n,&m,&K);
	if(n==1&&m==1) return printf("%d
",K),0;
	LL ans=0;
	for(int i=2; i<=K; ++i) ans+=FP(i-1,n+m-2);
	printf("%lld
",ans%mod*FP(K,1ll*(n-1)*(m-1)%(mod-1))%mod*n%mod*m%mod);

	return 0;
}

B physics(单调队列/剪枝 DP)

题目链接

带修改（只将1修改为0）最大全1正方形。
由于数据比较水，每次修改时判一下修改点是否在当前最大矩形内，如果不在就不用DP了。然后你就A了。。

正解：
对于一次询问的情况，我们可以预处理up[i][j]表示从(i,j)往上连续的1有多少。令L[i]表示当前行在第i列左边第一个up比它小的位置，R[i]同理，可以用单调栈预处理。那么答案就是(max{min{up[row][i],R[i]-L[i]-1}})。
如果有多次修改，首先可以倒序做，这样答案就是单调不降的了（不需要每次在整个矩形里求max）。
修改一个点((x,y))只会影响这一列的up,down（down定义类似up），可以暴力修改。
现在只需要对(x)这一行算一遍就行了。但是有up和down两个值，直接求最大正方形不好算，但是可以求是否有大小为(k)的最大全1正方形。
存在大小为(k)的正方形，也就是存在一个(i)满足(min{i,min{up[i-k+1,i]}+min{down[i-k+1,k]}-1}>=k)，这就是滑动窗口了。
而且答案最多只会变(n)次，所以对每次修改不断尝试更新答案就可以了。
复杂度(O(n^2+nq))。因为数据弱跑的比暴力+剪枝慢。

确实有分治做法，但是感觉常数更大的一匹啊？（别问我怎么知道的）

//6558ms	47884kb
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=2003;

int A[N][N],up[N][N],down[N][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;
}
int preSolve(int n,int m)
{
	static int L[N],R[N],sk[N];
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j) up[i][j]=A[i][j]?up[i-1][j]+1:0;
	for(int i=n; i; --i)
		for(int j=1; j<=m; ++j) down[i][j]=A[i][j]?down[i+1][j]+1:0;
	int ans=0;
	for(int i=1; i<=n; ++i)
	{
		up[i][0]=up[i][m+1]=-1;
		for(int j=1,top=0; j<=m+1; ++j)
		{
			while(up[i][sk[top]]>up[i][j]) R[sk[top--]]=j;
			sk[++top]=j;
		}
		for(int j=m,top=0; ~j; --j)
		{
			while(up[i][sk[top]]>up[i][j]) L[sk[top--]]=j;
			sk[++top]=j;
		}
		for(int j=1; j<=m; ++j) ans=std::max(ans,std::min(up[i][j],R[j]-L[j]-1));
	}
	return ans;
}
void Modify(int n,int c)
{
	for(int i=1; i<=n; ++i) up[i][c]=A[i][c]?up[i-1][c]+1:0;
	for(int i=n; i; --i) down[i][c]=A[i][c]?down[i+1][c]+1:0;
}
bool Update(int m,int r,int K)
{
	static int q1[N],v1[N],q2[N],v2[N];
	int *up=::up[r],*down=::down[r];
	for(int i=1,h1=1,t1=0,h2=1,t2=0; i<=m; ++i)
	{
		while(h1<=t1 && i-q1[h1]>=K) ++h1;
		while(h1<=t1 && up[i]<=v1[t1]) --t1;
		q1[++t1]=i, v1[t1]=up[i];
		while(h2<=t2 && i-q2[h2]>=K) ++h2;
		while(h2<=t2 && down[i]<=v2[t2]) --t2;
		q2[++t2]=i, v2[t2]=down[i];
		if(std::min(i,v1[h1]+v2[h2]-1)>=K) return 1;
	}
	return 0;
}

int main()
{
	static int Ans[10005],qx[10005],qy[10005];//not N...
	int n=read(),m=read(),Q=read();
	for(int i=1; i<=n; ++i)
	{
		register char c=gc(); while(c!='+'&&c!='-') c=gc();
		A[i][1]=c=='+';
		for(int j=2; j<=m; ++j) A[i][j]=gc()=='+';
	}
	for(int i=1; i<=Q; ++i) A[qx[i]=read()][qy[i]=read()]=0;
	int ans=preSolve(n,m);
	for(int i=Q; i; --i)
	{
		Ans[i]=ans, A[qx[i]][qy[i]]=1, Modify(n,qy[i]);
		while(Update(m,qx[i],ans+1)) ++ans;
	}
	for(int i=1; i<=Q; ++i) printf("%d
",Ans[i]);

	return 0;
}

暴力+剪枝：

//1750ms	32068kb
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=2003;

int A[N][N],f[N][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;
}

int main()
{
	int n=read(),m=read(),Q=read();
	for(int i=1; i<=n; ++i)
	{
		register char c=gc(); while(c!='+'&&c!='-') c=gc();
		A[i][1]=c=='+';
		for(int j=2; j<=m; ++j) A[i][j]=gc()=='+';
	}
	int ansx,ansy,ans=0;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j)
			f[i][j]=A[i][j]?std::min(f[i-1][j-1],std::min(f[i-1][j],f[i][j-1]))+1:0,
			f[i][j]>ans&&(ans=f[i][j],ansx=i,ansy=j);
	for(int x,y; Q--; )
	{
		A[x=read()][y=read()]=0;
		if(x>=ansx-ans&&x<=ansx&&y>=ansy-ans&&y<=ansy)
		{
			ans=0;
			for(int i=1; i<=n; ++i)
				for(int j=1; j<=m; ++j)
					f[i][j]=A[i][j]?std::min(f[i-1][j-1],std::min(f[i-1][j],f[i][j-1]))+1:0,
					f[i][j]>ans&&(ans=f[i][j],ansx=i,ansy=j);
		}
		printf("%d
",ans);
	}

	return 0;
}

C chemistry(期望 DP)

题目链接

之前怎么没写思路啊。。
过了这么久不想写了，粘solution了。
感觉挺nb的。。

//364ms	17200kb
#include <cstdio>
#include <cctype>
#include <cstring>
#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 mod 1000000007
#define Mod(x) x>=mod&&(x-=mod)
typedef long long LL;
const int N=2e5+5;

int n,K,P,A[N],C[13][13],Enum,H[N],nxt[N<<1],to[N<<1],f[N],g[N][11];
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 int FP(int x,int k)
{
	int t=1;
	for(; k; k>>=1,x=1ll*x*x%mod)
		if(k&1) t=1ll*t*x%mod;
	return t;
}
inline void AE(int u,int v)
{
	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
void DFS(int x,int fa)
{
	int pw=P;
	for(int i=1; i<=K; ++i) g[x][i]=pw=1ll*pw*A[x]%mod;//f[x][i]=g[x][i]=P*A[x]^i
	f[x]=pw;
	for(int i=H[x],v; i; i=nxt[i])
		if((v=to[i])!=fa)
		{
			DFS(v,x);
			LL tmp=f[x]+f[v];
			for(int j=1; j<K; ++j) tmp+=1ll*C[K][j]*g[x][j]%mod*g[v][K-j]%mod;
			f[x]=tmp%mod;
			for(int j=K; j; --j)
			{
				tmp=1ll*P*g[v][j]+g[x][j];
				for(int k=1; k<j; ++k)
					tmp+=1ll*C[j][k]*g[x][k]%mod*g[v][j-k]%mod;
				g[x][j]=tmp%mod;
			}
		}
}

int main()
{
	n=read(),K=read(),P=1ll*read()*FP(read(),mod-2)%mod;
	for(int i=1; i<=n; ++i) A[i]=read();
	for(int i=1; i<n; ++i) AE(read(),read());
	C[0][0]=1;
	for(int i=1; i<=K; ++i)
	{
		C[i][0]=C[i][i]=1;
		for(int j=1; j<i; ++j) C[i][j]=C[i-1][j]+C[i-1][j-1], Mod(C[i][j]);
	}
	DFS(1,1);
	printf("%d
",f[1]);

	return 0;
}

考试代码

A

#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod 1000000007
typedef long long LL;
const int N=5;

int n,m,K,f[N*N],A[N][N];

bool OK(int x,int y)
{
	int a=A[x][y];
	for(int i=1; i<=n; ++i) if(A[i][y]>=a&&i!=x) return 0;
	for(int i=1; i<=m; ++i) if(A[x][i]>=a&&i!=y) return 0;
	return 1;
}
void Calc()
{
	static bool vis[N];
	memset(vis,0,sizeof vis);
	int ans=0;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j)
			if(!vis[j]&&OK(i,j))
				{vis[j]=1, ++ans; break;}
	++f[ans];
}
void DFS(int x,int y)
{
	if(y>m) ++x,y=1;
	if(x>n)
	{
		Calc();
		return;
	}
	for(int i=1; i<=K; ++i) A[x][y]=i, DFS(x,y+1);
}
void Solve()
{
	DFS(1,1);
	LL ans=0;
	for(int i=0; i<=n*m; ++i) ans+=1ll*i*f[i]%mod;
	for(int i=0; i<=n*m; ++i) printf("%d ",f[i]); puts("");
	printf("n:%d m:%d K:%d ans:",n,m,K);
	printf("%d
",(int)(ans%mod));
//	printf("%d,",(int)(ans%mod));
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);

//	for(n=2; n<=2; ++n)
//		for(m=2; m<=2; ++m)
//			for(K=1; K<=15; ++K) Solve();
//	return 0;
	int n,m,K; scanf("%d%d%d",&n,&m,&K); ::n=n, ::m=m, ::K=K;
	if(n==4&&m==4&&K>=3)
	{
		if(K==3) printf("%d
",20470320);
		else if(K==4) printf("%d
",330277355);
//		else if(K==5) printf("%d
",);
		return 0;
	}
	DFS(1,1);
	LL ans=0;
	for(int i=0; i<=n*m; ++i) ans+=1ll*i*f[i]%mod;
	printf("%d
",(int)(ans%mod));

	return 0;
}

B

写分治T掉暴力能得的20分

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=2003;

int A[N][N],f[N][N],mxu[N][N],mxd[N][N],mxl[N][N],mxr[N][N],ans[10000005][2],Ans;
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 Calc(int n,int m)
{
	int ans=0;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j)
			ans=std::max(ans,f[i][j]=A[i][j]?std::min(f[i-1][j-1],std::min(f[i-1][j],f[i][j-1]))+1:0);
	return ans;
}
void Violence(int n,int m,int Q)
{
	while(Q--) A[read()][read()]=0, printf("%d
",Calc(n,m));
}
inline int Go_left(int x,int y)
{
	int ans=0;
	while(A[x][y-ans]) ++ans;
	return ans;
}
inline int Go_right(int x,int y)
{
	int ans=0;
	while(A[x][y+ans]) ++ans;
	return ans;
}
inline int Go_up(int x,int y)
{
	int ans=0;
	while(A[x-ans][y]) ++ans;
	return ans;
}
inline int Go_down(int x,int y)
{
	int ans=0;
	while(A[x+ans][y]) ++ans;
	return ans;
}
inline bool OK(int *A,int *A2,int l,int r,int x)
{
	static int q[N],p[N],q2[N],p2[N];
	int h=1,t=0,h2=1,t2=0;
	for(int i=l; i<=r; ++i)
	{
		while(h<=t&&q[t]>=A[i]) --t;
		q[++t]=A[i], p[t]=i;
		while(h2<=t2&&q2[t2]>=A2[i]) --t2;
		q2[++t2]=A2[i], p2[t2]=i;
		while(p[h]<=i-x) ++h;
		while(p2[h2]<=i-x) ++h2;
		if(i>=x&&q[h]+q2[h2]-1>=x) return 1;
	}
	return 0;
}
int Row(int row,int l,int r)
{
	int L=2,R=r-l+1,mid,ans=1;
	while(L<=R)
		if(OK(mxu[row],mxd[row],l,r,mid=L+R>>1)) ans=mid,L=mid+1;
		else R=mid-1;
	return ans;
}
inline bool OK2(int col,int l,int r,int x)
{
	static int q[N],p[N],q2[N],p2[N];
	int h=1,t=0,h2=1,t2=0;
	for(int i=l; i<=r; ++i)
	{
		while(h<=t&&q[t]>=mxl[i][col]) --t;
		q[++t]=mxl[i][col], p[t]=i;
		while(h2<=t2&&q2[t2]>=mxr[i][col]) --t2;
		q2[++t2]=mxr[i][col], p2[t2]=i;
		while(p[h]<=i-x) ++h;
		while(p2[h2]<=i-x) ++h2;
		if(i>=x&&q[h]+q2[h2]-1>=x) return 1;
	}
	return 0;
}
int Colu(int col,int u,int d)
{
	int L=2,R=d-u+1,mid,ans=1;
	while(L<=R)
		if(OK2(col,u,d,mid=L+R>>1)) ans=mid,L=mid+1;
		else R=mid-1;
	return ans;
}
int Pre(int u,int d,int l,int r,int rt)
{
	if(u>d||l>r) return 0;
//	printf("Pre(%d~%d %d~%d %d)
",u,d,l,r,rt);
	if(d-u>=r-l)
	{
		int mid=u+d>>1;
//		printf("mid:%d
",mid);
		for(int i=l; i<=r; ++i) mxu[mid][i]=Go_up(mid,i), mxd[mid][i]=Go_down(mid,i);
//		for(int i=l; i<=r; ++i) printf("mxu[%d][%d]=%d mxd[%d][%d]=%d
",mid,i,mxu[mid][i],mid,i,mxd[mid][i]);
		int res=Row(mid,l,r);
		ans[rt][0]=Pre(u,mid-1,l,r,rt<<1), ans[rt][1]=Pre(mid+1,d,l,r,rt<<1|1);
//		printf("1 mid:%d Pre(%d~%d %d~%d %d) res:%d %d %d
",mid,u,d,l,r,rt,res,ans[rt][0],ans[rt][1]);
		return std::max(res,std::max(ans[rt][0],ans[rt][1]));
	}
	else
	{
		int mid=l+r>>1;
		for(int i=u; i<=d; ++i) mxl[i][mid]=Go_left(i,mid), mxr[i][mid]=Go_right(i,mid);
		int res=Colu(mid,u,d);
		ans[rt][0]=Pre(u,d,l,mid-1,rt<<1), ans[rt][1]=Pre(u,d,mid+1,r,rt<<1|1);
//		printf("2 mid:%d Pre(%d~%d %d~%d %d) res:%d %d %d
",mid,u,d,l,r,rt,res,ans[rt][0],ans[rt][1]);
		return std::max(res,std::max(ans[rt][0],ans[rt][1]));
	}
}
void Solve(int u,int d,int l,int r,int x,int y,int rt)
{
	if(u>d||l>r) return;
	if(d-u>=r-l)
	{
		int mid=u+d>>1;
		if(x>mid)
		{
			for(int i=l; i<=r; ++i) mxd[mid][i]=Go_down(mid,i);
			Ans=std::max(Ans,std::max(Row(mid,l,r),ans[rt][0])), Solve(mid+1,d,l,r,x,y,rt<<1|1);
		}
		else if(x<mid)
		{
			for(int i=l; i<=r; ++i) mxu[mid][i]=Go_up(mid,i);
			Ans=std::max(Ans,std::max(Row(mid,l,r),ans[rt][1])), Solve(u,mid-1,l,r,x,y,rt<<1);
		}
		else mxu[x][y]=mxd[x][y]=0, Ans=std::max(Ans,std::max(ans[rt][0],ans[rt][1]));
	}
	else
	{
		int mid=l+r>>1;
		if(y>mid)
		{
			for(int i=u; i<=d; ++i) mxl[i][mid]=Go_left(i,mid);
			Ans=std::max(Ans,std::max(Colu(mid,u,d),ans[rt][0])), Solve(u,d,mid+1,r,x,y,rt<<1|1);
		}
		else if(y<mid)
		{
			for(int i=u; i<=d; ++i) mxr[i][mid]=Go_right(i,mid);
			Ans=std::max(Ans,std::max(Colu(mid,u,d),ans[rt][1])), Solve(u,d,l,mid-1,x,y,rt<<1);
		}
		else mxl[x][y]=mxr[x][y]=0, Ans=std::max(Ans,std::max(ans[rt][0],ans[rt][1]));
	}
}

int main()
{
//	freopen("ex_physics1.in","r",stdin);
//	freopen(".out","w",stdout);

	int n=read(),m=read(),Q=read();
	for(int i=1; i<=n; ++i)
	{
		register char c=gc(); while(c!='+'&&c!='-') c=gc();
		A[i][1]=c=='+';
		for(int j=2; j<=m; ++j) A[i][j]=gc()=='+';
	}
	if(1ll*n*m*Q<=2e8) return Violence(n,m,Q),0;
	Pre(1,n,1,m,1);
	for(int x,y; Q--; )
		x=read(),y=read(),A[x][y]=0,Ans=1,Solve(1,n,1,m,x,y,1),printf("%d
",Ans);

	return 0;
}

C

#include <cstdio>
#include <cctype>
#include <cstring>
#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 mod 1000000007
#define Mod(x) x>=mod&&(x-=mod)
typedef long long LL;
const int N=2e5+5;

int n,K,P,A[N],pw[N],pw2[N],Enum,H[N],nxt[N<<1],to[N<<1],f[105][105],g[105][105],sz[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 int FP(int x,int k)
{
	int t=1;
	for(; k; k>>=1,x=1ll*x*x%mod)
		if(k&1) t=1ll*t*x%mod;
	return t;
}
inline void AE(int u,int v)
{
	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
namespace Subtask1
{
	const int N=204;
	int n,K,f[N];
	LL Ans,Sum;
	bool chose[N];
	void DFS2(int x,int fa)
	{
		if(chose[x])
		{
			f[x]=0;
			for(int i=H[x],v; i; i=nxt[i])
				if((v=to[i])!=fa) DFS2(v,x);
		}
		else
		{
			f[x]=A[x];
			for(int i=H[x],v; i; i=nxt[i])
				if((v=to[i])!=fa) DFS2(v,x), f[x]+=f[v], Mod(f[x]);
			if(chose[fa]) Sum+=FP(f[x],K);
		}
	}
	void Calc(int t)
	{
		chose[0]=1, Sum=0, DFS2(1,0), Ans+=Sum%mod*pw[t]%mod*pw2[n-t]%mod;
	}
	void DFS(int x,int t)
	{
		if(x>n) {Calc(t); return;}
		DFS(x+1,t), chose[x]=1, DFS(x+1,t+1), chose[x]=0;
	}
	void Main()
	{
		n=::n, K=::K, DFS(1,0), printf("%d",(int)(Ans%mod));
	}
}
void DFS(int x,int fa)
{
	static int tmp[105];
	f[x][1]=A[x], sz[x]=1;
	for(int i=H[x],v; i; i=nxt[i])
		if((v=to[i])!=fa)
		{
			DFS(v,x);
			memset(tmp,0,sizeof tmp);
			for(int j=0; j<=sz[x]; ++j)
				for(int k=1; k<=sz[v]; ++k)
					tmp[j+k]+=((g[x][j]+g[v][k])%mod+FP(f[v][k],K))%mod, Mod(tmp[j+k]);
			memcpy(g[x],tmp,sizeof tmp);
			memset(tmp,0,sizeof tmp);
			for(int j=1; j<=sz[x]; ++j)
				for(int k=0; k<=sz[v]; ++k)
					printf("tmp[%d]=f[x][%d]+f[v][%d]=%d
",j+k,j,k,f[x][j]+f[v][k]),
					tmp[j+k]+=f[x][j]+f[v][k], Mod(tmp[j+k]);
			memcpy(f[x],tmp,sizeof tmp);
			sz[x]+=sz[v];
			printf("%d->%d
",x,v);
			for(int i=1; i<=n; ++i) printf("f[%d][%d]=%d g[%d][%d]=%d
",x,i,f[x][i],x,i,g[x][i]);
		}
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);

	n=read(),K=read(),P=1ll*read()*FP(read(),mod-2)%mod;
	pw[0]=pw2[0]=1, pw[1]=mod+1-P,pw2[1]=P;//pw:被活化的概率 
	for(int i=1; i<=n; ++i) pw[i]=1ll*pw[i-1]*(mod+1-P)%mod, pw2[i]=1ll*pw2[i-1]*P%mod;
	for(int i=1; i<=n; ++i) A[i]=read();
	for(int i=1; i<n; ++i) AE(read(),read());
	if(n<=200) return Subtask1::Main(),0;
//	DFS(1,1);
//	LL ans=0;
//	for(int i=1; i<=n; ++i) printf("%d:%d %d
",i,f[1][i],g[1][i]);
//	for(int i=1; i<=n; ++i) ans+=1ll*pw2[i]*pw[n-i]%mod*(FP(f[1][i],K)+g[1][i])%mod;
//	printf("%d
",(int)(ans%mod));

	return 0;
}

11.6 正睿停课训练 Day17

2018.11.6 正睿停课训练 Day17

A chinese(思路 计数)

B physics(单调队列/剪枝 DP)

C chemistry(期望 DP)

考试代码

A

B

C

A chinese(思路计数)