mcfx's blog - 2016年9月

BZOJ1041: [HAOI2008]圆上的整点

2016-09-18T23:41:00+08:00

###Description
求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。

###Input
只有一个正整数n,n<=2000 000 000

###Output
整点个数

###Sample Input
4

###Sample Output
4

###Solution
只考虑x,y均大于0的情况
首先，暴力枚举肯定是O(n)的，T
对于勾股数有一个结论，就是如果$$x^2+y^2=n^2$$，那么$$x=t(a^2-b^2),y=2tab,n=t(a^2+b^2)$$
那么我们可以枚举t，显然，只需要枚举n的每个质因数是否在t中就可以了（t中不需要有重复质因子）
枚举t后，需要将n/t写成a^2+b^2的形式，枚举a从1到sqrt(n/t)，时间复杂度O(sqrt(n/t))
注意去掉重复的a,b，用map实现即可
总时间复杂度应该是根号乘log吧。。
<del>这显然不是正解，不过跑的还是挺快的</del>

###Code
```c++
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>

std::map<int,bool> f;
  
#define pmax 65536
int prime[10000],pm,x[10],y[10],cc,ans=0,n;
bool np[pmax+1];

inline int solve(int nn)
{
	int ans=0;
	for(int i=sqrt(nn);i>0;i--)
	{
		int a=nn-i*i,b=sqrt(nn-i*i);
		if(b*b==a)
		{
			int c=2*b*i,d=std::abs(b*b-i*i);
			if(!(c&&d))continue;
			if(!(f[c*(n/nn)]||f[d*(n/nn)]))
			{
				f[c*(n/nn)]=f[d*(n/nn)]=1;
				ans+=8;
			}
		}
	}
	return ans;
}
  
void dfs(int id,int nn)
{
    if(id==cc)
    {
        ans+=solve(n/nn);
        return;
    }
    dfs(id+1,nn);
    dfs(id+1,nn*x[id]);
}

int main()
{
    for(int i=2;i<=pmax;i++)
    {
        if(!np[i])prime[pm++]=i;
        for(int j=0;j<pm&&i*prime[j]<=pmax;j++)
        {
            np[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
    int m;
    scanf("%d",&n);
    if(n==0)
    {
    	printf("1\n");
    	return 0;
	}
    m=n;
    for(int i=0;i<pm;i++)
        if(n%prime[i]==0)
        {
            x[cc]=prime[i];
            while(n%prime[i]==0)n/=prime[i],y[cc]++;
            cc++;
        }
    if(n>1)x[cc++]=n;
    n=m;
    dfs(0,1);
    printf("%d\n",ans+4);
    return 0;
}
```

BZOJ 1798: [Ahoi2009]Seq 维护序列

2016-09-15T13:11:00+08:00

###Description
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。

###Input
第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

###Output
对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

###Sample Input
7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

###Sample Output
2
35
8

###Solution
很显然，这是一道线段树区间修改+区间查询的裸题，每个节点存两个tag，分别表示乘多少，加多少，对于加的操作直接处理，乘的操作两个tag都乘

###Code
```c++
#include<cstdio>

#define LL long long

int seg[270000],t=1,f=0,t1[270000],t2[270000]={0},p,ys[270000];
bool tag[270000];

inline int se(int x)
{
	if(tag[x])
		return ((LL)seg[x]*t1[x]+(LL)t2[x]*ys[x])%p;
	else
		return seg[x];
}

inline void pd(int x)
{
	if(tag[x])
	{
		t1[x<<1]=(LL)t1[x<<1]*t1[x]%p,t2[x<<1]=((LL)t2[x<<1]*t1[x]+t2[x])%p;
		t1[x<<1|1]=(LL)t1[x<<1|1]*t1[x]%p,t2[x<<1|1]=((LL)t2[x<<1|1]*t1[x]+t2[x])%p;
		tag[x<<1]=tag[x<<1|1]=1;
		seg[x]=se(x);
		tag[x]=0,t1[x]=1,t2[x]=0;
	}
}

inline void up(int x)
{
	if(!tag[x])seg[x]=(se(x<<1)+se(x<<1|1))%p;
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&p);
	while(t<n+2)t<<=1,f++;
	for(int i=0;i<t+t;i++)t1[i]=1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",seg+i+t);
		ys[i+t]=1;
	}
	for(int i=t-1;i>0;i--)seg[i]=(seg[i<<1]+seg[i<<1|1])%p,ys[i]=ys[i<<1]+ys[i<<1|1];
	scanf("%d",&m);
	while(m--)
	{
		int a,b,c,ff;
		scanf("%d",&ff);
		if(ff==3)
		{
			scanf("%d%d",&a,&b);
			int l=a+t-1,r=b+t+1,ll,rr;
			LL ans=0;
			for(int i=f;i>=0;i--)
			{
				ll=l>>i,rr=r>>i;
				if(i)pd(ll),pd(rr);
				if((ll^rr)>1)
				{
					if((ll&1)==0)ans+=se(ll^1);
					if((rr&1)==1)ans+=se(rr^1);
				}
			}
			printf("%d\n",(int)(ans%p));
		}
		else if(ff==2)
		{
			scanf("%d%d%d",&a,&b,&c);
			int l=a+t-1,r=b+t+1,ll,rr;
			for(int i=f;i>=0;i--)
			{
				ll=l>>i,rr=r>>i;
				if(i)pd(ll),pd(rr);
				if((ll^rr)>1)
				{
					if((ll&1)==0)t2[ll^1]=(t2[ll^1]+c)%p,tag[ll^1]=1;
					if((rr&1)==1)t2[rr^1]=(t2[rr^1]+c)%p,tag[rr^1]=1;
				}
			}
			for(;l;l>>=1,r>>=1)
				up(l>>1),up(r>>1);
		}
		else
		{
			scanf("%d%d%d",&a,&b,&c);
			c%=p;
			int l=a+t-1,r=b+t+1,ll,rr;
			for(int i=f;i>=0;i--)
			{
				ll=l>>i,rr=r>>i;
				if(i)pd(ll),pd(rr);
				if((ll^rr)>1)
				{
					if((ll&1)==0)t1[ll^1]=(LL)t1[ll^1]*c%p,t2[ll^1]=(LL)t2[ll^1]*c%p,tag[ll^1]=1;
					if((rr&1)==1)t1[rr^1]=(LL)t1[rr^1]*c%p,t2[rr^1]=(LL)t2[rr^1]*c%p,tag[rr^1]=1;
				}
			}
			for(;l;l>>=1,r>>=1)
				up(l>>1),up(r>>1);
		}
	}
	return 0;
}
```
这个也可以当成zkw线段树区间修改的模板。。

BZOJ 1407: [Noi2002]Savage

2016-09-14T19:14:00+08:00

###Description
![1407.jpg][1]

###Input
第1行为一个整数N(1<=N<=15)，即野人的数目。
第2行到第N+1每行为三个整数Ci, Pi, Li表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。
(1<=Ci,Pi<=100, 0<=Li<=10^6)

###Output
仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于10^6。

###Sample Input
3
1 3 4
2 7 3
3 2 1

###Sample Output
6

###Solution
枚举m，每次枚举两个野人，将他们的ci,pi相减，记为c,p，那么如果有一个k在他们的年龄范围内，且c+pk模m等于0，则这个m不能取，k的最小值可以用扩展欧几里得求出
预处理每两个野人的ci,pi之差，li的最小值，可以优化时间

