这道题目是求sigma(ai*(xi)^3)=0 (1=<i<=5) 的方案数。其中a1~a5是已知的。
先想最暴力的五重循环，枚举x1~x5，显然会超时，我们就想先计算出前一半，把后一半移项，如果前一半的和和后一半的数互为相反数，则方案数加一。
用一个哈希维护一下这题复杂度就能降到O(100^3)。
View Code const base=3213157;var ans:longint; a:array[-4000000..4000000] of longint; b:array[-4000000..4000000] of longint; a1,a2,a3,a4,a5:longint;function cube(x:longint):longint;begin exit(x*x*x);end;procedure hash(x:longint);var now:longint;begin now:=x mod base;while (a[now]<>0) and (b[now]<>x) do inc(now);if (b[now]=x) then begin inc(a[now]); exit; end; inc(a[now]); b[now]:=x;end;function rehash(x:longint):longint;var now:longint;begin now:=x mod base;while (a[now]<>0) and (b[now]<>x) do inc(now);if (b[now]=x) then exit(a[now]); exit(0);end;procedure doleft;var sum,x1,x2,x3:longint;beginfor x1:=-50 to 50 dofor x2:=-50 to 50 dofor x3:=-50 to 50 doif (x1<>0) and (x2<>0) and (x3<>0) then begin sum:=a1*cube(x1)+a2*cube(x2)+a3*cube(x3); hash(sum);end;end;procedure doright;var x4,x5,sum:longint;beginfor x4:=-50 to 50 dofor x5:=-50 to 50 doif (x4<>0) and (x5<>0) then begin sum:=a4*cube(x4)+a5*cube(x5); sum:=-sum; ans:=ans+rehash(sum);end;end;begin readln(a1,a2,a3,a4,a5); ans:=0; fillchar(a,sizeof(a),0); doleft; doright; writeln(ans);end.注意x不能取0，要判断。
转载于:https://www.cnblogs.com/zjerly/archive/2011/10/17/2215767.html
