AtCoder Regular Contest 067

\(AT\_arc067\_a\)
https://www.luogu.com.cn/problem/AT_arc067_a
题解：筛出\(1\sim n\)中质数，计算每个质数出现次数，再累乘即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N=1010,P=1e9+7;

int n;
int buc[N];
int prime[N],cnt;
bool st[N];

void sieve(int n){
	for(int i=2; i<=n; i++){
		if(!st[i]) prime[++cnt]=i;
		for(int j=1; j<=cnt&&prime[j]<=n/i; j++){
			st[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}

int main(){
	sieve(N-1);
	cin >> n;
	for(int i=1; i<=cnt; i++)
		for(int j=prime[i]; j<=n; j*=prime[i]) buc[i]+=n/j;
	int ans=1;
	for(int i=1; i<=cnt; i++) ans=(LL)ans*(buc[i]+1)%P;
	cout << ans << endl;
	return 0;
}

\(AT\_arc067\_b\)
https://www.luogu.com.cn/problem/AT_arc067_b
题解：由于所有城市都需要到达，所以可看成每条边都必须走，将每条边的两种走法取最小，并累加即可。

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main(){
	int n,a,b;
	cin >> n >> a >> b;
	int last;
	cin >> last;
	int ans=0;
	for(int i=2; i<=n; i++){
		int x;
		cin >> x;
		ans+=min(b,(x-last)*a);
		last=x;
	}
	cout << ans << endl;
	return 0;
}

\(AT\_arc067\_c\)
https://www.luogu.com.cn/problem/AT_arc067_c
题解：考虑\(dp\)，令\(f(i,j)\)为考虑人数为\(a\sim i\)的组，共选了\(j\)个人的方案数目。
有转移\(f(i,j)=f(i-1,j)+\sum[c(n-(j-k),k)*g(k,\frac{k}{i})*f(i-1,j-k)],i|k,i*c\leq k\leq i*d,k\leq j\)。
其中\(c(i,j)\)代表从\(i\)个人中选\(j\)个人的方案数，\(g(i,j)\)为将\(i\)个人等分为\(j\)组的方案数。
其中\(c(i,j)=c(i-1,j)+c(i-1,j-1),g(i,j)=\frac{1}{j!}\prod c(i-k*\frac{i}{j},\frac{i}{j}),\frac{i}{j}|k,0\leq k\leq j-1\)。
\(c\)递推复杂度为\(O(n^2)\)，\(f,g\)递推复杂度均为\(O(n^2logn)\)。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N=1010,P=1e9+7;

int n,a,b,c,d;
int fac[N],inv[N];
int C[N][N],g[N][N],f[N][N];

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=(LL)res*a%P;
		a=(LL)a*a%P;
		b>>=1;
	}
	return res;
}

int main(){
	fac[0]=1;
	for(int i=1; i<N; i++) fac[i]=(LL)fac[i-1]*i%P;
	for(int i=0; i<N; i++) inv[i]=qpow(fac[i],P-2);
	for(int i=0; i<N; i++) C[i][0]=1;
	for(int i=1; i<N; i++)
		for(int j=1; j<N; j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
	for(int i=1; i<N; i++)
		for(int j=1; j<=i; j++){
			if(i%j) continue;
			g[i][j]=1;
			for(int k=0; k<=j-1; k++) 
				g[i][j]=(LL)g[i][j]*C[i-i/j*k][i/j]%P;
			g[i][j]=(LL)g[i][j]*inv[j]%P;
		}
	cin >> n >> a >> b >> c >> d;
	f[a-1][0]=1;
	for(int i=a; i<=b; i++)
		for(int j=0; j<=n; j++){
			f[i][j]=f[i-1][j];
			for(int k=i*c; k<=i*d&&k<=j; k+=i)
				f[i][j]=(f[i][j]+(LL)C[n-(j-k)][k]*g[k][k/i]%P*f[i-1][j-k])%P;
		}
	cout << f[b][n] << endl;
	return 0;
}

\(AT\_arc067\_d\)
https://www.luogu.com.cn/problem/AT_arc067_d
题解：考虑暴力枚举左右端点，计算贡献即为\(\sum_{j} \max(b_{l,j},b_{l+1,j},...,b_{r,j})\),对每个票券，预处理\(st\)表即可。
考虑优化，令\(f(i)\)为左端点为\(i\)时对应的最优右端点，发现\(f(i)\)存在单调性。
证明:假设有\(i<j\)，且\(f(i)>f(j)\),对\(l=i\)来说,\(r=f(i)\)优于\(r=f(j)\),这说明\(max(f(j)+1,...,f(i))-max(i,...,f(j))>sum(f(i))-sum(f(j))\)。则当\(l=j\)时，\(max(f(j)+1,...,f(i))-max(j,...,f(j))>max(f(j)+1,...,f(i))-max(i,...,f(j))>sum(f(i))-sum(f(j))\),这同样说明\(r=f(i)\)比\(r=f(j)\)优秀，矛盾，于是\(f(i)\leq f(j)\)，则\(f\)存在单调性。
考虑经典分治做法，令\(solve(l,r,L,R)\)为\(i\)在\(l\sim r\)时候，\(f(i)\)在\(L\sim R\)。直接枚举\(j\in [\max(mid,L),R]\)，计算得到\(f(mid)\)，递归处理\(solve(l,mid-1,L,f(mid)),solve(mid+1,r,f(mid),R)\)即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N=210,M=5010;

int n,m,lg;
int a[M],b[M][N],len[M];
int g[M],f[N][2*M][16];
LL s[N];

inline int query(int t,int l,int r){
	int k=len[r-l+1];
	return max(f[t][l][k],f[t][r-(1<<k)+1][k]);
}

LL calc(int x,int y){
	LL res=0;
	for(int i=1; i<=m; i++) res+=query(i,x,y);
	res-=s[y]-s[x];
	return res;
}

void solve(int l,int r,int L,int R){
	if(l>r) return;
	int mid=l+r>>1,pos=max(L,mid);
	for(int i=max(L,mid); i<=R; i++)
		if(calc(mid,i)>calc(mid,pos)) pos=i;
	g[mid]=pos;
	if(l==r) return;
	solve(l,mid-1,L,pos);
	solve(mid+1,r,pos,R);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	lg=(int)(log(n)/log(2))+1;
	for(int i=1; i<=n; i++) len[i]=log(i)/log(2);
	for(int i=2; i<=n; i++) cin >> a[i];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) cin >> b[i][j];
	for(int i=1; i<=m; i++)
		for(int j=1; j<=n; j++) f[i][j][0]=b[j][i];
	for(int i=1; i<=m; i++)
		for(int k=1; k<=lg; k++)
			for(int j=1; j<=n; j++)
				f[i][j][k]=max(f[i][j][k-1],f[i][j+(1<<(k-1))][k-1]);
	for(int i=2; i<=n; i++) s[i]=s[i-1]+a[i];
	solve(1,n,1,n);
	LL ans=0;
	for(int i=1; i<=n; i++) ans=max(ans,calc(i,g[i]));
	cout << ans << endl;
	return 0;
}