nixp.ru v3.0

26 мая 2017,
пятница,
08:43:26 MSK

DevOps с компанией «Флант»
anonymous написал 28 июля 2005 года в 11:33 (316 просмотров) Ведет себя неопределенно; открыл 1814 темы в форуме, оставил 5575 комментариев на сайте.

Помогите понять что делает эта программа и на каком принципе она основана:

{$I-,S-,Q-,R-}

Program m_inverse;

var

i: LongInt;

N: LongInt;

Result: Int64;

P, Pos, S: Array[1..100000] of LongInt;

RCnt, LCnt: Array[1..100000] of Int64;

Function Prev(X: LongInt): LongInt;

begin

Prev:= X and (X-1);

end;

Function Next(X: LongInt): LongInt;

begin

Next:= X shl 1 — Prev(X);

end;

Procedure Add(pos: LongInt);

var

X: LongInt;

begin

X:= pos;

While X <= N do begin

Inc(S[X]);

X:= Next(X);

end;

end;

Function FindSimpleSum(x: LongInt): LongInt;

var

Sum: LongInt;

begin

Sum:= 0;

While x>0 do begin

Sum:= Sum + S[x];

x:= Prev(x);

end;

FindSimpleSum:= Sum;

end;

Function FindSum(l, r: LongInt): LongInt;

begin

FindSum:= FindSimpleSum(r) — FindSimpleSum(l-1);

end;

begin

Assign(Input, 'input.txt’);

ReSet(Input);

ReadLn(N);

For i:= 1 to N do begin

ReadLn(P);

Pos[P]:= i;

end;

Close(Input);

FillChar(S, SizeOf(S), 0);

For i:= 1 to N do begin

RCnt[Pos]:= FindSum(Pos+1, N);

Add(Pos);

end;

FillChar(S, SizeOf(S), 0);

For i:= N downto 1 do begin

LCnt[Pos]:= FindSum(1, Pos-1);

Add(Pos);

end;

Result:= 0;

For i:= 1 to N do

Result:= Result + LCnt * RCnt;

Assign(Output, 'output.txt’);

ReWrite(Output);

WriteLn(Result);

Close(Output);

end.

особо интересуют функции prev и next

rgo

prev — вычитает из x самый младший бит, next — наоброт, добавляет к x младший бит x.

prev (…1100) -> …1000

next (…0100) -> …1000