每周编程题 （26/7 - 1/8）

引用:原帖由 Susan﹏汪汪 於 2014-7-27 08:26 PM 发表
呢个系Convolution问题

引用:原帖由 fitcat07 於 2014-7-28 11:24 AM 发表
你指呢个系数学上 convolution 嘅问题？

复制内容到剪贴板代码:Input:
5
2 0 1 3 3
3
0 2
1 2
3 4
Output:
7
1
27

复制内容到剪贴板代码:a_u * a_u + a_u+1 * a_u+1 + a_u+1 * a_u + a_u+2 * a_u+2 + a_u+2 * a_u+1 + a_u+2 * a_u + ... + a_v * a_v + a_v * a_v-1 + ... + a_v * a_u

复制内容到剪贴板代码:a_u * a_u + a_u+1 * a_u + a_u+2 * a_u + ... + a_v * a_u + a_u+1 * a_u+1 + a_u+2 * a_u+1 + ... + a_u+2 * a_u+2 + ... + a_v * a_v

复制内容到剪贴板代码:a_u * a_u + a_u+1 * a_u + a_u+2 * a_u + ... + a_v * a_u +
a_u+1 * a_u+1 + a_u+2 * a_u+1 + ... +
a_u+2 * a_u+2 + ... +
a_v * a_v

复制内容到剪贴板代码:2*2 2*0 2*1
0*2 0*0 0*1
1*2 1*0 1*1

引用:原帖由 fitcat07 於 2014-7-28 06:19 PM 发表
我恐怕会 TLE ...

引用:原帖由 Susan﹏汪汪 於 2014-7-28 06:45 PM 发表

理论上convolution可以有更优的复杂度
所以比直接计算会花更少时间

问题系如何精简化程式码

引用:原帖由 fitcat07 於 2014-7-28 10:17 PM 发表
每个查询时间复杂度可以做到 O(1)

复制内容到剪贴板代码:>>> a1 = [ 2, 0, 1 ]
>>> fsqr = lambda a1,a2 : [ a*b for a,b in zip(a1, a2) ]
>>> a2 = fsqr(a1, a1)
>>> multipliers = range(1, len(a1) +1)
>>> sum([ a * b for a,b in zip(a2, multipliers)])
7
>>>
>>> a1 = [ 3, 3 ]
>>> a2 = fsqr(a1, a1)
>>> multipliers = range(1, len(a1) +1)
>>> sum([ a * b for a,b in zip(a2, multipliers)])
27

复制内容到剪贴板代码:function fillArray(length, functor, thisArg)
{
return Array.apply(null, new Array(length)).map(functor, thisArg);
}

function complex(_re, _im)
{
this.real = isNaN(_re) ? 0 : Number(_re);
this.imag = isNaN(_im) ? 0 : Number(_im);
}

function real(_c)
{
if(isNaN(_c))
return _c.real;
else
return Number(_c);
}
function imag(_c)
{
if(isNaN(_c))
return _c.imag;
else
return 0;
}
function norm(_c)
{
if(isNaN(_c))
return _c.real * _c.real + _c.imag * _c.imag;
else
return Number(_c) * Number(_c);
}
function abs(_c)
{
if(isNaN(_c))
return Math.sqrt(norm(_c));
else
return Math.abs(Number(_c));
}
function arg(_c)
{
if(isNaN(_c))
return Math.atan2(_c.imag, _c.real);
else
return 0;
}
function conj(_c)
{
if(isNaN(_c))
return new complex(_c.real, -_c.imag);
else
return Number(_c);
}
function polar(rho, theta)
{
if(isNaN(rho) || Number(rho) == 0)
return 0;
else if(isNaN(theta) || Number(theta) == 0)
return Number(rho);
else if(Number(theta) == Math.PI)
return -Number(rho);
else
return new complex(Number(rho) * Math.cos(Number(theta)), Number(rho) * Math.sin(Number(theta)));
}
function plus(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real + b.real, a.imag + b.imag);
else if(isNaN(a))
return new complex(a.real + Number(b), a.imag);
else if(isNaN(b))
return new complex(Number(a) + b.real, b.imag);
else
return Number(a) + Number(b);
}
function minus(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real - b.real, a.imag - b.imag);
else if(isNaN(a))
return new complex(a.real - Number(b), a.imag);
else if(isNaN(b))
return new complex(Number(a) - b.real, -b.imag);
else
return Number(a) - Number(b);
}
function multiplies(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real * b.real - a.imag * b.imag, a.imag * b.real + b.imag * a.real);
else if(isNaN(a))
return new complex(a.real * Number(b), a.imag * Number(b));
else if(isNaN(b))
return new complex(Number(a) * b.real, Number(a) * b.imag);
else
return Number(a) * Number(b);
}
function divides(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex((a.real * b.real + a.imag * b.imag) / norm(b), (a.imag * b.real - b.imag * a.real) / norm(b));
else if(isNaN(a))
return new complex(a.real / Number(b), a.imag / Number(b));
else if(isNaN(b))
return new complex((Number(a) * b.real) / norm(b), (-b.imag * Number(a)) / norm(b));
else
return Number(a) / Number(b);
}