###Code
```c++
#include<cstdio>

int n,c[15],p[15],l[15],c2[105],p2[105],l2[105],n2=0;

inline int min(int a,int b)
{
	if(a<b)return a;else return b;
}

inline int max(int a,int b)
{
	if(a>b)return a;else return b;
}

int sol,gcd;

void exgcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=sol/a;y=0;
		gcd=a;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=x*(a/b);
}

inline int safeexgcd(int a,int b,int &x,int &y)
{
	if(a<b)exgcd(b,a,y,x);else exgcd(a,b,x,y);
}

int main()
{
	int maxc=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d%d%d",c+i,p+i,l+i),maxc=max(c[i],maxc);
	for(int i=0;i<n;i++)
		for(int j=0;j<i;j++)
		{
			c2[n2]=c[i]-c[j];
			p2[n2]=p[i]-p[j];
			l2[n2]=min(l[i],l[j]);
			n2++;
		}
	for(int i=maxc;1;i++)
	{
		bool flag=true;
		int x,y;
		for(int j=0;j<n2;j++)
		{
			sol=-c2[j];
			safeexgcd(p2[j],i,x,y);
			if(p2[j]*x+i*y!=sol)continue;
			int tmp=i/gcd;
			x%=tmp;
			if(x<0)x+=tmp;
			if(x<=l2[j])
			{
				flag=false;
				break;
			}
		}
		if(flag)
		{
			printf("%d\n",i);
			return 0;
		}
	}
}
```
另外随便写的代码就第4了
![puh.png][2]

[1]: /usr/uploads/2016/09/2556788862.jpg
  [2]: /usr/uploads/2016/09/909201119.png

BZOJ 1265: [AHOI2006]斐波卡契的兔子

2016-09-13T22:36:00+08:00

###Description
卡卡开始养兔子了！妈妈给他买了一对刚出生的兔子，卡卡了解到兔子的繁殖规律是这样的：才出生的一对兔子在一个月后将第一次生出一胎a对兔子，接着在出生后的二个月又将生出b对兔子，在第三个月和以后每个月都会繁殖c对兔子。(a <= b <= c) 由斐波纳契数列我们知道兔子的繁殖速度是很快的，然而卡卡有兔子一样多的好朋友，卡卡想在m个月后有k对兔子，以便分给他们的好友，他的愿望是否能够实现呢？ 
[任务] 编写一个程序：从输入文件中读入输入信息；计算m个月后卡卡将有多少对兔子，设之为P；计算如果m个月后卡卡要拥有至少k对兔子，那么开始时妈妈至少应该为卡卡购买多少对兔子，设之为Q；将结果输出至输出文件。

###Input
输入文件的第一行有4个正整数：a, b, c和m；而第二行则仅含一个正整数k。它们的含义见上文描述。

###Output
你的程序将向输出文件输出两行，第一行是一个整数P而第二行是一个整数Q。

###Sample Input
0 1 1 10
10000

###Sample Output
89
113

###HINT
0 <= a <= b <= c <= 100, 1 <= m <= 3 000, 1 <= k <= 10^6000

###Solution
我们用x,y,z表示一个月、两个月、三个月及以上的兔子，那么每次x=ax+by+cz,y=x,z=y+z就可以求出p，而q就是k/p向上取整
k/p可以用p,2p,4p,...,(2^t)p去求
然而为什么AC的人这么少呢。。

