# T1.dnf

$$C_{n+m-1}^{n-1}$$

$$C_{n+m-1-(Li+1)}^{n-1}$$

$$ans=\sum{\pm C_{n+m-1-\sum{(Li+1)}}^{n-1} }$$

#include <iostream>
#include <cstring>
#include <cstdio>

#define MD 1000000007
#define MX 200050

using namespace std;
typedef long long ll;

ll frac[MX+1];
ll n,m,k,ans;
ll use[20];

void init()
{
frac[0]=1;
for(ll i=1;i<=MX;i++)frac[i]=frac[i-1]*i%MD;
}

inline ll ksm(ll x,ll t)
{
ll as=1;
while(t)
{
if(t&1)as=as*x%MD;
x=x*x%MD;
t>>=1;
}
return as;
}

inline ll inv(ll x){return ksm(x,MD-2);}
inline ll C(ll n,ll m){return frac[n]*inv(frac[m])%MD*inv(frac[n-m])%MD;}

void input()
{
scanf("%lld%lld%lld",&n,&k,&m);
for(ll i=1;i<=k;i++)scanf("%lld",&use[i]);
}

void sch(int pos,ll sgmt,ll num)
{
if(sgmt>m)return;
if(pos==k+1)
{
if(num%2==0)ans=(ans+C(n+m-1-sgmt,n-1))%MD;
else ans=(ans-C(n+m-1-sgmt,n-1)+MD)%MD;
return;
}
sch(pos+1,sgmt+use[pos]+1,num+1);
sch(pos+1,sgmt,num);
}

int main()
{
freopen("dnf.in","r",stdin);
freopen("dnf.out","w",stdout);
init();
input();
sch(1,0,0);
cout<<ans<<endl;
return 0;
}


# T2.euclid

### 有关卡常技巧：

1. 压位：

#define SIZ 1000000000000000000


2. 高精度模板：

typedef struct bigintger{ll x[669];}BI;
inline BI pls(BI *a,BI *b)//貌似传入指针，返回结构体是最快的
{
BI c;
int lens=max(a->x[0],b->x[0]);
c.x[lens+1]=0,c.x[1]=0;//这一行结合下一行可以避免 memset
for(register int i=1;i<=lens;i++)c.x[i]=(c.x[i]+a->x[i]+b->x[i])%SIZ,c.x[i+1]=(a->x[i]+b->x[i])/SIZ;//将进位和计算本位的循环合二为一
if(c.x[lens+1])++lens;
c.x[0]=lens;
return c;
}


3. 避免冗余操作：

void work()
{
BI a,b,c;
BI *ap,*bp,*cp,*tmp;
ap=&a,bp=&b,cp=&c;
a.len=b.len=1;
a.x[1]=0,b.x[1]=1;
while(1)
{
*cp=pls(ap,bp);
if(big(cp,&n))
{
out(*ap);
puts("");
out(*bp);
puts("");
break;
}
tmp=ap;
ap=bp,bp=cp,cp=tmp;
}
}


4. 奸诈的技巧：

#pragma GCC optimize(2)


#include <iostream>
#include <cstring>
#include <cstdio>

#pragma GCC optimize(2)
#define len x[0]

#define SIZ 1000000000000000000
#define MX  14099

using namespace std;

typedef unsigned long long ll;

ll ten[19]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000};

typedef struct bigintger{ll x[669];}BI;

BI n;

inline BI pls(BI *a,BI *b)
{
BI c;
int lens=max(a->len,b->len);
c.x[lens+1]=0,c.x[1]=0;
for(register int i=1;i<=lens;i++)c.x[i]=(c.x[i]+a->x[i]+b->x[i])%SIZ,c.x[i+1]=(a->x[i]+b->x[i])/SIZ;
if(c.x[lens+1])++lens;
c.len=lens;
return c;
}

inline bool big(BI *a,BI *b)
{
if(a->len!=b->len)return a->len>b->len;
for(register int i=a->len;i>=1;--i)
if(a->x[i]!=b->x[i])
return a->x[i]>b->x[i];
return 0;
}

void out(BI a)
{
printf("%lld",a.x[a.len]);
for(register int i=a.len-1;i>=1;i--)printf("%018lld",a.x[i]);
}

void in(BI *a)
{
memset(a->x,0,sizeof(a->x));
a->len=0;
char ch[MX];
scanf("%s",ch);
int lens=strlen(ch);
for(register int i=0;i+i<lens;i++)swap(ch[i],ch[lens-i-1]);
for(register int i=0;i<lens;i++)a->x[i/18+1]=a->x[i/18+1]+(ch[i]-'0')*ten[i%18];
a->len=(lens-1)/18+1;
}

void work()
{
BI a,b,c;
BI *ap,*bp,*cp,*tmp;
ap=&a,bp=&b,cp=&c;
a.len=b.len=1;
a.x[1]=0,b.x[1]=1;
while(1)
{
*cp=pls(ap,bp);
if(big(cp,&n))
{
out(*ap);
puts("");
out(*bp);
puts("");
break;
}
tmp=ap;
ap=bp,bp=cp,cp=tmp;
}
}

int main()
{
freopen("euclid.in","r",stdin);
freopen("euclid.out","w",stdout);
in(&n);
work();
return 0;
}



# T3.divisor

or#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int numbers[2000]=
{
1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,
7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,
166320,221760,277200,332640,498960,554400,665280,720720,1081080,
1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,
10810800,14414400,17297280,
21621600,
32432400,36756720,
43243200,
61261200,
73513440,
110270160,
122522400,
147026880,
183783600,
245044800,
294053760,
367567200,
551350800,
698377680,
735134400,
1000000001
};

int main()
{
freopen("divisor.in","r",stdin);
freopen("divisor.out","w",stdout);
int n;
cin>>n;
if(n==0)cout<<0<<endl;
else for(int i=0;i<=1500;i++)if(n>=numbers[i]&&n<numbers[i+1]){cout<<numbers[i]<<endl;return 0;}
}