Editorial for VM 08 Bài 03 - Đếm đường đi trên đồ thị đầy đủ


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      base=1000000;
      digit=6;
type bignum=array[0..1000] of longint;
var n:longint;
    re:bignum;

procedure rf;
begin
     assign(input,fi);
     reset(input);
     read(n);
     close(input);
end;

procedure plus(var a:bignum);
var i:longint;
begin
     for i:=1 to a[0] do
     begin
          inc(a[i]);
          if a[i]=base then a[i]:=0
          else break;
     end;
     if a[a[0]]=0 then
     begin
          inc(a[0]);
          a[a[0]]:=1;
     end;
end;

procedure multi(var a:bignum;b:longint);
var i,mem,t:longint;
begin
     mem:=0;
     for i:=1 to a[0] do
     begin
          t:=a[i]*b+mem;
          mem:=t div base;
          a[i]:=t mod base;
     end;
     if mem>0 then
     begin
          inc(a[0]);
          a[a[0]]:=mem;
     end;
end;

procedure pr;
var i:longint;
begin
     fillchar(re,sizeof(re),0);
     re[0]:=1; re[1]:=1;
     if n=2 then re[1]:=0;
     for i:=2 to n-2 do
     begin
          plus(re);
          multi(re,i);
     end;
     plus(re);
end;

procedure wf;
var i,j,t:longint; s:string;
begin
     assign(output,fo);
     rewrite(output);
     for i:=re[0] downto 1 do
     begin
          if i<re[0] then
          begin
               str(re[i],s);
               t:=length(s);
               for j:=t+1 to digit do write(0);
          end;
          write(re[i]);
     end;
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    public static void main(String argv[]) {
        int n = new Scanner(System.in).nextInt();
        BigInteger res = new BigInteger("1");
        BigInteger mul = BigInteger.ONE;
        for(int i = 3; i <= n; ++i) {
            res = res.multiply(mul).add(BigInteger.ONE);
            mul = mul.add(BigInteger.ONE);
        }
        System.out.println(res);
    }
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int MOD = 100000;

using namespace std;
typedef vector<int> BigInt;

int n;

BigInt operator + (BigInt a, BigInt b) {
    BigInt c; int carry = 0;
    for(int i = 0; i < a.size() || i < b.size(); i++) {
        if (i < a.size()) carry += a[i];
        if (i < b.size()) carry += b[i];
        c.push_back(carry % MOD);
        carry /= MOD;
    }
    if (carry) c.push_back(carry);
    return c;
}

BigInt operator * (BigInt a, int b) {
    BigInt c; int carry = 0;
    for(int i = 0; i < a.size(); i++) {
        carry += a[i] * b;
        c.push_back(carry % MOD);
        carry /= MOD;
    }
    if (carry) c.push_back(carry);
    return c;
}

void print(BigInt a) {
    printf("%d", a[a.size() - 1]);
    for(int i = a.size() - 2; i >= 0; i--)
        printf("%05d", a[i]);
    printf("\n");
}

int main() {
    scanf("%d", &n);
    BigInt res; res.push_back(1);
    BigInt tmp = res;
    for(int i = n - 2; i; i--) {
        tmp = tmp * i;
        res = res + tmp;
    }
    print(res);
    return 0;
}

Code mẫu của RR

const
  base=1000;

type
  big=array[0..1000] of longint;

var
  f:array[2..1000] of big;
  i,n:longint;

procedure nhan(a:big; k:longint; var b:big);
    var
      i,nho:longint;
    begin
      nho:=0; b[0]:=a[0];
      for i:=1 to a[0] do
        begin
          b[i]:=a[i]*k+nho;
          nho:=b[i] div base;
          b[i]:=b[i] mod base;
        end;

      while nho>0 do
        begin
          inc(b[0]);
          b[b[0]]:=nho mod base;
          nho:=nho div base;
        end;
    end;

procedure cong1(var a:big);
    var
      i,nho:longint;
    begin
      nho:=1;
      for i:=1 to a[0] do
        begin
          a[i]:=a[i]+nho;
          if a[i]<base then nho:=0
          else begin nho:=1; dec(a[i],base); end;
        end;
      if nho>0 then
        begin
          inc(a[0]);
          a[a[0]]:=nho;
        end;
    end;

procedure print(var a:big);
    var
      i:longint;
    begin
      write(a[a[0]]);
      for i:=a[0]-1 downto 1 do
        if a[i]>=100 then write(a[i])
        else if a[i]>=10 then write('0',a[i])
        else write('00',a[i]);
    end;

begin
  f[2][0]:=1; f[2][1]:=1;
  for i:=3 to 1000 do
    begin
      nhan(f[i-1],i-2,f[i]);
      cong1(f[i]);
    end;

  read(n);
  print(f[n]);
end.

Code mẫu của hieult

#include <cstdio>
//#include <conio.h>
#define base 10000

int a[1000];
int scs;

void print()
{
     printf("%d",a[scs]);
     for(int i = scs-1;i>=1;i--) printf("%04d",a[i]);
}

int main()
{
    int n;
    scanf("%d",&n);
    a[1] = 1;scs = 1;
    for(int i = 1;i<=n-2;i++)
    {
        int du = 0,temp;
        temp = a[1];
        a[1] = (temp*i+1)%base;
        du = (temp*i+1)/base;
        for(int j = 2;j<=scs;j++)
        {
            temp = a[j];
            a[j] = (temp*i+du)%base;
            du = (temp*i+du)/base;
        }
        if(du>0) a[++scs] = du;
    } 
    print();
    //getch();           
}

Code mẫu của ll931110

program CWAY;
const
  maxn = 1000;
  maxd = 550;
  base = 100000;
type
  arr = array[1..maxd] of longint;
var
  F: array[0..maxn] of arr;
  n: longint;

function adjust(d: arr; x: longint): arr;
var
  tmp: arr;
  i: longint;
begin
  for i := 1 to maxd do tmp[i] := d[i] * x;
  inc(tmp[1]);

  for i := 1 to maxd - 1 do if tmp[i] >= base then
    begin
      tmp[i + 1] := tmp[i + 1] + tmp[i] div base;
      tmp[i] := tmp[i] mod base;
    end;

  adjust := tmp;
end;

procedure precom;
var
  i: longint;
begin
  fillchar(F, sizeof(F), 0);
  F[0,1] := 1;
  for i := 1 to maxn - 2 do F[i] := adjust(F[i - 1],i);
end;

procedure printresult;
var
  i,j,k: longint;
  s: string;
begin
  readln(n);
  n := n - 2;

  i := maxd;
  while F[n,i] = 0 do dec(i);

  write(F[n,i]);
  for j := i - 1 downto 1 do
    begin
      str(F[n,j],s);
      for k := 1 to 5 - length(s) do write(0);
      write(s);
    end;
end;

begin
  precom;
  printresult;
end.

Code mẫu của skyvn97

#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();
}

Code mẫu của khuc_tuan

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        BigInteger cur = BigInteger.ONE;
        for (int i = 3; i <= n; ++i)
            cur = cur.multiply(BigInteger.valueOf(i - 2)).add(BigInteger.ONE);
        System.out.println(cur);
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.