###Code
```c++
#include<bits/stdc++.h>
  
#define gm 1000
#define cas 10000000
#define max2 20050
  
int a[gm],b[gm],c[gm],k[gm],m,al,bl,cl,kl,t[gm],aa,bb,cc,r1[gm],r2[gm],r3[gm],l1,l2,l3;
int f[max2][gm],fl[max2],tf[max2][gm],tfl[max2],ans[gm],ansl,rrt[gm];
char tmp[10000];
  
inline void print(int *x,int xl)
{
    printf("%d",x[xl-1]);
    for(int i=xl-2;i>=0;i--)printf("%07d",x[i]);
}
  
inline int max(int a,int b)
{
    if(a>b)return a;else return b;
}
  
inline void add(int *x,int *y,int &xl,int yl)
{
    int ll=max(xl,yl);
    for(int i=0;i<ll;i++)
    {
        x[i]+=y[i];
        if(x[i]>=cas)x[i]-=cas,x[i+1]++;
    }
    if(x[ll])xl=ll+1;else xl=ll;
}
  
inline void addto(int *x,int *y,int *z,int xl,int yl,int &zl)
{
    zl=max(xl,yl);
    z[0]=0;
    for(int i=0;i<zl;i++)
    {
        z[i]+=x[i]+y[i];
        if(z[i]>=cas)z[i]-=cas,z[i+1]=1;else z[i+1]=0;
    }
    if(z[zl])zl++;
}
 
inline void multo(int *x,int y,int *z,int xl,int &zl)
{
    z[0]=0;
    for(int i=0;i<xl;i++)
    {
        z[i]+=x[i]*y;
        z[i+1]=z[i]/cas;
        z[i]%=cas;
    }
    if(z[xl])zl=xl+1;else zl=xl;
}
  
inline bool larger(int *x,int *y,int xl,int yl)
{
    if(xl>yl)return true;
    if(xl<yl)return false;
    for(int i=max(xl,yl)-1;i>=0;i--)
    {
        if(x[i]>y[i])return true;
        if(x[i]<y[i])return false;
    }
    return false;
}
  
inline void dec(int *x,int *y,int &xl,int yl)
{
    for(int i=0;i<xl;i++)
    {
        x[i]-=y[i];
        while(x[i]<0)x[i]+=cas,x[i+1]--;
    }
    while(xl&&!x[xl-1])xl--;
}
  
int main()
{
    al=1,bl=0,cl=0;
    a[0]=1;
    scanf("%d%d%d%d",&aa,&bb,&cc,&m);
    scanf("%s",tmp);
    int tml=strlen(tmp),tmp2=1;
    std::reverse(tmp,tmp+tml);
    kl=(tml+6)/7;
    for(int i=0;i<tml;i++)
    {
        if(i%7==0)tmp2=1;
        k[i/7]=k[i/7]+(tmp[i]-'0')*tmp2;
        tmp2*=10;
    }
    for(int i=0;i<m;i++)
    {
        multo(a,aa,r1,al,l1);
        multo(b,bb,r2,bl,l2);
        multo(c,cc,r3,cl,l3);
        add(c,b,cl,bl);
        memcpy(b,a,al*4);
        bl=al;
        addto(r1,r2,a,l1,l2,al);
        add(a,r3,al,l3);
    }
    add(a,b,al,bl);
    add(a,c,al,cl);
    print(a,al);
    printf("\n");
    memcpy(f[0],a,al*4);
    fl[0]=al;
    tf[0][0]=1;
    tfl[0]=1;
    ansl=0;
    int ma;
    for(ma=0;!larger(f[ma],k,fl[ma],kl);ma++)
    {
        multo(f[ma],2,f[ma+1],fl[ma],fl[ma+1]);
        multo(tf[ma],2,tf[ma+1],tfl[ma],tfl[ma+1]);
    }
    for(int i=ma-1;i>=0;i--)
    {
        if(!larger(f[i],k,fl[i],kl))
        {
            dec(k,f[i],kl,fl[i]);
            add(ans,tf[i],ansl,tfl[i]);
        }
    }
    if(kl)
    {
        rrt[0]=1;
        add(ans,rrt,ansl,1);
    }
    print(ans,ansl);
    printf("\n");
    return 0;
}
```

BZOJ 1009: [HNOI2008]GT考试

2016-09-09T20:13:00+08:00

###Description
阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为0

###Input
第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000

###Output
阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.

###Sample Input
4 3 100
111

###Sample Output
81

###Solution
我们把不吉利的数字用s表示，用f[i][j]表示n[i]匹配到s[j]的情况数，则可以用一个转移矩阵a通过f[i-1][j]求出f[i][j]
a[i][j]表示在s中匹配了i位时，在后面添数，有多少种情况匹配到j位，也就是指s的前i位后面添数后最长的公共前后缀长度为j的情况数
kmp预处理，然后对于每个i，枚举添加的数，再仿照kmp进行处理，即可求出转移矩阵
矩阵快速幂优化就可以过了，时间复杂度$$O(logN*M^3)$$

