Editorial for Đếm chuỗi đối xứng
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=''; maxn=121; base=100000000; digit=8; type bignum=array[0..10] of longint; var n:longint; s:string; f:array[1..maxn,1..maxn] of bignum; procedure rf; var i:longint; begin assign(input,fi); reset(input); read(s); n:=length(s); fillchar(f,sizeof(f),0); close(input); end; procedure plus(var a:bignum;b,c:bignum); var i,mem,max:longint; begin if b[0]>c[0] then max:=b[0] else max:=c[0]; mem:=0; for i:=1 to max do begin a[i]:=(b[i]+c[i]+mem) mod base; mem:=(c[i]+b[i]+mem) div base; end; if mem>0 then begin inc(max); a[max]:=mem; end; a[0]:=max; end; procedure minus(var a:bignum;b:bignum); var i,mem,max:longint; begin max:=a[0]; mem:=0; for i:=1 to max do if a[i]-b[i]-mem<0 then begin a[i]:=a[i]+base-b[i]-mem; mem:=1; end else begin a[i]:=a[i]-b[i]-mem; mem:=0; end; i:=max; while (i>1) and (a[i]=0) do dec(i); a[0]:=i; end; procedure calc(l,r:longint); var t:bignum; begin if l=r then begin f[l,l,0]:=1; f[l,l,1]:=1; exit; end; if f[l,r-1,0]=0 then calc(l,r-1); if f[l+1,r,0]=0 then calc(l+1,r); plus(f[l,r],f[l,r-1],f[l+1,r]); if s[l]=s[r] then begin fillchar(t,sizeof(t),0); t[0]:=1; t[1]:=1; plus(f[l,r],f[l,r],t); end else begin if (l+1<=r-1) and (f[l+1,r-1,0]=0) then calc(l+1,r-1); minus(f[l,r],f[l+1,r-1]); end; end; procedure pr; var i,j:longint; begin calc(1,n); end; procedure wf; var i,j,t:longint; s:string; re:bignum; begin assign(output,fo); rewrite(output); re:=f[1,n]; 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
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int BASE = 1000000000, MAX_DIGIT = 5, LOG_BASE = 9, N = 120; struct BigInteger { int d[MAX_DIGIT], n; void operator = (const int &x) { memset(d, 0, sizeof d); n = 0; for(int t = x; t != 0; t /= BASE) d[n++] = t % BASE; } void operator += (const BigInteger &a) { int rem = 0; n = max(n, a.n); for(int i = 0; i < n; ++i) { int p = d[i] + a.d[i] + rem; if(p >= BASE) d[i] = p - BASE, rem = 1; else d[i] = p, rem = 0; } if(rem) d[n++] = rem; } void operator -= (const BigInteger &a) { int rem = 0; for(int i = 0; i < n; ++i) { int p = d[i] - a.d[i] - rem; if(p < 0) d[i] = p + BASE, rem = 1; else d[i] = p, rem = 0; } while(n > 0 && d[n-1] == 0) --n; } void print() { printf("%d", d[n-1]); for(int i = n-2; i >= 0; --i) printf("%0*d", LOG_BASE, d[i]); printf("\n"); } } f[N][N], ONE; char s[N+1]; int main() { ONE = 1; scanf("%s", s); int n = strlen(s); for(int i = 0; i < n; ++i) f[i][i] = ONE; for(int l = 2; l <= n; ++l) for(int i = 0, j = l - 1; j < n; ++i, ++j) { f[i][j] = f[i+1][j]; f[i][j] += f[i][j-1]; if(s[i] == s[j]) f[i][j] += ONE; else f[i][j] -= f[i+1][j-1]; } f[0][n-1].print(); return 0; }
Code mẫu của ladpro98
program qbpal; uses math; type big=string; const fi=''; var s:string; f:array[1..123,1..123] of big; check:array[1..123,1..123] of boolean; n:longint; procedure input; var inp:text; begin assign(inp,fi); reset(inp); readln(inp,s); close(inp); n:=length(s); end; function plus(a,b:big):big; var c:big; i,carry,s:longint; begin carry:=0;c:=''; while length(a)<length(b) do a:='0'+a; while length(b)<length(a) do b:='0'+b; for i:=length(a) downto 1 do begin s:=ord(a[i])+ord(b[i])+carry-96; c:=chr(s mod 10+48) +c; carry:=s div 10; end; if carry>0 then c:='1'+c; exit(c); end; function sub(a,b:big):big; var c:big; s,br,i:longint; begin br:=0; c:=''; while length(a)<length(b) do a:='0'+a; while length(b)<length(a) do b:='0'+b; for i:=length(a) downto 1 do begin s:=ord(a[i])-ord(b[i])-br; if s<0 then begin s:=s+10; br:=1; end else br:=0; c:=chr(s+48)+c; end; while (length(c)>1) and (c[1]='0') do delete(c,1,1); exit(c); end; procedure init; var i,j:longint; begin for i:=1 to n do begin f[i,i]:='1'; check[i,i]:=true; end; for i:=1 to n-1 do begin if s[i]=s[i+1] then begin f[i,i+1]:='3'; check[i,i+1]:=true; end else begin f[i,i+1]:='2'; check[i,i+1]:=true; end; end; end; function dp(i,j:longint):big; var k:longint; begin if check[i,j] then exit(f[i,j]); check[i,j]:=true; if s[i]=s[j] then f[i,j]:=plus(plus(dp(i+1,j),dp(i,j-1)),'1') else f[i,j]:=sub(plus(dp(i+1,j),dp(i,j-1)),dp(i+1,j-1)); exit(f[i,j]); end; begin input; init; write(dp(1,n)); end.
Code mẫu của RR
{$R+,Q+} uses math; const MAXN=200; oo=10; type bigNum=array[0..MAXN] of longint; var s:string; n:longint; d:array[0..MAXN,0..MAXN] of bigNum; operator +(a,b:bigNum) c:bigNum; var nho,i:longint; begin nho:=0; fillchar(c,sizeof(c),0); c[0]:=max(a[0],b[0]); for i:=MAXN downto MAXN-c[0]+1 do begin c[i]:=a[i]+b[i]+nho; nho:=c[i] div oo; c[i]:=c[i] mod oo; end; if nho>0 then begin inc(c[0]); c[MAXN-c[0]+1]:=nho; end; end; operator -(a,b:bigNum) c:bigNum; var nho,i:longint; begin nho:=0; fillchar(c,sizeof(c),0); c[0]:=a[0]; for i:=MAXN downto MAXN-c[0]+1 do begin c[i]:=a[i]-b[i]-nho; if c[i]<0 then begin nho:=1; c[i]:=c[i]+oo; end else nho:=0; end; while (c[0]>0) and (c[MAXN-c[0]+1]=0) do dec(c[0]); end; procedure solve; var i,j,k:longint; a:bigNum; begin fillchar(a,sizeof(a),0); a[0]:=1; a[200]:=1; for i:=1 to n do d[i,i]:=a; for k:=1 to n do for i:=1 to n-k do begin j:=i+k; if s[i]=s[j] then d[i,j]:=d[i,j-1]+d[i+1,j]+a else d[i,j]:=d[i,j-1]+d[i+1,j]-d[i+1,j-1]; end; end; procedure print(a:bigNum); var i:longint; s:string; begin if a[0]=0 then begin writeln(0); exit; end; write(a[MAXN-a[0]+1]); for i:=MAXN-a[0]+2 to MAXN do write(a[i]); writeln; end; begin readln(s); n:=length(s); solve; print(d[1,n]); end.
Code mẫu của hieult
#include <cstdio> #include <cstring> //#include <conio.h> #define base 100000000 struct solon { int so; int a[40]; }; solon f[122][122],T; char s[122]; int n; solon tong (solon A,solon B) { int du = 0; solon C; if(A.so<B.so) { C = A; A = B; B = C; } for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0; C.so = A.so; for(int i = 1;i<=A.so;i++) { C.a[i] = (A.a[i]+B.a[i]+du)%base; du = (A.a[i]+B.a[i]+du)/base; } if(du>0) {C.so++; C.a[C.so] = du;} return C; } solon hieu(solon A,solon B) { int du = 0; solon C; for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0; C.so = A.so; for(int i = 1;i<=A.so;i++) { C.a[i] = (A.a[i]-B.a[i]-du); if(C.a[i]<0) { C.a[i] += base; du = 1; } } while(C.a[C.so]==0 && C.so>1) C.so--; return C; } void print(solon A) { printf("%d",A.a[A.so]); for(int i = A.so-1;i>=1;i--) printf("%08d",A.a[i]); } bool doixung(int i,int j) { if(j-i<2) return (s[i]==s[j]); if(s[i]!=s[j]) return false; else return doixung(i+1,j-1); } int main() { // freopen("QBPAL.in","r",stdin); scanf("%s",s); n = strlen(s); T.so = 1; T.a[1] = 1; for(int i = 0;i<n;i++) { f[i][i] = T; f[i+1][i].so = 1; f[i+1][i].a[1] = 0; } for(int k = 1;k<n;k++) for(int i =0;i+k<n;i++) { int j = i+k; f[i][j] = tong(f[i+1][j],f[i][j-1]); if(s[i]==s[j]) f[i][j] = tong(f[i][j],T); else f[i][j] = hieu(f[i][j],f[i+1][j-1]); // printf("%d %d %d\n",i,j,f[i][j].a[1]); } //if(doixung(0,n-1)) f[0][n-1] = hieu(f[0][n-1],T); print(f[0][n-1]); // getch(); }
Code mẫu của khuc_tuan
s = raw_input() n = len(s) F = [[-1 for i in range(n)] for j in range(n)] def calc(a,b): if a>b: return 1 if a==b: return 2 if F[a][b]!=-1: return F[a][b] res = 0 res = calc(a+1,b) + calc(a,b-1) - calc(a+1,b-1) if s[a]==s[b]: res += calc(a+1,b-1) F[a][b] = res return res print calc(0,n-1) - 1
Comments