bzoj1566

好题，这道题体现了换一个角度计数的思想

a1^2+a2^2+……ak^2=(变成第1种输出序列的操作序列数目)^2+(变成第2种输出序列的操作序列数目)^2……

脑洞大一点，这就相当于两个操作序列变成相同输出序列的对数（包括自己和自己）

于是dp即可……dp[i,j,k]表示输出到第i个，第一个操作序列在上面取了j个，第二个操作序列在上面取了k个，怎么弄大家都会……

 const mo=;

 var s1,s2:array[..] of char;

     p,m,n,i,j,k,j1,k1:longint;

     f:array[..,..,..] of longint;

 procedure reverse;

   var s:ansistring;

   begin

     readln(s);

     for i:= to n do

       s1[n-i+]:=s[i];

     s1[n+]:='$';

     readln(s);

     for i:= to m do

       s2[m-i+]:=s[i];

     s2[m+]:='#';

   end;

 begin

   readln(n,m);

   reverse;

   f[,,]:=;

   for i:= to m+n do

   begin

     p:=-p;

     fillchar(f[p],sizeof(f[p]),);

     for j:= to n do

       for k:= to n do

         if f[-p,j,k]>=mo then f[-p,j,k]:=f[-p,j,k] mod mo;

     for j:= to n do

       for k:= to n do

       begin

         j1:=i--j;

         k1:=i--k;

         if (j1>=) and (k1>=) and (j1<=m) and (k1<=m) then

         begin

           if s1[j+]=s1[k+] then inc(f[p,j+,k+],f[-p,j,k]);

           if s1[j+]=s2[k1+] then inc(f[p,j+,k],f[-p,j,k]);

           if s2[j1+]=s1[k+] then inc(f[p,j,k+],f[-p,j,k]);

           if s2[j1+]=s2[k1+] then inc(f[p,j,k],f[-p,j,k]);

         end;

       end;

   end;

   writeln(f[p,n,n] mod mo);

 end.

巴特西

bzoj1566

最新文章

热门文章