###Code
```c++
#include<cstdio>
 
struct _matrix
{
    int s[21][21],a,b;
    _matrix()
    {
        for(int i=0;i<21;i++)
            for(int j=0;j<21;j++)
                s[i][j]=0;
    }
}temp;
 
int mod;
 
void mul(_matrix &x,_matrix y)
{
    for(int i=0;i<x.a;i++)
        for(int j=0;j<y.b;j++)
        {
            temp.s[i][j]=0;
            for(int k=0;k<x.b;k++)
                temp.s[i][j]+=x.s[i][k]*y.s[k][j];
            temp.s[i][j]%=mod;
        }
    temp.a=x.a;
    temp.b=y.b;
    x=temp;
}
 
int m[21],n,f[21];
 
int main()
{
    int mm;
    scanf("%d%d%d",&n,&mm,&mod);
    char t[20];
    scanf("%s",t);
    for(int i=0;i<mm;i++)m[i+1]=t[i]-48;
    f[1]=0;
    for(int i=2;i<=mm;i++)
    {
        int t=i-1;
        while(t!=0&&m[f[t]+1]!=m[i])t=f[t];
        if(t==0)
        {
            if(m[1]==m[i])
                f[i]=1;
            else
                f[i]=0;
        }
        else
        {
            f[i]=f[t]+1;
        }
    }
    _matrix a;
    a.a=mm+1;
    a.b=mm+1;
    a.s[0][0]=9,a.s[0][1]=1;
    for(int i=1;i<mm;i++)
    {
        for(int j=0;j<10;j++)
        {
            if(m[i+1]==j)
            {
                a.s[i][i+1]++;
                continue;
            }
            int t=i;
            while(t!=0&&m[f[t]+1]!=j)t=f[t];
            if(t==0)
            {
                if(m[1]==j)
                    a.s[i][t+1]++;
                else
                    a.s[i][0]++;
            }
            else
                a.s[i][f[t]+1]++;
        }
    }
    _matrix b;
    b.a=1;
    b.b=mm+1;
    b.s[0][0]=9;
    b.s[0][1]=1;
    int ans=0,to=n-1,no=1;
    while(no<to)
    {
        if(to&no)mul(b,a);
        mul(a,a);
        no<<=1;
    }
    for(int i=0;i<mm;i++)ans+=b.s[0][i];
    printf("%d\n",ans%mod);
    return 0;
}
```

BZOJ 1089: [SCOI2003]严格n元树

2016-09-08T22:30:00+08:00

###Description
如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d
（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为2的严格2元树有三个，如下图：
![1.jpg][1]
给出n, d，编程数出深度为d的n元树数目。

###Input
仅包含两个整数n, d(0 < n <= 32, 0 <= d <= 16)

###Output
仅包含一个数，即深度为d的n元树的数目。

###Sample Input
【样例输入1】
2 2

【样例输入2】
2 3

【样例输入3】
3 5

###Sample Output
【样例输出1】
3

【样例输出2】
21

【样例输出2】
58871587162270592645034001

###Solution
我们用f(d)表示深度不大于d的n元树数目，则答案为f(d)-f(d-1)
当深度为d时，可以看做一棵深度为1的n元树，每个叶子节点向下都有d(n-1)种可能，再加上深度为0的情况，可得出f(d)=f(d-1)^n+1

###Code
```c++
#include<cstdio>
#include<memory.h>
#include<cstring>

#define maxnum 100
#define cas 1000000000

int a[maxnum],b[maxnum],t[maxnum],al=1,bl;

inline void mul()
{
	memset(t,0,(al+bl+1)*4);
	for(int i=0;i<al;i++)
		for(int j=0;j<bl;j++)
		{
			long long f=(long long)a[i]*b[j];
			t[i+j]+=f%cas;
			if(t[i+j]>=cas)t[i+j]-=cas,t[i+j+1]++;
			t[i+j+1]+=f/cas;
			if(t[i+j+1]>=cas)t[i+j+1]-=cas,t[i+j+2]++;
		}
	if(t[al+bl-1])al=al+bl;else al=al+bl-1;
	memcpy(a,t,al*4);
}

inline void print(int *a)
{
	printf("%d",a[al-1]);for(int i=al-2;i>=0;i--)printf("%09d",a[i]);printf("\n");
}

int main()
{
	int n,d;
	scanf("%d%d",&n,&d);
	a[0]=1;
	while(d--)
	{
		memcpy(b,a,al*4);
		bl=al;
		for(int i=1;i<n;i++)mul();
		a[0]++;
		for(int i=0;a[i]>=cas;i++)a[i]-=cas,a[i+1]++;
		if(a[al])al++;
	}
	for(int i=0;i<bl;i++)a[i]-=b[i];
	for(int i=0;i<al;i++)if(a[i]<0)a[i]+=cas,a[i+1]--;
	if(!a[al-1])al--;
	print(a);
	printf("\n");
	return 0;
}
```

