lyzlyz?lyzlyz!

听说这是JSOIDay5

膜了贵省的题目，感到不明觉厉。

条哥出去吔东西了，于是没有断网。

为了比赛公平，窝决定先泼会隔膜。

T1

这是一道好题。（然而窝不会做）

NiroBC将此题吊着打太强辣！！！

考虑三维容斥，即选i行j列k中颜色，表示i行j列可染可不染，另外n-i行和m-j列必定不染，k种颜色可用可不用，c-k种颜色必定不用。

那么答案就是

[tex]\sum\limits_{i = 0}^n {\sum\limits_{j = 0}^m {\sum\limits_{k = 0}^c {\mathop C\nolimits_n^i \mathop C\nolimits_m^j } } } \mathop C\nolimits_c^k {(k + 1)^{ij}}{( - 1)^{n + m + c - i - j - k}}[/tex]

于是n³枚举i、j、k就可以辣！（NiroBC还有一个不明觉厉的n²logn的做法）

T2

这是一道送分题。（其实是窝做过）

首先考虑这样一种暴力：枚举i，然后在前面找j，求出[j,i]的gcd。

那么可以优化，即已经知道了gcd[i,j]，那么gcd[i,j+1]=gcd(a[j+1],gcd[i,j])。

显然会发现有许多gcd是相同的，那么对于后面就没用辣~

那么只要维护一下不同的gcd就能AC了。（虽然理论上是n²的但是卡它的数据太难出了Orz）

T3

这是一道恶心题。（其实是窝懒得写）

首先对于每一条地铁线路构一条新的路径，其中上站的边权为1,0，下站的边权为0,0，中途乘坐的边权为0,1。

那么只要让第一维边权最短的情况下第二维边权最长，跑最短路就可以辣！

然并卵Spfa被卡飞。。

于是可以先dijkstra处理第一维最短路，那么出现在最短路上的边一定构成了一个DAG。

那么就可以拓扑排序辣！

【Codes】

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int mod=1000000007;
int n,m,p,i,j,k;
ll ans;
ll c[410][410];
ll mi[410][160010];
int main(){
	scanf("%d%d%d",&n,&m,&p);
	c[0][0]=1;
	for (i=1;i<=max(n,max(m,p));i++){
		c[i][0]=1;
		for (j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	}
	for (i=1;i<=p+1;i++){
		mi[i][0]=1;
		for (j=1;j<=n*m;j++)mi[i][j]=mi[i][j-1]*i%mod;
	}
	for (i=0;i<=n;i++)
		for (j=0;j<=m;j++)
			for (k=0;k<=p;k++){
				ll tmp=c[n][i]*c[m][j]%mod*c[p][k]%mod*mi[k+1][i*j]%mod;
				if ((n+m+p-i-j-k)&1)ans=(ans-tmp+mod)%mod;else ans=(ans+tmp)%mod;
			}
	printf("%lld\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int M=200010;
int n,i,j,r;
ll ans;
ll a[M],h[M][2],q[M][2];
ll gcd(ll x,ll y){
	if (!(x%y))return y;else return gcd(y,x%y);
}
int main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		for (j=1;j<=r;j++)h[j][0]=gcd(h[j][0],a[i]);
		h[++r][0]=a[i],h[r][1]=i;
		int cnt=1;
		q[1][0]=h[1][0],q[1][1]=h[1][1];
		ans=max(ans,h[1][0]*(i-h[1][1]+1));
		for (j=2;j<=r;j++)
			if (h[j][0]!=h[j-1][0]){
				q[++cnt][0]=h[j][0],q[cnt][1]=h[j][1];
				ans=max(ans,h[j][0]*(i-h[j][1]+1));
			}
		r=cnt;
		for (j=1;j<=cnt;j++)h[j][0]=q[j][0],h[j][1]=q[j][1];
	}
	printf("%lld\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define fi first
#define se second
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int M=5000010;
const int inf=1000000007;
int n,m,i,j,y,st,ed,tmp,cnt,edgenum,Edgenum;
char s[50];
int head[M],vet[M],next[M],Head[M],Vet[M],Next[M],Len[M],init[M],dis[M],Dis[M],len[M][2],inq[M],x[M],q[M];
priority_queue<PII,vector<PII>,greater<PII> >Q;
pair<ull,int>a[M];
int solve(){
	ull tmp=0;
	for (int i=0;i<strlen(s);i++)tmp=tmp*2333+s[i];
	int ans=a[lower_bound(a+1,a+m+1,make_pair(tmp,0))-a].se;
	return ans;
}
void addedge(int x,int y,int p,int q){
	vet[++edgenum]=y;
	next[edgenum]=head[x];
	head[x]=edgenum;
	len[edgenum][0]=p;
	len[edgenum][1]=q;
}
void Addedge(int x,int y,int p){
	Vet[++Edgenum]=y;
	Next[Edgenum]=Head[x];
	Head[x]=Edgenum;
	Len[Edgenum]=p;
	init[y]++;
}
void dijkstra(){
	for (i=1;i<=cnt;i++)dis[i]=inf;
	Q.push(make_pair(0,st));dis[st]=0;
	for (i=1;i<=cnt;i++)inq[i]=0;
	while (!Q.empty()){
		int u=Q.top().se;Q.pop();
		if (inq[u])continue;
		inq[u]=1;
		for (int e=head[u];e;e=next[e]){
			int v=vet[e];
			if (dis[u]+len[e][0]<dis[v]){
				dis[v]=dis[u]+len[e][0];
				Q.push(make_pair(dis[v],v));
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++){
		scanf("%s",s);
		for (j=0;j<strlen(s);j++)a[i].fi=a[i].fi*2333+s[j];
		a[i].se=i;
	}
	sort(a+1,a+m+1);
	cnt=m;
	for (i=1;i<=n;i++){
		scanf("%d",&tmp);
		scanf("%s",s);
		x[1]=solve();
		addedge(x[1],++cnt,1,0);
		for (j=2;j<=tmp;j++){
			scanf("%s",s);
			y=cnt,x[j]=solve();
			addedge(y,++cnt,0,1);
			addedge(x[j],cnt,1,0);
			addedge(cnt,x[j],0,0);
		}
		addedge(x[tmp],++cnt,1,0);
		for (j=tmp-1;j>=1;j--){
			y=cnt;
			addedge(y,++cnt,0,1);
			addedge(x[j],cnt,1,0);
			addedge(cnt,x[j],0,0);
		}
	}
	scanf("%s",s);
	st=solve();
	scanf("%s",s);
	ed=solve();
	dijkstra();
	for (i=1;i<=cnt;i++)
		for (int e=head[i];e;e=next[e])
			if (dis[i]+len[e][0]==dis[vet[e]])Addedge(i,vet[e],len[e][1]);
	int l=1,r=0;
	for (i=1;i<=cnt;i++)if (!init[i])q[++r]=i;
	while (l<=r){
		int u=q[l++];
		for (int e=Head[u];e;e=Next[e]){
			int v=Vet[e];
			init[v]--;
			if (init[v]==0)q[++r]=v;
		}
	}
	for (i=1;i<=cnt;i++){
		int u=q[i];
		for (int e=Head[u];e;e=Next[e]){
			int v=Vet[e];
			Dis[v]=max(Dis[v],Dis[u]+Len[e]);
		}
	}
	printf("%d\n%d\n",dis[ed],Dis[ed]);
}