function Fourier(data)
{
switch(data.length)
{
case 0:
return new Array;

case 1:
return data;

case 2:
var data_1 = multiplies(data[0], Math.SQRT1_2);
var data_2 = multiplies(data[1], Math.SQRT1_2);
return new Array(plus(data_1, data_2), minus(data_1, data_2));

default:
if((data.length & (data.length - 1)) == 0) return Radix2CooleyTukey(data);
else return Bluestein(data);
}
}
function Radix2CooleyTukey(data)
{
var result = new Array;
for (var i = 0; i < data.length; ++i)
{
var idx = 0;
var _idx = i;
var _level = data.length;
while (_level >>= 1)
{
idx += (_idx < _level ? 0 : Math.floor(data.length / _level) >> 1);
_idx %= _level;
}
result[i] = divides(data[idx], Math.sqrt(data.length));
}

for (var level = 1; level < data.length; level <<= 1)
{
var temp = result.slice(0);
for (var i = 0; i < data.length; ++i)
{
var local = i % (level << 1);
var global = (level << 1) * Math.floor(i / (level << 1));
var k = global + local % level;
var _angle = -Math.PI * (local % level) / level;
var _polar = polar((local < level ? 1 : -1), _angle);
result[i] = plus(temp[k], multiplies(_polar, temp[k + level]));
}
}

return result;
}
function Bluestein(data)
{
var signal = new Array;
var kernel = new Array;
var phase = new Array;

for(var idx = 0; idx < data.length; ++idx)
{
var k = (idx * idx) % (2 * data.length);
phase[idx] = polar(1, -k * Math.PI / data.length);
kernel[idx] = conj(phase[idx]);
signal[idx] = multiplies(data[idx], phase[idx]);
}
var result = Convolve(signal, kernel);

var part = result.slice(data.length);
result = result.slice(0, data.length);
if(data.length % 2)
{
for(var idx = 0; idx < part.length; ++idx)
result[idx] = minus(result[idx], part[idx]);
} else
{
for(var idx = 0; idx < part.length; ++idx)
result[idx] = plus(result[idx], part[idx]);
}

for(var idx = 0; idx < result.length; ++idx)
result[idx] = divides(multiplies(phase[idx], result[idx]), Math.sqrt(data.length));

return result;
}
function Flip(data)
{
var temp = data.shift();
data.reverse();
data.unshift(temp);
return data;
}
function InverseFourier(data)
{
return Flip(Fourier(data));
}
function Convolve(signal, kernel)
{
var result = new Array;
if(signal.length == 0 || kernel.length == 0) return result;
if(signal.length == 1)
{
for(var idx = 0; idx < kernel.length; ++idx) result.push(multiplies(kernel[idx], signal[0]));
return result;
}
if(kernel.length == 1)
{
for(var idx = 0; idx < signal.length; ++idx) result.push(multiplies(signal[idx], kernel[0]));
return result;
}

var complexity = [
_split_convolve_complexity(signal.length, kernel.length),
_split_convolve_complexity(kernel.length, signal.length),
_fft_convolve_complexity(signal.length, kernel.length),
];

if(complexity[0] <= complexity[2] || complexity[1] <= complexity[2])
{
var _signal, _kernel;
if(complexity[0] <= complexity[1])
{
_signal = signal;
_kernel = kernel;
} else
{
_kernel = signal;
_signal = kernel;
}
var split_length = _split_convolve_length(_signal.length);
var num = parseInt(_signal.length / split_length);
for(var i = 0; i < num; ++i)
{
var temp = Convolve(_signal.slice(i * split_length, (i + 1) * split_length), _kernel);
for(var j = i * split_length; j < result.length; ++j)
result[j] = plus(result[j], temp.shift());
result = result.concat(temp);
}
if(_signal.length % split_length)
{
var temp = Convolve(_signal.slice(num * split_length), _kernel);
for(var j = num * split_length; j < result.length; ++j)
result[j] = plus(result[j], temp.shift());
result = result.concat(temp);
}
return result;
}
return _fft_convolve(signal, kernel);
}
function _fft_convolve(signal, kernel)
{
var _length = _fft_convolve_length(signal.length, kernel.length);
var _signal = Radix2CooleyTukey(signal.concat(fillArray(_length - signal.length, Number.prototype.valueOf, 0)));
var _kernel = Radix2CooleyTukey(kernel.concat(fillArray(_length - kernel.length, Number.prototype.valueOf, 0)));

var result = new Array;
for(var idx = 0; idx < _length; ++idx)
result[idx] = multiplies(_signal[idx], _kernel[idx]);
result = InverseFourier(result).slice(0, signal.length + kernel.length - 1);

for(var idx = 0; idx < result.length; ++idx)
result[idx] = multiplies(result[idx], Math.sqrt(_length));
return result;
}
function _fft_convolve_length(x, y)
{
return 1 << Math.ceil(Math.log(x + y - 1) / Math.LN2);
}
function _fft_convolve_complexity(x, y)
{
var length = _fft_convolve_length(x, y);
return 3 * length * Math.ceil(Math.log(length) / Math.LN2) + 2 * length;
}
function _mixed_convolve_complexity(x, y)
{
if (x == 1 || y == 1) return x * y;
return Math.min(_split_convolve_complexity(x, y), _split_convolve_complexity(y, x), _fft_convolve_complexity(x, y));
}
function _split_convolve_length(x)
{
return parseInt(Math.sqrt(x));
}
function _split_convolve_complexity(x, y)
{
var _x = _split_convolve_length(x);
return parseInt(x / _x) * _mixed_convolve_complexity(_x, y) + (x % _x ? _mixed_convolve_complexity(x % _x, y) : 0);
}


