内容目录
一个长度为3N字符串满足:由N个A,N个B,N个C组成,对于它的任意前缀,满足A的个数>=B的个数>=C的个数。求满足这样条件的字符串的个数。
看到这题第一反应:打表!第二反应三个字:高精度
这题动态转移方程为f[i,j,k]=f[i-1,j,k]+f[i,j-1,k]+f[i,j,k-1] i,j,k表示A,B,C的个数,考察是否可行
高精啊高精……
Program str; type arr=record len:longint; d:array[1..15] of longint; end; var n,i,j,k:longint; f:array[0..60,0..60,0..60] of arr; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure sum(a,b:arr;var c:arr); var i,j:longint; const F=100000000; begin fillchar(c,sizeof(c),0); c.len:=max(a.len,b.len); for i:=1 to c.len do begin inc(c.d[i],a.d[i]+b.d[i]); inc(c.d[i+1],c.d[i] div F); c.d[i]:=c.d[i] mod F; end; if c.d[c.len+1]>0 then inc(c.len); while (c.len>0) and (c.d[c.len]=0) do dec(c.len); end; Procedure print(a:arr); var i,p:longint; begin write(a.d[a.len]); for i:=a.len-1 downto 1 do begin p:=a.d[i]; if p<10000000 then write('0'); if p<1000000 then write('0'); if p<100000 then write('0'); if p<10000 then write('0'); if p<1000 then write('0'); if p<100 then write('0'); if p<10 then write('0'); write(p); end; writeln; end; begin read(n); fillchar(f,sizeof(f),0); f[0,0,0].len:=1; f[0,0,0].d[1]:=1; for i:=1 to n do for j:=0 to i do for k:=0 to j do begin if k>0 then begin sum(f[i,j,k],f[i,j,k-1],f[i,j,k]); end; if i>j then sum(f[i,j,k],f[i-1,j,k],f[i,j,k]); if j>k then sum(f[i,j,k],f[i,j-1,k],f[i,j,k]); end; print(f[n,n,n]); end.