Prob.3 of NOIP 2002 (Junior) *Solution*

酱油 posted @ Wed, 02 Sep 2015 16:46:22 +0800 in OI life with tags Solution , 935 readers

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.)

 

Avatar_small
Connaught Place Esco said:
Sat, 22 Jan 2022 13:31:34 +0800

The Hot and Sexy Girls are here to give all sorts of fun and enjoyment here.

Avatar_small
AAA said:
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. 토토사이트

Avatar_small
AAA said:
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

Avatar_small
AAA said:
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? 먹튀검증

Avatar_small
AAA said:
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? 麥克風

Avatar_small
AAA said:
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. 回收手提電腦

Avatar_small
Anamika said:
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> ||

Avatar_small
Anamika said:
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

Avatar_small
AP 1st Inter Economi said:
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.

Avatar_small
meidir said:
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

Avatar_small
New Delhi Escort said:
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.

Avatar_small
Massge Republic said:
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.

Avatar_small
Bangalore Escort Ser said:
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.

Avatar_small
meidir said:
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. 카지노사이트

Avatar_small
meidir said:
Sat, 19 Nov 2022 03:53:24 +0800

Some genuinely interesting information, well written and loosely user friendly. 온라인카지노

Avatar_small
shivani09 said:
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. 

Avatar_small
shivani09 said:
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. 

Avatar_small
shivani09 said:
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 .

Avatar_small
aliya said:
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 |

Avatar_small
aliya said:
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 ||

Avatar_small
aliya said:
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

Avatar_small
shivani09 said:
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. 

Avatar_small
shivani09 said:
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. 

Avatar_small
shivani02 said:
Thu, 20 Apr 2023 14:51:59 +0800

This article is a guest post by the team of Delhi Escort .

 

.

Avatar_small
annusharma said:
Tue, 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.

Avatar_small
shivani02 said:
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.

Avatar_small
Patna Call Girl said:
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

 
Avatar_small
Aliya said:
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 ||

Avatar_small
Aliya said:
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 ||
 


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter