【日常小测】超级绵羊异或

题目大意

求$(b)\oplus(b+a)\oplus(b+2a)\oplus\cdots\oplus(b+(n-1)a)$
其中$n,a,b\le10^9$

解题报告

因为是二进制,所以我们每一位分开考虑
又因为数$a$二进制下第$k$位的奇偶性与$a>>(k-1)$的奇偶性相同
所以对于第$k$位,我们实际是要求$\sum\limits_{x=0}^{n-1}{\left\lfloor {\frac{{ax + b}}{{{2^k}}}} \right\rfloor}$,我们将其一般化:求解$f(a,b,c,n)=\sum\limits_{x=0}^{n}{\left\lfloor {\frac{{ax + b}}{{{c}}}} \right\rfloor}$

设$s(x)=\sum\limits_{i=1}^{x}{i}$。为了只讨论$a,b<c$的情况,我们先来预处理一下:

  1. 若$a \ge c$那么显然$f(a,b,c,n) = f(a \% c,b,c,n) + \lfloor\frac{a}{c}\rfloor \cdot s(n)$
  2. 若$b \ge c$那么显然$f(a,b,c,n) = f(a,b\%c,c,n) + \lfloor\frac{b}{c}\rfloor \cdot n$

之后我们就可以施展膜法了:
设$m=\lfloor\frac{an+b}{c}\rfloor$
那么原式$=\sum\limits_{x=0}^{n}{\sum\limits_{y=0}^{m}{[y<\lfloor\frac{ax+b}{c}\rfloor]}}$
把$y<\lfloor\frac{ax+b}{c}\rfloor$提出来,可以化简:
$y<\lfloor\frac{ax+b}{c}\rfloor = c(y+1) \le ax+b = cy+c-b-1<ax=x>\lfloor\frac{cy+c-b-1}{a}\rfloor$
那么原式$=\sum\limits_{y=0}^{m}{\sum\limits_{x=0}^{n}{[x>\lfloor\frac{cy+c-b-1}{a}\rfloor]}}=n(m+1)-\sum\limits_{y=0}^m{\lfloor\frac{cy+c-b-1}{a}\rfloor}$
相当于$f(a,b,c,n)=n(m+1)-f(c,c-b\%c-1,a\%c,m)$
窝萌发现,这货的形式简直和辗转相处搞$gcd$一模一样
于是这货的复杂度也是$O(\log n)$的

当然这题还有一种数形结合的推法
推出来式子略有不同,不过时间复杂度仍然为$O(\log n)$
不过本文这种推法似乎更优?据敦敦敦讲,这货可以推广到高维
但我不会 QwQ

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read() {
	char c=getchar(); int ret=0,f=1;
	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;
}

LL cal(LL a, LL b, LL c, LL n) { 
	if (a >= c) return (((n-1)*n/2)*(a/c)&1) ^ cal(a%c, b, c, n);
	if (b >= c) return (n * (b/c) & 1) ^ cal(a, b%c, c, n);
	if (!a) return (b/c) * n & 1;
	LL nw = (a * (n - 1) + b) / c; 
	return ((n-1) * nw & 1) ^ cal(c, c - b - 1, a, nw);
}

int main() {
	for (int T=read(),a,b,n;T;T--) {
		n = read(); b = read(); 
		a = read(); LL c = 1, ans = 0;
		if (!b) {printf("%d\n",(n&1)?a:0); continue;} 
		for (int i=0;i<=60;i++,c<<=1) 
			ans += cal(a, b, c, n) * c;
		printf("%lld\n",ans);
	}
	return 0;
}

351 thoughts to “【日常小测】超级绵羊异或”

  1. Howdy! I could have sworn I’ve been to this site before but after going
    through a few of the articles I realized it’s new to me.
    Regardless, I’m definitely delighted I found it and I’ll be book-marking it and checking
    back regularly!

  2. First off I want to say excellent blog! I
    had a quick question in which I’d like to ask if you do not mind.

    I was interested to know how you center yourself and clear your thoughts prior to writing.
    I have had a hard time clearing my thoughts in getting my ideas out there.
    I truly do take pleasure in writing however
    it just seems like the first 10 to 15 minutes are lost simply just trying to figure out how to begin.
    Any ideas or tips? Cheers!

  3. Thanks for ones marvelous posting! I definitely
    enjoyed reading it, you can be a great author.I will ensure that I bookmark your blog and will come back later in life.
    I want to encourage you to definitely continue your great writing, have a nice morning!

  4. I really like your blog.. very nice colors & theme. Did you create
    this website yourself or did you hire someone to do it for you?
    Plz reply as I’m looking to construct my own blog and would
    like to find out where u got this from. thanks a lot

  5. Hi there would you mind letting me know which webhost
    you’re using? I’ve loaded your blog in 3 completely
    different internet browsers and I must say this blog loads a lot faster then most.
    Can you recommend a good web hosting provider at a reasonable price?
    Thanks, I appreciate it!

  6. Amazing blog! Is your theme custom made or did you download
    it from somewhere? A theme like yours with a few simple tweeks would really
    make my blog jump out. Please let me know
    where you got your design. Many thanks natalielise pof

  7. Howdy superb website! Does running a blog like this take a large amount of work?

    I have absolutely no knowledge of coding but I was hoping to start my own blog in the near future.
    Anyway, if you have any suggestions or techniques for new blog owners please share.
    I understand this is off subject nevertheless I just wanted to ask.

    Many thanks! pof natalielise

  8. Having read this I believed it was really enlightening.
    I appreciate you finding the time and effort to put this
    informative article together. I once again find
    myself spending a significant amount of time both reading and posting comments.
    But so what, it was still worth it!

  9. I have been browsing on-line greater than 3
    hours as of late, but I by no means discovered any interesting article like yours.
    It is lovely worth sufficient for me. In my opinion, if all web
    owners and bloggers made excellent content as you probably did, the internet will probably be
    a lot more helpful than ever before.

  10. Oh my goodness! Awesome article dude! Many thanks, However I am having
    troubles with your RSS. I don’t understand the reason why I cannot subscribe to it.
    Is there anybody else having similar RSS issues? Anybody who knows the solution will you kindly respond?
    Thanx!!

  11. Hmm it looks like your blog ate my first comment (it was extremely long) so I guess I’ll just sum it up what
    I had written and say, I’m thoroughly enjoying your blog. I as well am
    an aspiring blog writer but I’m still new to everything.
    Do you have any tips for newbie blog writers? I’d definitely
    appreciate it.

  12. Undeniably believe that that you stated. Your favorite reason appeared to
    be on the web the easiest thing to be mindful of.
    I say to you, I definitely get irked at the same
    time as other folks consider issues that they plainly don’t
    realize about. You controlled to hit the nail upon the highest as
    smartly as outlined out the whole thing without having side-effects ,
    folks could take a signal. Will likely be again to get
    more. Thank you

  13. Hey! This post couldn’t be written any better! Reading this post reminds me of
    my old room mate! He always kept chatting about this.
    I will forward this article to him. Fairly certain he
    will have a good read. Many thanks for sharing!

  14. My brother recommended I might like this blog. He was entirely right.

    This post actually made my day. You cann’t consider simply how a lot time I had spent for this info!

    Thanks!

  15. When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment
    is added I get four e-mails with the same comment.
    Is there any way you can remove people from that service?

    Cheers!

  16. Yesterday, while I was at work, my sister stole my iphone and tested to see
    if it can survive a thirty foot drop, just so she can be a
    youtube sensation. My iPad is now broken and she has 83 views.
    I know this is entirely off topic but I had to share it with someone!

  17. Hey just wanted to give you a quick heads up. The text in your post seem to be running off
    the screen in Opera. I’m not sure if this is a format issue or something to do
    with internet browser compatibility but I thought
    I’d post to let you know. The design and style look great though!

    Hope you get the issue fixed soon. Kudos

  18. What’s Taking place i am new to this, I stumbled upon this
    I have discovered It positively useful and it has aided me
    out loads. I’m hoping to give a contribution & aid other users like its aided me.
    Great job.

  19. Write more, thats all I have to say. Literally, it seems as though you relied on the video
    to make your point. You clearly know what youre talking
    about, why waste your intelligence on just posting
    videos to your blog when you could be giving us something enlightening to read?

  20. Greetings from Colorado! I’m bored at work so I decided to
    check out your website on my iphone during lunch break.
    I love the information you present here and can’t wait to take a look when I get home.
    I’m shocked at how quick your blog loaded on my mobile ..
    I’m not even using WIFI, just 3G .. Anyways, excellent blog!

  21. Please let me know if you’re looking for a author for your weblog.

    You have some really good posts and I believe I would be a good asset.
    If you ever want to take some of the load off, I’d love to write some
    material for your blog in exchange for a link back to mine.
    Please send me an e-mail if interested. Cheers!

  22. I don’t know whether it’s just me or if perhaps everybody
    else experiencing problems with your site. It seems like some of the
    text within your content are running off the screen. Can someone else please provide feedback
    and let me know if this is happening to them as well?
    This might be a problem with my web browser because I’ve had this happen before.
    Many thanks

  23. 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 bit, but other than that, this is excellent blog.
    An excellent read. I’ll definitely be back.

  24. I really like your blog.. very nice colors & theme. Did you
    create this website yourself or did you hire someone
    to do it for you? Plz respond as I’m looking to create my own blog and would like to know where u got this from.

    many thanks

  25. Have you ever thought about publishing an e-book or guest authoring on other blogs?
    I have a blog based upon on the same information you discuss and would love to have you share some stories/information. I know my viewers would value your work.

    If you are even remotely interested, feel free
    to send me an e mail.

  26. whoah this blog is magnificent i love studying your posts.
    Keep up the good work! You realize, lots of people are searching round for this info,
    you could help them greatly.

  27. Link exchange is nothing else except it is just placing the other person’s blog link on your page at suitable place and other person will also do similar in support
    of you.

  28. I do not even know how I stopped up here, however I believed this put up was once
    great. I don’t recognise who you are however certainly
    you’re going to a well-known blogger if you happen to aren’t already.
    Cheers!

  29. An intriguing discussion is definitely worth comment.
    I do think that you should write more about this subject, it might not be a taboo matter but generally people don’t
    discuss these issues. To the next! Kind regards!!

  30. A fascinating discussion is definitely worth comment.
    There’s no doubt that that you ought to publish more about this subject, it might not be
    a taboo subject but usually folks don’t speak about such subjects.
    To the next! Kind regards!!

  31. Do you have a spam problem on this blog; I also am a blogger, and
    I was curious about your situation; many of us have developed some nice
    practices and we are looking to swap solutions with other folks, be
    sure to shoot me an e-mail if interested.

  32. What’s Taking place i am new to this, I stumbled upon this I’ve discovered It positively useful
    and it has helped me out loads. I hope to give a contribution & assist other customers like its aided me.
    Good job.

  33. I have fun with, result in I discovered just what I was taking a look for.
    You’ve ended my 4 day long hunt! God Bless you man. Have
    a nice day. Bye

  34. That is the right blog for anybody who desires to seek out out about this topic. You notice a lot its nearly exhausting to argue with you (not that I actually would want…HaHa). You definitely put a brand new spin on a subject thats been written about for years. Great stuff, simply nice!

  35. Hello there, I do believe your website could possibly be having browser compatibility problems.

    Whenever I look at your website in Safari, it looks fine however, when opening in IE,
    it’s got some overlapping issues. I merely wanted to give you a quick heads up!
    Apart from that, wonderful website!

  36. Hi! I know this is kind of off-topic but I needed to ask.
    Does operating a well-established website like yours take
    a lot of work? I’m brand new to running a blog however I do
    write in my journal daily. I’d like to start a blog so I can share my experience and
    feelings online. Please let me know if you have any kind of
    ideas or tips for brand new aspiring bloggers. Thankyou!

  37. When I initially left a comment I appear to have
    clicked on the -Notify me when new comments are added- checkbox and from now on whenever a comment is added I
    recieve four emails with the same comment. Is there a way you can remove me from that service?
    Cheers!

  38. I’m not sure exactly why but this site is loading incredibly
    slow for me. Is anyone else having this issue or is it a problem on my end?
    I’ll check back later on and see if the problem still exists.

  39. Hello! Do you know if they make any plugins to protect against hackers?
    I’m kinda paranoid about losing everything I’ve worked hard on. Any tips?

  40. I just couldn’t depart your site prior to suggesting that I actually enjoyed the standard information a person provide for your visitors? Is going to be back often to check up on new posts

  41. certainly like your web site however you need to test the spelling on quite a few of your posts. Many of them are rife with spelling issues and I in finding it very troublesome to inform the truth then again I¡¦ll certainly come again again.

  42. hello!,I like your writing very a lot! proportion we keep up a correspondence extra approximately your post on AOL? I require an expert in this area to resolve my problem. May be that is you! Looking forward to peer you.

  43. I want to point out my love for your kindness for individuals who absolutely need guidance on in this theme. Your real commitment to passing the solution up and down came to be amazingly significant and have in most cases encouraged regular people much like me to achieve their endeavors. Your helpful report can mean so much to me and somewhat more to my office colleagues. With thanks; from everyone of us.

  44. autosasartwhite leather converse nfl mens nike tampa bay buccaneers 31 jordan whitehead red name number pullover hoodie anthony miller womens limited white jersey nike nfl chicago bears vapor untouchable road 17 air max zero grey yellow nike kaishi noir hommes f…

  45. Hey there just wanted to give you a quick heads up. The words in your content seem to be running off the screen in Opera. I’m not sure if this is a format issue or something to do with web browser compatibility but I thought I’d post to let you know. The design and style look great though! Hope you get the issue fixed soon. Kudos|

  46. Hi there! This is my first visit to your blog! We are a group of volunteers and starting a new initiative in a community in the same niche. Your blog provided us valuable information to work on. You have done a extraordinary job!|

  47. Do you mind if I quote a couple of your articles as long as I provide credit and sources back to your blog? My blog site is in the very same niche as yours and my users would certainly benefit from a lot of the information you provide here. Please let me know if this ok with you. Appreciate it!|

  48. Howdy are using WordPress for your blog platform? I’m new to the blog world but I’m trying to get started and set up my own. Do you need any coding expertise to make your own blog? Any help would be really appreciated!|

  49. Heya i am for the first time here. I came across this board and I find It really useful & it helped me out much. I hope to give something back and aid others like you aided me.

  50. Hey there! I’ve been following your web site for a long time now and finally got the bravery to go ahead and give you a shout out from Lubbock Tx! Just wanted to tell you keep up the excellent job!|

  51. Hi there! This article could not be written any better! Looking through this post reminds me of my previous roommate! He continually kept talking about this. I most certainly will send this information to him. Pretty sure he will have a good read. Thank you for sharing!|

  52. Hi, i think that i saw you visited my site so i came to return the choose?.I’m trying to find issues to enhance my web site!I guess its good enough to use a few of your concepts!!|

  53. It’s truly very complicated in this busy life to listen news on TV, so I simply use internet for that reason, and get the latest news.|

Leave a Reply

Your email address will not be published. Required fields are marked *