Editorial for VOI 06 Bài 6 - Đường đi trên lưới
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.
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=''; z=1000000000; maxn=101; var n,m,re:longint; a,f:array[1..maxn,1..maxn] of longint; procedure rf; var i,j:longint; begin readln(m,n); for i:=1 to m do for j:=1 to n do read(a[i,j]); end; function gcd(x,y:longint):boolean; begin gcd:=true; if x*y=0 then begin gcd:=(x+y)<>1; exit; end; if (x and 1) or (y and 1)=0 then exit; if x>y then gcd:=gcd(x mod y,y) else gcd:=gcd(x,y mod x); end; procedure pr; var i,j,u,v:longint; begin for i:=1 to m do f[i,1]:=1; for j:=1 to n do for i:=1 to m do begin for v:=1 to j-1 do for u:=1 to i do if gcd(a[i,j],a[u,v]) then begin f[i,j]:=f[i,j]+f[u,v]; if f[i,j]>=z then f[i,j]:=f[i,j]-z; end; if j<n then for u:=1 to i-1 do if gcd(a[i,j],a[u,j]) then begin f[i,j]:=f[i,j]+f[u,j]; if f[i,j]>=z then f[i,j]:=f[i,j]-z; end; end; end; procedure wf; var i:longint; begin re:=0; for i:=1 to m do begin re:=re+f[i,n]; if re>=z then re:=re-z; end; writeln(re); end; begin assign(input,fi); reset(input); assign(output,fo); rewrite(output); rf; pr; wf; close(input); close(output); end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N 105 #define MOD 1000000000 int f[N][N], a[N][N], m, n; int gcd(int a, int b) { int t; while(b) { t = b; b = a % t; a = t; } return a; } int main() { //freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); scanf("%d%d",&m,&n); rep(i,m) rep(j,n) scanf("%d",&a[i][j]); rep(i,m) f[i][0] = 1; rep(i,m) rep(j,n) rep(x,i+1) rep(y,j+1) if( y < n-1 && x+y < i+j && gcd(a[x][y], a[i][j]) != 1) f[i][j] = (f[i][j] + f[x][y]) % MOD; int res = 0; rep(i,m) res = (res + f[i][n-1])%MOD; printf("%d\n", res); return 0; }
Code mẫu của ladpro98
program nkpath; uses math; const fi=''; maxN=111; base=trunc(1e9); var a:array[1..maxN,1..maxN] of longint; f:array[1..maxN,1..maxN] of longint; m,n,res:longint; procedure input; var inp:text; i,j:longint; begin assign(inp,fi); reset(inp); readln(inp,m,n); for i:=1 to m do for j:=1 to n do read(inp,a[i,j]); close(inp); end; function gcd(a,b:longint):longint; var r: longint; begin repeat r := a mod b; a := b; b := r; until b = 0; exit(a); end; procedure dp; var i,j,x,y:longint; begin for i:=1 to m do f[i,n]:=1; for j:=n-1 downto 1 do for i:=m downto 1 do begin for y:=j to n do for x:=i to m do if gcd(a[i,j],a[x,y])>1 then begin f[i,j]:=(f[i,j]+f[x,y]); if f[i,j]>=base then dec(f[i,j],base); end; end; end; procedure output; var i:longint; begin for i:=1 to m do begin res:=(res+f[i,1]); if res>=base then dec(res,base); end; write(res); end; begin input; dp; output; end.
Code mẫu của RR
const base=1000000000; var res,p,q,i,j,m,n:longint; f,a:array[1..111,1..111] of longint; function gcd(a,b:longint):longint; begin if (a=0) or (b=0) then exit(a+b) else exit(gcd(b,a mod b)); end; begin read(m,n); for i:=1 to m do for j:=1 to n do read(a[i,j]); for i:=1 to m do f[i,1]:=1; for p:=1 to m do for q:=1 to n do for i:=1 to p do for j:=1 to q do if j<n then if (i+j<p+q) and (gcd(a[i,j],a[p,q])>1) then begin inc(f[p,q],f[i,j]); if f[p,q]>base then dec(f[p,q],base); end; res:=0; for i:=1 to m do begin res:=res+f[i,n]; if res>base then dec(res,base); end; writeln(res); end.
Code mẫu của hieult
#include <cstdio> //#include <conio.h> #include <iostream> #define du 1000000000 long long f[110][110]; int n,m,a[110][110]; int GCD(int a,int b) { int r; if(b==0 || a==0) return 0; while(b!=0) { r = a%b; a = b; b = r; } return a; } int main() { // freopen("NKPATH.in","r",stdin); scanf("%d %d",&m,&n); for(int i = 1;i<=m;i++) for(int j = 1;j<=n;j++) scanf("%d",&a[i][j]); // printf("%d %d\n",a[1][1],a[1][2]); memset(f,0,sizeof(f)); f[m][n] = 1; for(int i = 1;i<=m;i++) f[i][n] = 1; for(int i = n-1;i>=1;i--) for(int j = m;j>=1;j--) { for(int u=n;u>=i;u--) for(int v = m;v>=j;v--) { if(u==i && j==v) break; if(GCD(a[j][i],a[v][u])>1) { f[j][i] = (f[j][i]+f[v][u])%du; // printf("%d %d\n",f[j][i],f[v][u]); } // printf("%d\n",GCD(a[j][i],a[v][u])); } //printf("%d\n",f[j][i]); } long long KQ = 0; for(int i = 1;i<=m;i++) KQ = (KQ+f[i][1])%du; printf("%lld",KQ); // getch(); }
Code mẫu của khuc_tuan
#include <iostream> #include <cstdio> using namespace std; int m, n, a[110][110], f[110][110], res; int main() { scanf("%d%d", &m, &n); for(int i=0;i<m;++i) for(int j=0;j<n;++j) scanf("%d", &a[i][j]); for(int i=0;i<m;++i) for(int j=0;j<n;++j) { for(int u=0;u<=i;++u) for(int v=0;v<=j;++v) if(u+v<i+j && v<n-1) { int x = a[i][j], y = a[u][v]; while(x!=0 && y!=0) { if(x>y) x%=y; else y%=x; } if(x+y>1) f[i][j] = (f[i][j] + f[u][v]) % 1000000000; } if(j==0) f[i][j] = (1+f[i][j]) % 1000000000; if(j==n-1) res = (res+f[i][j]) % 1000000000; } cout << res << endl; //system("pause"); return 0; }
Comments