「NOIP2020」排水系统(water)

题解1

我成功地把一道 $1000\mathrm{bytes}$ 的签到题活生生地整成了 $5000\mathrm{bytes}$ 的毒瘤题。

我一开始的做法是给所有点反过来做 拓扑排序 ，然后按 拓扑序 从大到小枚举点，暴力地把它的水流完。因为我估算时出了锅，没有考虑到通分后分母最大是 $60^{11}$ ，所以只开了 long long ，60分。

改题时我打了 高精度 ，非常麻烦，要重载 $+,\times ,÷,\mathrm{mod},>$ ，而在重载这些运算符的过程中我又用到了 $-,\le ,==$ ，因此把它们也重载了，加上一些运算符还要重载参数为 int 的，直接上了 $5000\mathrm{bytes}$ 。

改完之后调了好久，接着就是 TLE 的问题了。又卡了卡常才过去。

题解2

其实根本不用那么麻烦，如果先除再乘的话是可以用 long double 水过去的。

先除再乘就是 $$\begin{array}{r}\frac{a}{b}+\frac{c}{d}=\frac{\frac{\mathrm{lcm}(b,d)}{b}\cdot a+\frac{\mathrm{lcm}(b,d)}{d}\cdot c}{\mathrm{lcm}(b,d)}\end{array}$$

因此可以先处理出 $\mathrm{lcm}(b,d)$ ，再计算。

long double 的模运算可以用两种方法实现：

1. $a\mathrm{m}\mathrm{o}\mathrm{d}b=a-\lfloor \frac{a}{b}\rfloor \cdot b$ ；
2. 用 cmath 库下的 fmod 函数。

代码

我只写了第一种解法的代码：

