啊啊啊啊，第一次停（dìng）课咯，感觉要记录一下联赛dìng课期间的颓废生活

第二弹：2015.11.04&2015.11.05膜你题

 2015.11.04 膜你题【NOIP2015 Day 3】 

T1:mazey(u)

第一次做交互题哎，感觉还挺好玩（大雾）

其实就是DFS，然后不要忘了走回去，还有就是到了1800步要跳出（右边大神没成功跳出爆零了QAQ

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#include"maze_lib.h"
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
bool f[220][220];
int tot;
void DFS(int xx,int yy)
{
	for (int i=0;i<4;++i)
	if (f[xx+dx[i]][yy+dy[i]])
	{
		int tmp=move(i); tot++;
		if (tot>=1800) return;
		if (tmp==0) f[xx+dx[i]][yy+dy[i]]=0;
		else
		{
			f[xx+dx[i]][yy+dy[i]]=0;
			DFS(xx+dx[i],yy+dy[i]);
			if (i==1) move(0);
			else if (i==0) move(1);
			else if (i==2) move(3);
			else if (i==3) move(2);
			tot++;
			if (tot>=1800) return;
		}
	}
}
void work()
{
	memset(f,1,sizeof(f));
	tot=0;
	DFS(100,100);
}

T2:0

其实是有规律的，a(n) = 10/9 - 10^n/9 + n + n*10^n，但是模数不是质数导致逆元爆炸，比较受伤

像是快速面炸掉了？（我错了wu

【未满分代码】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define LL long long
using namespace std;
LL ans,nn,k,q,n,mod;
LL ksm(LL xx,LL yy)
{
	LL tmp=1ll,sum=0;
	while (yy)
	{
		if (yy&1) sum=(sum*tmp)%mod;
		yy>>=1;
		tmp=(tmp*tmp)%mod;
	}
	return tmp;
}
int main()
{
	while (scanf("%lld%lld",&n,&mod)!=EOF)
	{
		if (mod==1ll){	puts("0"); continue;}
		if (mod==2ll)
		{
			if (n==1) puts("1");  else
			{ if (n&1) puts("0"); else puts("1");}	continue;
		}
		n--;
		nn=n%mod; k=ksm(10,n);
		if (n<=1000)
		{
			if (n==0) 	{	puts("1"); continue;}
			LL tmp=1;
			for (int i=2;i<=n;++i) tmp=(tmp*10%mod+1)%mod;
			ans=(((1+nn)%mod+nn*k%mod)%mod+mod-tmp)%mod;
			printf("%lld\n",ans); continue;
		} 
		q=ksm(9,mod-2);
		ans=(((1+nn)%mod+nn*k%mod)%mod+mod-q*k%mod)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}

T3:function    T4:Ž幻♂想♂乡

看上去不可做便弃疗了，暴力卷分走人

2015.11.05膜你题【NOIP2015模拟赛】

T1：树的统计I

手算+脑补发现看上去像n^(n-1)，于是二话不说就写了程序

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
LL n,mod;
LL ksm(LL xx,LL yy)
{
	LL sum=1,tmp=xx;
	while (yy)
	{
		if (yy&1) sum=sum*tmp%mod;
		tmp=tmp*tmp%mod; yy>>=1;
	}
	return sum;
}
int main()
{
	scanf("%lld%lld",&n,&mod);
	printf("%lld",ksm(n%mod,n-1));
	return 0;
}

【猛然发现昨天快速幂写错了~~~~(>_<)~~~~】

T2：树的统计II

不会。。。

看qlj打表，找到规律，然而要用矩阵乘法，弃疗QAQ（感觉矩阵乘法真心需要恶补啊啊啊啊

T3：树的统计II

卡特兰数，虽然不知道到底为什么是，但是看到数据的第一眼就感觉有点恍恍惚惚，然后算了前几个就当卡特兰数处理辣

h(n)=C(2n,n)/(n+1) (n=0,1,2,...) 又 h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

然而依旧逆元杀啊

这是一个只能过60分的程序QAQ【吐槽：边上那位拉板子AK辣，大家快去%%%→_→

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
LL ans,mod,n;
LL a[500000],b[500000];
LL mul(LL xx,LL yy)
{
	if (yy==0) return 1ll;
	LL tmp=mul(xx,yy>>1)%mod;
	tmp=tmp*tmp%mod;
	if (yy&1) tmp=tmp*xx%mod;
	return tmp;
}
int main()
{
	scanf("%lld%lld",&n,&mod);
	if (n<=100000)
	{
		n--;
		memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
		ans=1ll;
		for (LL i=2;i<=n*2ll;++i)
		if (a[i]==0)
		{
			LL j=i*i;
			while (j<=n*2ll) a[j]=i,j+=i;
		}
		for (LL i=2;i<=n;++i) b[i]=-1;
		for (LL i=n+2;i<=n*2ll;++i) b[i]=1;
		for (LL i=n*2ll;i>=2;--i)
			if (a[i]==0) 
				ans=ans*mul(i,b[i])%mod;
			else 
			{
				b[a[i]]+=b[i];
				b[i/a[i]]+=b[i];
			}
		printf("%lld\n",ans);
	}
	else puts("0");
	return 0;
}