[1]: /usr/uploads/2016/09/1813884886.jpg

BZOJ 1002: [FJOI2007]轮状病毒

2016-09-07T23:02:00+08:00

###Description
轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示
![bzoj1002.p1.png][1]
N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不同的3轮状病毒，如下图所示
![bzoj1002.p2.png][2]
现给定n(N<=100)，编程计算有多少个不同的n轮状病毒

###Input
第一行有1个正整数n

###Output
计算出的不同的n轮状病毒数输出

###Sample Input
3

###Sample Output
16

###Solution
这道题的正解是基尔霍夫矩阵，推出f[i]=f[i-1]*3-f[i-2]+2，然而我这等蒟蒻肯定是不知道怎么证的
下面是我的做法：
首先去掉外面的某条边，图就变成了类似于这样的结构：
![bzoj1002-1.png][3]
可行解就类似于下图：
![bzoj1002-2.png][4]
我们将未与中心节点相连的点标0，相连的标1，删去的边也标1，每个解就变成了一个01串
假设某个解最外面一共去掉k条边，那么这个01串长度为n+k-1，共有2k-1个1，而由于向上的边与删去的边交替出现，每个解一定与每个01串一一对应，所以最外层去掉k条边时，解的个数为 $$C(n+k-1,k\cdot 2-1)$$。
由于固定了某条边必须去掉，这里只求出了总情况数了k/n，所以还需要乘上n/k，最后的结果就是这样的：
$$\sum_k^n C(n+k-1,k\cdot 2-1)\cdot\frac{n}{k}$$
考虑到高精度大约要O(n)，时间复杂度O(n^3)
记录上一个 $$C(n+k-1,k\cdot 2-1)$$，可以优化到O(n^2)

<del>然而这种数据范围为什么不打表。。</del>

###Code
```c++
#include<cstdio>
 
#define cas 10000000
#define maxnum 100
 
int x[maxnum],y[maxnum],tmp[maxnum+1];
 
inline void mul(int a)
{
    tmp[0]=0;
    for(int i=0;i<maxnum;i++)
    {
        y[i]*=a;
        y[i]+=tmp[i];
        tmp[i+1]=y[i]/cas;
        y[i]%=cas;
    }
}
 
inline void div(int a)
{
    for(int i=maxnum-1;i>=0;i--)
    {
        if(i)y[i-1]+=y[i]%a*cas;
        y[i]/=a;
    }
}
 
inline void c(int a,int b)
{
    if(b>a/2)b=a-b;
    for(int i=0;i<maxnum;i++)y[i]=0;
    y[0]=1;
    for(int i=a;i>a-b;i--)mul(i);
    for(int i=2;i<=b;i++)div(i);
}
 
inline void print(int *k)
{
    bool is0=true;
    for(int i=maxnum-1;i>=0;i--)
    {
        if(is0&&k[i])
        {
            is0=false;
            printf("%d",k[i]);
        }
        else if(!is0)
        {
            printf("%07d",k[i]);
        }
    }
}
 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        c(n+i-1,2*i-1);
        mul(n);
        div(i);
        for(int i=0;i<maxnum;i++)
        {
            x[i]+=y[i];
            if(x[i]>cas)x[i]-=cas,x[i+1]++;
        }
    }
    print(x);
    return 0;
}
```

[1]: /usr/uploads/2016/09/2454961388.png
  [2]: /usr/uploads/2016/09/212298548.png
  [3]: /usr/uploads/2016/09/3955661276.png
  [4]: /usr/uploads/2016/09/3098156740.png
  [5]: /usr/uploads/2016/09/1992184554.gif
  [6]: /usr/uploads/2016/09/1288349390.gif
  [7]: /usr/uploads/2016/09/1992184554.gif