相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4827
神犇题解:https://blog.sengxian.com/solutions/hnoi-2017-day1
解题报告
这题怎么讲呢?如果你不知道循环卷积,那么你只有$70$分
比如说:我 _(:з」∠)_
百度百科上循环卷积这个词条的例题就是这题
所以知道循环卷积的定义,然后写一个$FFT$就可以了
Code
#include<bits/stdc++.h> #define LL long long #define CPL complex<double> using namespace std; const int N = 200000; const int INF = 2e9; const double EPS = 0.5; const double PI = acos(-1); int n,m,B,C,mx,len,tt,f[N],pos[N]; CPL a[N],b[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void FFT(CPL *arr, int ty) { for (int i=0;i<len;i++) { if (pos[i] < i) { swap(arr[pos[i]], arr[i]); } } for (int ll=1;ll<len;ll<<=1) { CPL wn(cos(PI/ll), sin(PI/ll)*ty); for (int i=0;i<len;i+=ll*2) { CPL w(1,0); for (int j=0;j<ll;j++,w=w*wn) { CPL tmp = arr[i+j+ll] * w; arr[i+j+ll] = arr[i+j] - tmp; arr[i+j] = arr[i+j] + tmp; } } } if (ty == -1) { for (int i=0;i<len;i++) { arr[i] /= len; } } } int main() { n = read(); m = read(); for (int i=0,tmp;i<n;i++) { B += (tmp = read()) << 1; C += tmp * tmp; a[i] = CPL{tmp, 0}; } for (int i=0,tmp;i<n;i++) { B -= (tmp = read()) << 1; C += tmp * tmp; b[n-i] = CPL{tmp, 0}; } for (len=1,tt=-1;len<n*2;len<<=1,++tt); for (int i=1;i<len;i++) { pos[i] = pos[i>>1]>>1; if (i&1) { pos[i] |= 1 << tt; } } FFT(a, 1); FFT(b, 1); for (int i=0;i<len;i++) { a[i] = a[i] * b[i]; } FFT(a, -1); for (int i=n;i<len;i++) { a[i%n] += a[i]; } for (int i=0;i<n;i++) { f[i] = a[i].real() + EPS; mx = max(f[i], mx); } C = C - 2 * mx; int p1 = -1.0 * B / 2 / n + EPS; int p2 = -1.0 * B / 2 / n - EPS; printf("%d\n",min(p1*p1*n+B*p1, p2*p2*n+B*p2) + C); return 0; }
I think the admin of this web site is genuinely working hard in favor of his website,
as here every data is quality based information.
Hey there! I’ve been reading your website for a long time now
and finally got the bravery to go ahead and give you a shout out from Atascocita Texas!
Just wanted to mention keep up the good work!
Its not my first time to pay a visit this website, i am browsing this website dailly and take pleasant information from here all the time.
Wow, marvelous blog layout! How long have you been blogging for?
you make blogging look easy. The overall look of your site is excellent, let
alone the content!
Hmm is anyone else experiencing problems with
the images on this blog loading? I’m trying to determine if its a problem on my end
or if it’s the blog. Any feed-back would be greatly appreciated.
I don’t even know how I ended up here, but I thought this post was great.
I don’t know who you are but definitely you’re going to a famous
blogger if you are not already 😉 Cheers!
Hi Dear, are you genuinely visiting this web site daily, if
so then you will absolutely obtain fastidious
knowledge.
These are actually impressive ideas in regarding blogging.
You have touched some pleasant things here. Any way keep up
wrinting.
Good response in return of this matter with genuine arguments and
describing the whole thing concerning that.
It’s amazing to pay a quick visit this site and reading the views of all mates about this paragraph, while I am also eager of getting knowledge.
In fact when someone doesn’t understand afterward its up to other users that they will assist,
so here it occurs.
Its like you read my mind! You seem to know so much about this,
like you wrote the book in it or something. I think that you could do with a few
pics to drive the message home a little bit, but instead of that, this is wonderful blog.
A fantastic read. I will certainly be back.
I like what you guys are usually up too. Such
clever work and reporting! Keep up the terrific works guys I’ve included
you guys to my own blogroll.
Do you mind if I quote a few of your articles as long as I provide credit and sources back to your weblog? My blog is in the very same niche as yours and my users would genuinely benefit from a lot of the information you present here. Please let me know if this alright with you. Thank you!
If some one wishes to be updated with most recent technologies after that he must be
pay a visit this web site and be up to date daily.
I was suggested this website by my cousin. I’m not sure whether this post is written by him as nobody else know such detailed
about my difficulty. You are amazing! Thanks!
Wow, amazing blog layout! How long have you been blogging for?
you make blogging look easy. The overall look of your site
is great, as well as the content!
Fantastic beat ! I would like to apprentice while you amend your
web site, how can i subscribe for a blog website? The account aided
me a acceptable deal. I had been a little bit acquainted of this your broadcast provided bright clear concept
I am really enjoying the theme/design of your blog.
Do you ever run into any internet browser compatibility problems?
A small number of my blog readers have complained about my site not
working correctly in Explorer but looks great in Opera.
Do you have any advice to help fix this problem?
Heya i’m for the primary time here. I found this board and I
in finding It truly useful & it helped me out much. I hope to provide something again and aid others like you aided me.
I seriously love your site.. Excellent colors & theme.
Did you develop this site yourself? Please reply back as I’m wanting to create my own website and want to find out where you got this from or exactly what the theme is
named. Appreciate it!
This paragraph is really a good one it helps new the web viewers, who are wishing in favor of blogging.
Aw, this was an extremely good post. Taking a few minutes and actual effort
to generate a very good article… but what can I say… I procrastinate
a lot and never seem to get anything done.
Extremely educative bless you, I do believe your trusty subscribers might want far more items of this nature maintain the excellent effort.
Do not enough money to buy a building? You not have to worry, just because it’s possible to receive the business loans to solve such problems. Therefore take a car loan to buy all you want.
I’m working on a new list. I’m hopeful that this one will be much bigger. I made some announcements about my future site plans.one will be much bigger. I made some announcements about my future site plans.I’m going to be adding some new stuff soon. You’ll definitely want to stay tuned for that.
Worthwhile information as well as outstanding design you’ve got here!
Hello just wanted to give you a quick heads up and let you know a few of the images aren’t loading properly. I’m not sure why but I think its a linking issue. I’ve tried it in two different browsers and both show the same results.