function triSum(a)
{
if (a.length == 1)
{
return a[0] * a[0];
}

var uHalfLength = Math.ceil(a.length / 2);
var dHalfLength = Math.floor(a.length / 2);

var sum = triSum(a.slice(0, dHalfLength)) + triSum(a.slice(-dHalfLength));

var _c = Convolve(a.slice(0, uHalfLength), a.slice(-uHalfLength));
for(var val in _c)
{
sum += real(_c[val]);
}

return sum;
}

var n = readline();
var a = readline().split(" ");
var m = readline();

while(m--)
{
var uv = readline().split(" ");
var sub = a.slice(uv[0], Number(uv[1]) + 1);
print(triSum(sub));
}

复制内容到剪贴板代码:function fillArray(length, functor, thisArg)
{
return Array.apply(null, new Array(length)).map(functor, thisArg);
}

function complex(_re, _im)
{
this.real = isNaN(_re) ? 0 : Number(_re);
this.imag = isNaN(_im) ? 0 : Number(_im);
}

function real(_c)
{
if(isNaN(_c))
return _c.real;
else
return Number(_c);
}
function imag(_c)
{
if(isNaN(_c))
return _c.imag;
else
return 0;
}
function norm(_c)
{
if(isNaN(_c))
return _c.real * _c.real + _c.imag * _c.imag;
else
return Number(_c) * Number(_c);
}
function abs(_c)
{
if(isNaN(_c))
return Math.sqrt(norm(_c));
else
return Math.abs(Number(_c));
}
function arg(_c)
{
if(isNaN(_c))
return Math.atan2(_c.imag, _c.real);
else
return 0;
}
function conj(_c)
{
if(isNaN(_c))
return new complex(_c.real, -_c.imag);
else
return Number(_c);
}
function polar(rho, theta)
{
if(isNaN(rho) || Number(rho) == 0)
return 0;
else if(isNaN(theta) || Number(theta) == 0)
return Number(rho);
else if(Number(theta) == Math.PI)
return -Number(rho);
else
return new complex(Number(rho) * Math.cos(Number(theta)), Number(rho) * Math.sin(Number(theta)));
}
function plus(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real + b.real, a.imag + b.imag);
else if(isNaN(a))
return new complex(a.real + Number(b), a.imag);
else if(isNaN(b))
return new complex(Number(a) + b.real, b.imag);
else
return Number(a) + Number(b);
}
function minus(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real - b.real, a.imag - b.imag);
else if(isNaN(a))
return new complex(a.real - Number(b), a.imag);
else if(isNaN(b))
return new complex(Number(a) - b.real, -b.imag);
else
return Number(a) - Number(b);
}
function multiplies(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real * b.real - a.imag * b.imag, a.imag * b.real + b.imag * a.real);
else if(isNaN(a))
return new complex(a.real * Number(b), a.imag * Number(b));
else if(isNaN(b))
return new complex(Number(a) * b.real, Number(a) * b.imag);
else
return Number(a) * Number(b);
}
function divides(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex((a.real * b.real + a.imag * b.imag) / norm(b), (a.imag * b.real - b.imag * a.real) / norm(b));
else if(isNaN(a))
return new complex(a.real / Number(b), a.imag / Number(b));
else if(isNaN(b))
return new complex((Number(a) * b.real) / norm(b), (-b.imag * Number(a)) / norm(b));
else
return Number(a) / Number(b);
}

