NOI2013
最近做一下历年真题，写一些题解吧。
Day2T1
这是这年六道题里最水的一道，不过也没有1A，真是太弱了。
很容易由递推公式推出来通项公式，令
[tex]p = a^{m-1},\\r = \frac{a^{m-1}-1}{a-1}*b[/tex]
则有
[tex]f[i][m] = p*f[i][1]+r,\\f[i][1] = c*p*f[i-1][1]+c*r+d (i \ne 1)[/tex]
注意到此时已经推出来了第一列的递推公式，再依据每一行的递推公式，很容易得到每个数的通项公式，这里不再赘述，请看官自行推导。可是看一下数据就会发现，n，m的值很大最多有1000000位，这里我们采用一种类似于费马小定理的方法进行加速。下面具体来说，
费马小定理：
[tex]a^{\varphi(p)} \equiv 1 \pmod{p}[/tex]
注意到，当
[tex]m = base - 1[/tex]
时，[tex]p = 1[/tex],所以当[tex]m \leftarrow m \,\bmod\,\ (base - 1)[/tex]时，对答案无任何影响，对n同理。由此我们将原问题等价为[tex]n,m < base[/tex]的简单问题，结合我上面的公式即可写出程序。
注意：1.当a或c为1，时上面的公式会出现错误，请看官自行解决这个问题，我就是因为这个没有1A的。
2.除以(a-1)时采用逆元，具体方法见我之前的博文 OI数论总结
代码
#include<cstdio>
#include<cstring>
#define base 1000000007
#define dec(x) ((x - 1 + base) % base)
int n,nn,m,mm,a,b,c,d,p,r,p1,r1,p2,r2,x,n1,m1;
int getint(int &n){
int ret = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while('0' <= c && c <= '9') ret = ((long long)ret * 10LL + (long long)(c - '0')) % (long long)(base-1), n = ((long long)n * 10LL + (long long)(c - '0')) % (long long)(base), c = getchar();
return ret;
}
int MultiMod(int a,int b,int p){//a*b % p
int ret = 0,m = a;
while(b){
if(b & 1) ret = (ret + m) % p;
m = (m + m) % p;
b >>= 1;
}
return ret;
}
int PowerMod(int a,int b,int p){//a^b % p
int ret = 1,m = a;
while(b){
if(b & 1) ret = (long long)ret*(long long)m%(long long)p;
m = (long long)m*(long long)m%(long long)p;
b >>= 1;
}
return ret;
}
int main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
n = getint(n1),m = getint(m1);
nn = dec(n),mm = dec(m);
scanf("%d%d%d%d",&a,&b,&c,&d);
p = PowerMod(a,mm,base);
r = MultiMod(MultiMod(dec(p),PowerMod(a-1,base-2,base),base),b,base);
if(a == 1) r = MultiMod(dec(m1),b,base);
p1 = MultiMod(c,p,base);
r1 = (MultiMod(c,r,base) + d) % base;
p2 = PowerMod(p1,nn,base);
r2 = MultiMod(MultiMod(dec(p2),PowerMod(p1-1,base-2,base),base),r1,base);
if(p1 == 1) r2 = MultiMod(dec(n1),r1,base);
x = (p2+r2) % base;
x = (MultiMod(p,x,base)+r) % base;
printf("%d\n",x);
return 0;
}
2022年8月18日 14:07
JAC 12th Question Paper 2023 Download – JAC Intermediate Important Question Paper 2023 PDF, Jharkhand JAC 12th Question Paper 2023 Academic Council which is also abbreviated as JAC is one of the biggest education board for school which provides school education to students and responsible for conducting the examinations for the 10th and 12th class which is also called Intermediate.
2024年9月11日 15:16
http://richiewu.is-programmer.com/posts/210872.html
2024年9月11日 17:37
Thank you so much for the post you do. I like your post and all you share with us is up to date and quite informative, i would like to bookmark the page so i can come here again to read you, as you have done a wonderful job
2024年9月11日 17:38
I really impressed after read this because of some quality work and informative thoughts . I just wanna say thanks for the writer and wish you all the best for coming!.
2024年9月11日 17:39
Just saying thanks will not just be sufficient, for the fantasti c lucidity in your writing. I will instantly grab your rss feed to stay informed of any updates . Well, this got me thinking what other workouts are good for those of us who find ourselves on the road or have limited equipment options. I read a article under the same title some time ago, but this articles quality is much, much better. How you do this. Great job for publishing such a beneficial web site. Your web log isn’t only useful but it is additionally really creative too. There tend to be not many people who can certainly write not so simple posts that artistically. This is a great article thanks for sharing this informative information. I will visit your blog regularly for some latest post. I will visit your blog regularly for Some latest post.
2024年9月11日 17:40
Excellent article. The writing style which you have used in this article is very good and it made the article of better quality. Thank you so much for this informative post . Great info! I recently came across your blog and have been reading along. I thought I would leave my first comment. I don’t know what to say except that I have . This is an excellent post I seen thanks to share it. It is really what I wanted to see hope in future you will continue for sharing such a excellent post. Took me time to read all the comments, but I really enjoyed the article. It proved to be Very helpful to me and I am sure to all the commenters here! It’s always nice when you can not only be informed, but also entertained!
2024年9月11日 18:13
Positive site, where did u come up with the information on this posting?I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work
2024年9月11日 18:39
That's an interesting article. You have a real ability to write unique content. I like the way you express your thoughts and your views in this article. I agree with your way of thinking. His writing ability is also great I want to write the same thing as you..
2024年9月11日 18:40
What an impressive new idea! It touched me a lot. I want to hear your opinion on my site. Please come to my website and leave a comment. Thank you.
2024年9月11日 18:41
This is the type of information I’ve long been trying to find. Thank you for writing this information.
2024年9月11日 18:42
I was very pleased to find this site.I wanted to thank you for this great read!! I definitely enjoying every little bit of it and I have you bookmarked to check out new stuff you post. Thank you so much for sharing these amazing tips. I must say you are an incredible writer, I love the way that you describe the things. Please keep sharing . Im no expert, but I believe you just made an excellent point. You certainly fully understand what youre speaking about, and I can truly get behind that. Very likely I’m going to bookmark your blog . You absolutely have wonderful stories. Cheers for sharing with us your blog.
2024年9月11日 18:43
You really make it look so natural with your exhibition however I discover this issue to be really something which I figure I could never appreciate. It appears to be excessively confounded and amazingly wide for me. I’m searching forward for your next post, I’ll attempt to get its hang
2024年9月11日 18:44
Having read this I believed it was really informative. I appreciate you taking the time and effort to put this information together. I once again find myself spending a significant amount of time both reading and commenting. But so what, it was still worth it! It is good to hear that your store is now expanding to new locations. I have been a patron of Fantastic Eyes because of all the wonderful work that you guys do . hope that this expansion move of yours will turn out to be successful. I will definitely go and see this new store of yours .
2024年9月11日 18:45
I’m having a small problem. I’m unable to subscribe to your rss feed for some reason. I’m using google reader by the way. This is actually appealing, You’re a significantly seasoned author. I have joined with your feed plus expect witnessing the very good write-ups. And additionally, We’ve shared your web blog inside our social networking sites. After reading your article I was amazed. I know that you explain it very well. And I hope that other readers will also experience how I feel after reading your article. I found this one pretty fascinating and it should go into my collection. Very good work
2024年9月11日 19:10
A great content material as well as great layout. Your website deserves all of the positive feedback it’s been getting. I will be back soon for further quality contents..Hello, I have been using the service for many websites, but when I found your website, it was amazing. Thank you for sharing such good information.
2024年9月11日 19:12
I basically need to reveal to you that I am new to weblog and certainly enjoyed this blog webpage. Likely I’m going to bookmark your blog . You totally have superb stories. Supports imparting to us your blog.
2024年9月11日 19:18
Im obliged for the blog post. Really thank you! Awesome. ..Nice to be visiting your blog again, it has been months for me. Well this article that i’ve been waited for so long. I need this article to complete my assignment in the college, and it has same topic with your article. Thanks, grea
2024年9月11日 19:19
Such sites are important because they provide a large dose of useful information . Thanks with regard to publishing this type of excellent post! I discovered your site ideal for my personal requirements. It has fantastic as well as useful articles. Continue the great function! I am usually to blogging and i also actually appreciate your website content continuously. Your content has really peaks my interest. I’m going to bookmark your blog and maintain checking for new data. Great post, and great website. Thanks for the information!
2024年9月11日 19:20
I forgot about it for a long time. It popped up and I came back. It's still a pleasant blog. I should bookmark it so that I don't forget it again. without ever forgetting again
2024年9月11日 19:31
I’ve been surfing online more than 2 hours today, yet I never found any interesting article like yours. It is pretty worth enough for me. Personally, if all website owners and bloggers made good content as you did, the internet will be a lot more useful than ever before.
2024年9月11日 19:58
A great content material as well as great layout. Your website deserves all of the positive feedback it’s been getting. I will be back soon for further quality contents..Hello, I have been using the service for many websites, but when I found your website, it was amazing. Thank you for sharing such good information.
2024年9月11日 20:48
i feel so lucky because i've a blogger like you that gives clean thoughts depending on the every day scenario. To be very sincere, your blogs are easy to read and understand. True success with your destiny articles as properly. thanks for this enticing article. Now and again you operate actual-lifestyles examples to your articles that are perfect for me as a reader, however regrettably, every now and then i didn’t get your point within the put up. It seems fake or inapprorticle. You make this records interesting and tasty. You deliver readers plenty to consider and that i appreciate that sort of writing. Very good factors you wrote right here.. High-quality stuff... I suppose you have made a few honestly exciting points. Keep up the coolest paintings
2024年9月11日 21:40
You have done a great job on this article. It’s very readable and highly intelligent. You have even managed to make it understandable and easy to read. You have some real writing talent. Thank you.
2024年9月11日 22:27
I am impressed. I don't think Ive met anyone who knows as much about this subject as you do. You are truly well informed and very intelligent. You wrote something that people could understand and made the subject intriguing for everyone. Really, great blog you have got here. I'm glad I found this web site, I couldn't find any knowledge on this matter prior to.Also operate a site and if you are ever interested in doing some visitor writing for me if possible feel free to let me know, im always look for people to check out my web site.