Prob.3 of NOIP 2002 (Junior) *Solution*
More than two years ago, I thought it was an Ad Hoc problem and I had a try, but I failed.
Now I've realized it is just a math problem with floyd!
"Sky Gate":http://www.luogu.org/problem/show?pid=1037
Given a positive integer number n, and k ways of changing a digit. You could change a digit in a way called x y. Which means you could change number x into y. Then how many numbers could be produced after a series of changing operations? (Caution: We could change 0 times) Input: n k xi yi(1<=i<=k) Output: The answer required Sample Input: 234 2 2 5 3 6 Sample Output: 4 Explanations: 234, 264, 534, 564 are numbers available. For all 5 testcases: 1<=n<=10^30, 1<=k<=15, 0<=xi<=9, 1<=yi<=9
It's a problem of calculating the number of possible answers, but not a problem requiring every answer. So it's not recommended to use BFS, and that's why I failed two years ago...
Consider this situation: If a[i] means the number of ways that the i-th digit could change into, then the answer to the question is Πa[i]. It's obvious since every number couldn't be changed into zero unless it is zero at the beginning.
So use floyd to get can[i][j] indicating whether i could be changed into j.
Then get a[i]=Σcan[i][j].
Now calculate Πa[i] with higher precision.
Then it comes to coding...
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
int k,i,j,jw,x,y,ans[110],st[110],len,f[110];
bool a[10][10];
char c;
int main()
{
while((c=getchar())!=' ')st[++len]=c-48;
scanf("%d",&k);
for(i=1;i<=k;i++){scanf("%d%d",&x,&y);a[x][y]=1;}for(i=0;i<=9;i++)a[i][i]=1;
for(i=1;i<=9;i++)for(j=0;j<=9;j++)for(k=1;k<=9;k++)a[j][k]=a[j][k]||a[j][i]&&a[i][k];
ans[0]=ans[1]=1;
for(i=0;i<=9;i++)for(j=0;j<=9;j++)f[i]+=a[i][j];
for(i=1;i<=len;i++)
{
for(j=1;j<=ans[0];j++){ans[j]=ans[j]*f[st[i]]+jw;jw=ans[j]/10;ans[j]%=10;}
while(jw){ans[++ans[0]]=jw%10;jw/=10;}
}
for(i=ans[0];i>=1;i--)printf("%d",ans[i]);puts("");return 0;
}
Not very complex, in fact.
If you have a better solution, please show your solution through comments, and I'll take it seriously.
(Comments are welcomed and it is recommended that you reply in English.)
Sat, 22 Jan 2022 13:31:34 +0800
The Hot and Sexy Girls are here to give all sorts of fun and enjoyment here.
Tue, 01 Feb 2022 21:49:57 +0800
Wow, cool post. I'd like to publish similar to this too - taking time and real hard work to produce a great article... but I put things off too much and never seem to obtain started. Thanks though. 토토사이트
Sun, 27 Mar 2022 20:04:30 +0800
Youre so cool! I dont suppose Ive read anything this way before. So nice to uncover somebody by incorporating original applying for grants this subject. realy thank you for starting this up. this website is one thing that is required on the internet, someone after some originality. helpful job for bringing new stuff to your world wide web! Licensed Clinical Social Workers
Fri, 27 May 2022 18:25:07 +0800
Thanks for the auspicious writeup. It actually used to be a leisure account it. Glance complicated to more delivered agreeable from you! However, how can we be in contact? 먹튀검증
Sat, 04 Jun 2022 21:33:39 +0800
Thanks , I’ve just been searching for info about this topic for a while and yours is the greatest I have found out so far. But, what about the conclusion? Are you sure about the supply? 麥克風
Mon, 13 Jun 2022 21:03:36 +0800
This is actually exciting, You’re an enormously knowledgeable blogger. I have enrolled with your feed and also anticipate witnessing the useful write-ups. At the same time, I’ve shared your site in our social networks. 回收手提電腦
Tue, 14 Jun 2022 15:28:01 +0800
Tangling page on the web. The creator portrays all focal concentrate completely. Individuals can be reasonable. Overpowering explanation of the thing easy to understand.Keep posting
<a href="https://www.thebangaloreescorts.in/escorts/agartala.html">Agartala Escorts</a> ||
<a href="https://www.thebangaloreescorts.in/escorts/ajmer.html">Escorts in Ajmer</a> ||
<a href="https://www.thebangaloreescorts.in/escorts/akola.html">Akola Escorts Service</a> ||
<a href="https://www.thebangaloreescorts.in/escorts/ambattur.html">Escorts Service in Ambattur</a> ||
<a href="https://www.thebangaloreescorts.in/escorts/amravati.html">Amravati Escorts Agency</a> ||
Tue, 28 Jun 2022 16:18:02 +0800
Particularly overwhelming article all encounters reveals major as everybody would be reachable and clear. By approaches of the maker for sharing this blog. [url=https://www.thebangaloreescorts.in/]Independent Escorts in Bangalore[/url] Keep on circumnavigating
Thu, 08 Sep 2022 21:35:46 +0800
The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student, and the economics subject paper-1 AP 1st Inter Economics Model Paper and paper-2 important questions with suggestions are available through AP Jr and Sr inter Economics Model Paper 2023 Pdf with guess paper.
Mon, 03 Oct 2022 19:08:46 +0800
A domain name is an identification label which defines a realm of administrative autonomy, authority, or control in the Internet. Domain names are also critica for domain hosting\website hosting Macbook air
Sat, 29 Oct 2022 19:09:39 +0800
Extraordinary news particularly stunning site!! Individual .. Critical .. Floundering .. I will bookmark your blog and take the feeds furthermore,I'm fulfilled to track down a great deal of clear data here inside the set up, appreciation for sharing.
Sat, 29 Oct 2022 19:11:46 +0800
Appreciation for sharing this information. I really like your blog region obviously. You have truly shared an illuminating and overpowering web journal district with people.
Sat, 29 Oct 2022 19:13:22 +0800
This is a gigantic article. I think this is conceivably of the best part I've at whatever point disengaged. Your work is stunning and convincing. I really feel a commitment of appreciation.
Fri, 04 Nov 2022 23:48:51 +0800
Im no professional, but I believe you just crafted a very good point point. You definitely understand what youre talking about, and I can seriously get behind that. Thanks for staying so upfront and so truthful. 카지노사이트
Sat, 19 Nov 2022 03:53:24 +0800
Some genuinely interesting information, well written and loosely user friendly. 온라인카지노
Sat, 11 Mar 2023 12:53:52 +0800
What would you do if you know that Saket Escorts || is one of the best place where luxury high-class escort service providers are available? It has a list of finest and most beautiful as well as independent girls in this world.
Sat, 11 Mar 2023 19:59:52 +0800
You've probably heard about it just by chance. If not, then your partner might have told you that Escorts in Saket are among the best in the world. In fact, with a little research, you'll find that Delhi Escorts are among the most in-demand service providers for those seeking intimate companionship.
Mon, 13 Mar 2023 17:57:07 +0800
If you are searching for a reliable escort in Delhi, Do not worry anymore. Here is the right place to spend a totally night fun with Karol Bagh Call Girls .
Mon, 20 Mar 2023 19:38:24 +0800
She will bring you to some unforgettable places where you can relax, unwind and get yourself together when things need it. Hbr Layout Escorts || Hennur Escorts || Hangasandra Escorts || Horamavu Escorts || Hosur Escorts || Hsr Layout Escorts || Indraprastha Escorts || Jalahalli Escorts || Jayanagar Escorts || Kadugodi Escorts || Kalyan Nagar Escorts || Kengri Escorts || Mg Road Escorts |
Mon, 20 Mar 2023 19:39:40 +0800
Our ladies are all very experienced, friendly and ready to make you feel special. call girl number || bhabhi whatsapp number || sex videos || porn clip ||
Mon, 20 Mar 2023 19:40:40 +0800
They can give you a night of unforgettable passion Bangalore Escorts Service and delight that you will never forget in your entire life
Tue, 21 Mar 2023 15:14:51 +0800
Sex Stories Hindi || Articles is an Indian blog that aims to provide a sex platform for people who want to read and write sex stories in Hindi.
Wed, 05 Apr 2023 19:26:35 +0800
Hindi language has a vast collection of romantic stories that relate to the mischievous nature of love. It expresses feelings in a beautiful way and touches the heart with its melodious voice. This article discusses the main reasons why Chudai ki Kahani || are so special.
Thu, 20 Apr 2023 14:51:59 +0800
This article is a guest post by the team of Delhi Escort .
.
Sun, 23 Apr 2023 10:32:09 +0800
Thanks you!
Xây nhà trọn gói tại tphcm Thi cong alu Giá thi công nhà khung thép Sua nha gia re Giam sat cong trinh Xay nha gia re WinconsTue, 23 May 2023 15:37:17 +0800
We have the best in VIP Safdarjung Escorts and we have become the best choice for many of our clients who are looking for something more than ordinary girls.
Wed, 31 May 2023 15:56:05 +0800
We recommend that before viewing our collection, Hot Indian Wife Fucking a safe space with no outside distractions.
Wed, 02 Aug 2023 12:55:41 +0800
The Escorts Service is a very unique service because it allows people to request any type of escort that they want. They can request an escort for either a one-time situation or an ongoing basis, whatever they feel will work best for their situation ..Patna Call Girl || Call Girl in Mysore || Allahabad Escort Service || Nashik Call Girl || Ranchi Call Girl || coimbatore Escort Service || Call Girls in Saket || Call Girls in Mangalore || Call Girl Cuttack || Karimnagar Call Girls || Satara Call Girl || Puri Call Girl || Baner Call Girls || Call Girls in PaharGanj || Thane Escort Service || Call Girl in Aurangabad || Hubli Call Girls || Escort Service in Aerocity || Call Girl in Varanasi || Call Girls in kota
Wed, 23 Aug 2023 14:48:52 +0800
Thank you for the significant data on this extraordinary subject and for anticipating more extraordinary posts. You rock for partaking in this magnificence article with me. I'm feeling a debt of gratitude without a doubt! Anticipating another extraordinary article. Best of luck to the creator! The very best! sexy video || hot sexy video || sexy video bf || Ullu Sexy actress ||
Wed, 23 Aug 2023 14:49:21 +0800
It was a very good post indeed. I thoroughly enjoyed reading it in my lunch time. Will surely come and visit this blog more often. Thanks for sharing hindi sexy film || open sexy bp || Ullu sexy video || tamil sexy video || Telegram Adult channels || Desi Bhabhi Sexy Videos ||