function Fourier(data)
{
switch(data.length)
{
case 0:
return new Array;

case 1:
return data;

case 2:
var data_1 = multiplies(data[0], Math.SQRT1_2);
var data_2 = multiplies(data[1], Math.SQRT1_2);
return new Array(plus(data_1, data_2), minus(data_1, data_2));

default:
if((data.length & (data.length - 1)) == 0) return Radix2CooleyTukey(data);
else return Bluestein(data);
}
}
function Radix2CooleyTukey(data)
{
var result = new Array;
for (var i = 0; i < data.length; ++i)
{
var idx = 0;
var _idx = i;
var _level = data.length;
while (_level >>= 1)
{
idx += (_idx < _level ? 0 : Math.floor(data.length / _level) >> 1);
_idx %= _level;
}
result[i] = divides(data[idx], Math.sqrt(data.length));
}

for (var level = 1; level < data.length; level <<= 1)
{
var temp = result.slice(0);
for (var i = 0; i < data.length; ++i)
{
var local = i % (level << 1);
var global = (level << 1) * Math.floor(i / (level << 1));
var k = global + local % level;
var _angle = -Math.PI * (local % level) / level;
var _polar = polar((local < level ? 1 : -1), _angle);
result[i] = plus(temp[k], multiplies(_polar, temp[k + level]));
}
}

return result;
}
function Bluestein(data)
{
var signal = new Array;
var kernel = new Array;
var phase = new Array;

for(var idx = 0; idx < data.length; ++idx)
{
var k = (idx * idx) % (2 * data.length);
phase[idx] = polar(1, -k * Math.PI / data.length);
kernel[idx] = conj(phase[idx]);
signal[idx] = multiplies(data[idx], phase[idx]);
}
var result = Convolve(signal, kernel);

var part = result.slice(data.length);
result = result.slice(0, data.length);
if(data.length % 2)
{
for(var idx = 0; idx < part.length; ++idx)
result[idx] = minus(result[idx], part[idx]);
} else
{
for(var idx = 0; idx < part.length; ++idx)
result[idx] = plus(result[idx], part[idx]);
}

for(var idx = 0; idx < result.length; ++idx)
result[idx] = divides(multiplies(phase[idx], result[idx]), Math.sqrt(data.length));

return result;
}
function Flip(data)
{
var temp = data.shift();
data.reverse();
data.unshift(temp);
return data;
}
function InverseFourier(data)
{
return Flip(Fourier(data));
}
function Convolve(signal, kernel)
{
if (signal.length == 0 || kernel.length == 0)
{
return new Array;
}
if (signal.length == 1)
{
var result = new Array;
for(var idx = 0; idx < kernel.length; ++idx)
result[idx] = multiplies(signal[0], kernel[idx]);
return result;
}
if (kernel.length == 1)
{
var result = new Array;
for(var idx = 0; idx < signal.length; ++idx)
result[idx] = multiplies(signal[idx], kernel[0]);
return result;
}

return _split_convolve(signal, kernel);
}
function _split_convolve(signal, kernel)
{
if (signal.length == 1)
{
var result = new Array;
for(var idx = 0; idx < kernel.length; ++idx)
result[idx] = multiplies(signal[0], kernel[idx]);
return result;
}
if (kernel.length == 1)
{
var result = new Array;
for(var idx = 0; idx < signal.length; ++idx)
result[idx] = multiplies(signal[idx], kernel[0]);
return result;
}
if (signal.length < kernel.length)
{
return _split_convolve(kernel, signal);
}

var _split_length = _split_convolve_length(signal.length, kernel.length);

if (_split_length == signal.length)
{
return _fft_convolve(signal, kernel);
}

var size = signal.length + kernel.length - 1;
var bound = _split_length;

var n = Math.floor(signal.length / _split_length);
var _r = signal.length % _split_length ? 1 : 0;

var result;
for (var i = 0; i < n + _r; ++i)
{
if (i == n) bound = signal.length % _split_length;

var part = signal.slice(i * _split_length, i * _split_length + bound);

if (_split_length == 1)
{
part = _split_convolve(kernel, part);
} else
{
part = _fft_convolve(part, kernel);
}

if(i == 0)
{
result = part;
} else
{
for (var j = 0; j < kernel.length - 1; ++j)
{
result[i * _split_length + j] = plus(result[i * _split_length + j], part[j]);
}
result = result.concat(part.slice(kernel.length - 1));
}
}

return result;
}
function _fft_convolve(signal, kernel)
{
var _length = _fft_convolve_length(signal.length, kernel.length);
var _signal = Radix2CooleyTukey(signal.concat(fillArray(_length - signal.length, Number.prototype.valueOf, 0)));
var _kernel = Radix2CooleyTukey(kernel.concat(fillArray(_length - kernel.length, Number.prototype.valueOf, 0)));

var result = new Array;
for(var idx = 0; idx < _length; ++idx)
result[idx] = multiplies(_signal[idx], _kernel[idx]);
result = InverseFourier(result).slice(0, signal.length + kernel.length - 1);

for(var idx = 0; idx < result.length; ++idx)
result[idx] = multiplies(result[idx], Math.sqrt(_length));
return result;
}
function _fft_convolve_length(x, y)
{
return 1 << Math.ceil(Math.log(x + y - 1) / Math.LN2);
}
function _fft_convolve_complexity(x, y)
{
var length = _fft_convolve_length(x, y);
return 3 * length * Math.ceil(Math.log(length) / Math.LN2) + 2 * length;
}
function _split_convolve_complexity(x, y, _x)
{
return Math.floor(x / _x) * _fft_convolve_complexity(_x, y) + (x % _x ? _fft_convolve_complexity(x % _x, y) : 0);
}
function _split_convolve_length(x, y)
{
var _split_length = 1;
var _min_complexity = x * y;

var temp = _fft_convolve_complexity(x, y);
if (temp < _min_complexity)
{
_min_complexity = temp;
_split_length = x;
}

var _y = Math.ceil(Math.log(y) / Math.LN2);

for (var i = _y + 1; (1 << i) - y < x; ++i)
{
temp = _split_convolve_complexity(x, y, (1 << i) - y);
if (_min_complexity > temp)
{
_min_complexity = temp;
_split_length = (1 << i) - y;
}
}

return _split_length;
}


function triSum(a)
{
if (a.length == 1)
{
return a[0] * a[0];
}

var uHalfLength = Math.ceil(a.length / 2);
var dHalfLength = Math.floor(a.length / 2);

var sum = triSum(a.slice(0, dHalfLength)) + triSum(a.slice(-dHalfLength));

var _c = Convolve(a.slice(0, uHalfLength), a.slice(-uHalfLength));
for(var val in _c)
{
sum += real(_c[val]);
}

return sum;
}

var n = readline();
var a = readline().split(" ");
var m = readline();

while(m--)
{
var uv = readline().split(" ");
var sub = a.slice(uv[0], Number(uv[1]) + 1);
print(triSum(sub));
}