2017 Multi-University Training Contest - Team 2

Puzzle

Sdjpx Is Happy

lbn187

#include<bits/stdc++.h>
#define N 3030
using namespace std;
int T,n,mx,mi,i,j,k,an,VV,w,mxx,t,la,a[N],ql[N],qr[N],F[N][N],G[N][N];
bool ok;
int getv(int L,int R){
	int w=0;
	for(int i=L;i<=R;i++)
		if(G[L][i]==G[L][R]&&F[L][i]-G[L][i]==i-L)w++;
	return w;
}
int main(){
	scanf("%d",&T);
	for(;T--;){
		scanf("%d",&n);mxx=0;an=0;VV=0;
		for(i=1;i<=n;i++)scanf("%d",&a[i]);
		for(i=1;i<=n;i++){
			F[i][i]=G[i][i]=a[i];
			for(j=i+1;j<=n;j++){
				F[i][j]=max(F[i][j-1],a[j]);
				G[i][j]=min(G[i][j-1],a[j]);
			}
		}
		for(i=j=1;i<=n;i++){
			mxx=max(mxx,a[i]);
			if(mxx==i){
				mi=1e9;ok=0;t=0;
				for(k=la=j;k<=i;k++){
					if(a[k]==i)ok=1;
					mi=min(mi,a[k]);
					if(i-mi+1==k-j+1&&ok){
						ql[++t]=la;
						qr[t]=k;
						la=k+1;
					}
				}
				if(t==1)VV=max(VV,0);else
				if(t==2)VV=max(VV,1);else
					for(k=2;k<t;k++)
						VV=max(VV,1+getv(ql[k],qr[k]));
				an++;
				j=i+1;
			}
		}
		printf("%d\n",an+VV);
	}
}

If the starlight never fade

TrickGCD

Aki

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 1e9 + 7;
int u[N], f[N], p[N], t, I[N];
long long i, j;
int mpow(int x, int n) {
	int res = 1;
	while (n) {
		if (n & 1) res = 1LL * res * x % M;
		n >>= 1;
		x = 1LL * x * x % M;
	}
	return res;
}
int mu[N], cnt[N];
int main() {
	mu[1] = M - 1;
	for(int i = 1; i <= 100000; i++)
	{
		for(int j = i + i; j <= 100000; j += i)
		{
			mu[j] = (mu[j] - mu[i] + M) % M;
		}
	}
	for(u[1]=1,i=2;i<N;i++){
		if(!f[i])p[++t]=i,u[i]=-1;
		for(j=1;j<=t&&i*p[j]<N;j++){
			f[i*p[j]]=1;
			if(i%p[j]==0)  break;
			u[i*p[j]]=-u[i];
		}
	}
	for (int i = 1; i <= 100000; ++ i) {
		assert((M - u[i]) % M == mu[i]);
	}
	int T, zzz = 0;
	scanf("%d", &T);
	while (T --) {
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= 100000; ++ i) cnt[i] = 0;
		int sum = 1;
		for (int i = 1; i <= n; ++ i) {
			int a;
			scanf("%d", &a);
			cnt[a] ++;
			sum = 1LL * sum * a % M;
		}
		for (int i = 100000; i >= 1; -- i) cnt[i] += cnt[i + 1];
		int ans = 0;
		for (int i = 1; i <= 100000; ++ i) {
			vector<int> res;
			for (int j = i; j <= 100000; j += i) {
				res.push_back(cnt[j]);
				//printf("res + %d\n", cnt[j]);
			}
			res.push_back(0);
			int tmp = 1;
			int cc = 0;
			for (int j = 0; j < (int) res.size() - 1; ++ j) {
				tmp = 1LL * tmp * mpow(j + 1, res[j] - res[j + 1]) % M;
				cc += res[j] - res[j + 1];
			}
			//puts("--");
			//printf("u[%d]=%d\n", i, u[i]);
			if (cc == n) {
				(ans += 1LL * mu[i] * tmp % M) %= M;
				//printf("%d\n", mu[i]);
			}
		}
		printf("Case #%d: %d\n", ++ zzz, (sum + ans) % M);
	}
}

String and String