CWAY - Đếm số đường đi trên đồ thị đầy đủ
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef vector<int> vi;
struct bignum
{
vi d;
bignum()
{
d.clear();
}
bignum(int x)
{
bignum();
if (x==0) d.push_back(0);
while (x>0)
{
d.push_back(x%10);
x=x/10;
}
}
bignum(const bignum &x)
{
d=x.d;
}
bignum operator + (const bignum &x)
{
bignum res=bignum();
int n=max(d.size(),x.d.size());
int i,s,c,a,b;
s=0;
c=0;
for (i=1;i<=n;i=i+1)
{
if (i>d.size()) a=0; else a=d[i-1];
if (i>x.d.size()) b=0; else b=x.d[i-1];
s=a+b+c;
if (s>9) c=1; else c=0;
res.d.push_back(s%10);
}
if (c>0) res.d.push_back(1);
while (res.d[res.d.size()-1]==0) res.d.pop_back();
return (res);
}
bignum operator * (int x)
{
if (x==0) return (bignum(0));
if ((d.size()==1) && (d[0]==0)) return (bignum(0));
bignum res=bignum();
int i,s,c;
s=0;
c=0;
for (i=1;i<=d.size();i=i+1)
{
s=d[i-1]*x+c;
c=s/10;
res.d.push_back(s%10);
}
while (c>0)
{
res.d.push_back(c%10);
c=c/10;
}
while (res.d[res.d.size()-1]==0) res.d.pop_back();
return (res);
}
void print(void)
{
int i;
for (i=d.size();i>=1;i=i-1) printf("%d",d[i-1]);
}
};
int i,n;
bignum s[2000];
int main(void)
{
scanf("%d",&n);
s[2]=bignum(1);
for (i=3;i<=n;i=i+1)
s[i]=s[i-1]*(i-2)+bignum(1);
s[n].print();
}