Hướng dẫn giải của VM 08 Bài 03 - Đếm đường đi trên đồ thị đầy đủ


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.