#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("sse3","sse2","sse")
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cstring>
using namespace std;
namespace IO
{
	char p[15],buf[100005],outstr[5000005],*l=buf,*r=buf;
	int outlen=0;
	inline char gc()
	{return l==r&&(r=(l=buf)+fread(buf,1,100005,stdin),l==r)?EOF:*l++;}
	inline void read(int &k)
	{
		char ch;while(ch=gc(),ch<'0'||ch>'9');k=ch-48;
		while(ch=gc(),ch>='0'&&ch<='9') k=k*10+ch-48;
	}
	inline void print_int(int x)
	{
		if(!x) outstr[++outlen]='0';
		else
		{
			int len=0;
			while(x) p[++len]=x%10+48,x/=10;
			for(;len;--len) outstr[++outlen]=p[len];
		}
	}
}
using namespace IO;
#define fo(i,l,r) for(i=l;i<=r;++i)
#define M 500005
#define N 100005
const int P=10000;
int in[N],out[N],d[N],data[N],ans[N],ffir[N],
fto[M],fnex[M],gfir[N],gto[M],gnex[M],s,cnt;
inline int mymax(int x,int y){return x>y?x:y;}
struct bignum
{
	int a[11],len;
	bignum(){memset(a,0,sizeof a),len=1;}
	/*bool operator > (const bignum x) const
	{
		if(len^x.len) return len>x.len;
		for(int i=len;i;--i)
			if(a[i]^x.a[i]) return a[i]>x.a[i];
		return 0;
	}
	bool operator < (const bignum x) const
	{
		if(len^x.len) return len<x.len;
		for(int i=len;i;--i)
			if(a[i]^x.a[i]) return a[i]<x.a[i];
		return 0;
	}
	bool operator <= (const bignum x) const
	{return !(*this>x);}
	bool operator == (const bignum x) const
	{
		if(len^x.len) return 0;
		for(int i=len;i;--i)
			if(a[i]^x.a[i]) return 0;
		return 1;
	}
	bignum operator + (const bignum x)
	{
		bignum z=x;
		z.len=mymax(len,x.len);
		for(int i=1;i<=z.len;++i)
		{
			z.a[i]+=a[i];
			z.a[i+1]+=z.a[i]/P,
			z.a[i]%=P;
		}
		while(z.a[z.len+1])
			z.a[z.len+1]+=z.a[z.len]/P,
			z.a[z.len++]%=P;
		return z;
	}
	bignum operator + (const int x)
	{
		bignum z=*this;
		z.a[1]+=x;
		for(int i=1;i<=len;++i)
		{
			if(z.a[i]<P) break;
			z.a[i+1]+=z.a[i]%P,
			z.a[i]%=P;
		}
		while(z.a[z.len+1])
			z.a[z.len+1]+=z.a[z.len]/P,
			z.a[z.len++]%=P;
		return z;
	}
	bignum operator - (const bignum x)
	{
		bignum z=*this;
		for(int i=1;i<=len;++i)
		{
			z.a[i]-=x.a[i];
			if(z.a[i]<0) --z.a[i+1],z.a[i]+=P;
		}
		while(z.len>1&&!z.a[z.len]) --z.len;
		return z;
	}
	bignum operator * (const int x)
	{
		bignum z;z.len=len;
		for(int i=1;i<=len;++i)
		{
			z.a[i]+=a[i]*x,
			z.a[i+1]+=z.a[i]/P,
			z.a[i]%=P;
		}
		while(z.a[z.len+1])
			z.a[z.len+1]+=z.a[z.len]/P,
			z.a[z.len++]%=P;
		while(z.len>1&&!z.a[z.len]) --z.len;
		return z;
	}
	bignum operator * (const bignum y)
	{
		bignum z;int i,j;
		z.len=len+y.len-1;
		fo(i,1,len) fo(j,1,y.len)
			z.a[i+j-1]+=a[i]*y.a[j];
		fo(i,1,z.len)
			z.a[i+1]+=z.a[i]/P,
			z.a[i]%=P;
		while(z.a[z.len+1])
			z.a[z.len+1]+=z.a[z.len]/P,
			z.a[z.len++]%=P;
		while(z.len>1&&!z.a[z.len]) --z.len;
		return z;
	}
	bignum operator / (const bignum y)
	{
		bignum z;
		int l,r,s;
		z.len=len-y.len+1;
		for(int i=z.len;i;--i)
		{
			l=1,r=P-1,s=0;
			while(l<=r)
			{
				z.a[i]=l+r>>1;
				if(z*y<=*this) s=z.a[i],l=z.a[i]+1;
				else r=z.a[i]-1;
			}
			z.a[i]=s;
		}
		while(z.len>1&&!z.a[z.len]) --z.len;
		return z;
	}
	bignum operator % (const bignum y)
	{
		if(*this<y) return *this;
		bignum z;
		int l,r,s;
		z.len=len-y.len+1;
		for(int i=z.len;i;--i)
		{
			l=1,r=P-1,s=0;
			while(l<=r)
			{
				z.a[i]=l+r>>1;
				if(z*y<=*this) s=z.a[i],l=z.a[i]+1;
				else r=z.a[i]-1;
			}
			z.a[i]=s;
		}
		while(!z.a[z.len]) --z.len;
		return *this-z*y;
	}*/
}_1;
inline bool greater(const bignum x,bignum &y)
{
	if(x.len^y.len) return x.len>y.len;
	for(int i=x.len;i;--i)
		if(x.a[i]^y.a[i]) return x.a[i]>y.a[i];
	return 0;
}
inline bool le(const bignum x,bignum &y)
{return !greater(x,y);}
inline bignum plus(const bignum x,const bignum y)
{
	bignum z=x;
	z.len=mymax(x.len,y.len);
	for(int i=1;i<=z.len;++i)
	{
		z.a[i]+=y.a[i],
		z.a[i+1]+=z.a[i]/P,
		z.a[i]%=P;
	}
	while(z.a[z.len+1])
		z.a[z.len+1]+=z.a[z.len]/P,
		z.a[z.len++]%=P;
	return z;
}
inline bignum plus(bignum &x,int &y)
{
	bignum z=x;
	z.a[1]+=y;
	for(int i=1;i<=z.len;++i)
	{
		if(z.a[i]<P) break;
		z.a[i+1]+=z.a[i]%P,
		z.a[i]%=P;
	}
	while(z.a[z.len+1])
		z.a[z.len+1]+=z.a[z.len]/P,
		z.a[z.len++]%=P;
	return z;
}
inline bignum minus(bignum &x,const bignum y)
{
	bignum z=x;
	for(int i=1;i<=z.len;++i)
	{
		z.a[i]-=y.a[i];
		if(z.a[i]<0) --z.a[i+1],z.a[i]+=P;
	}
	while(z.len>1&&!z.a[z.len]) --z.len;
	return z;
}
inline bignum times(bignum &x,int &y)
{
	bignum z;z.len=x.len;
	for(int i=1;i<=z.len;++i)
	{
		z.a[i]+=x.a[i]*y,
		z.a[i+1]+=z.a[i]/P,
		z.a[i]%=P;
	}
	while(z.a[z.len+1])
		z.a[z.len+1]+=z.a[z.len]/P,
		z.a[z.len++]%=P;
	while(z.len>1&&!z.a[z.len]) --z.len;
	return z;
}
inline bignum times(bignum &x,bignum &y)
{
	bignum z;int i,j;
	z.len=x.len+y.len-1;
	fo(i,1,x.len) fo(j,1,y.len)
		z.a[i+j-1]+=x.a[i]*y.a[j];
	fo(i,1,z.len)
		z.a[i+1]+=z.a[i]/P,
		z.a[i]%=P;
	while(z.a[z.len+1])
		z.a[z.len+1]+=z.a[z.len]/P,
		z.a[z.len++]%=P;
	while(z.len>1&&!z.a[z.len]) --z.len;
	return z;
}
inline bignum div(bignum &x,bignum &y)
{
	bignum z;
	int l,r,s;
	z.len=x.len-y.len+1;
	for(int i=z.len;i;--i)
	{
		l=1,r=P-1,s=0;
		while(l<=r)
		{
			z.a[i]=l+r>>1;
			if(le(times(z,y),x)) s=z.a[i],l=z.a[i]+1;
			else r=z.a[i]-1;
		}
		z.a[i]=s;
	}
	while(z.len>1&&!z.a[z.len]) --z.len;
	return z;
}
inline bignum mod(bignum &x,bignum &y)
{
	if(greater(y,x)) return x;
	bignum z;
	int l,r,s;
	z.len=x.len-y.len+1;
	for(int i=z.len;i;--i)
	{
		l=1,r=P-1,s=0;
		while(l<=r)
		{
			z.a[i]=l+r>>1;
			if(le(times(z,y),x)) s=z.a[i],l=z.a[i]+1;
			else r=z.a[i]-1;
		}
		z.a[i]=s;
	}
	while(z.len>1&&!z.a[z.len]) --z.len;
	return minus(x,times(z,y));
}
inline void print(bignum &x,const char ch)
{
	print_int(x.a[x.len]);
	for(int i=x.len-1;i;--i)
		outstr[++outlen]=x.a[i]/1000+48,
		outstr[++outlen]=x.a[i]/100%10+48,
		outstr[++outlen]=x.a[i]/10%10+48,
		outstr[++outlen]=x.a[i]%10+48;
	outstr[++outlen]=ch;
}
inline bignum gcd(bignum x,bignum y)
{
	if(x.len==1&&!x.a[1]) return _1;
	if(y.len==1&&!y.a[1]) return _1;
	bignum r=mod(x,y);
	while(r.len>1||r.a[1]) x=y,y=r,r=mod(x,y);
	return y;
}
struct num
{
	bignum p,q;
	num(){q.a[1]=1;}
	inline void add(num x)
	{
		p=plus(times(p,x.q),times(x.p,q)),q=times(q,x.q);
		bignum tmp=gcd(p,q);
		p=div(p,tmp),q=div(q,tmp);
	}
}a[N],tmp;
inline void graph_Sort(int n)
{
	int head=0,tail=0,x,i;
	fo(i,1,n) if(!out[i])
		data[++tail]=i,ans[++cnt]=i;
	while(head<=tail)
	{
		x=data[++head];
		for(i=gfir[x];i;i=gnex[i])
		{
			--out[gto[i]];
			if(!out[gto[i]]) data[++tail]=gto[i];
		}
	}
}
int main()
{
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	int n,m,x,i,j;
	read(n),read(m);
	_1.a[1]=1;
	fo(i,1,n)
	{
		read(d[i]);
		fo(j,1,d[i])
		{
			read(x),++out[i],++in[x],
			fto[++s]=x,fnex[s]=ffir[i],ffir[i]=s,
			gto[s]=i,gnex[s]=gfir[x],gfir[x]=s;
		}
	}
	fo(i,1,m) a[i].p.a[1]=1;
	graph_Sort(n);
	for(int j=n;j;--j)
	{
		x=data[j],tmp=a[x],tmp;
		tmp.q=times(tmp.q,d[x]);
		for(i=ffir[x];i;i=fnex[i])
			a[fto[i]].add(tmp);
	}
	fo(i,1,cnt) print(a[ans[i]].p,' '),print(a[ans[i]].q,'\n');
	fwrite(outstr+1,outlen,1,stdout);
	return 0;
}