BZOJ-1002: Rotavirus [FJOI2007]

Problem Description: There are many variety to the rotavirus. Some of them follow the structure in the image below(graph 1.1), where there are connections between every node on the circumference with the center and with its neighbour. Specifically, we define the N-sided virus as a virus that for every pairs of nodes on the virus there is only one path to go through. For example, if  = 3, then there are 16 different kinds of N-sides viruses(graph 1.2). For any given N (N ≤ 100), print the number of different ways to form a N-sides virus.

            Graph 1.1                            Graph1.2

#include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <stdio.h> #include <fstream> #include <cmath> #include <stdlib.h> #include <iomanip> #include <algorithm> #include <limits.h> using namespace std; #define FAST_IO ios::sync_with_stdio(false); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<double,double> pdd; typedef long long ll; const int maxn = 1e6 + 10; class BigNum{ public: string str; BigNum(){} BigNum(string s):str(s){} BigNum operator +(BigNum b){ string re = ""; string num_a = str; string num_b = b.str; int add = 0; for(int i = num_a.size() - 1, j = num_b.size() - 1; j >= 0; i--,j--){ int a = num_a[i] - '0'; int b = num_b[j] - '0'; re.push_back((char)((a + b + add) if(a + b + add >= 10) add = 1; else add = 0; } for(int i = num_a.size() - num_b.size() - 1; i >= 0; i--){ int a = num_a[i] - '0'; re.push_back((char)((a + add) if(a + add >= 10) add = 1; else add = 0; } if(add) re.push_back(add + '0'); reverse(re.begin(),re.end()); return BigNum(re); } BigNum operator -(BigNum b){ string re = ""; string num_a = str; string num_b = b.str; bool flag = 1; if(num_a.size() < num_b.size() || (num_a.size() == num_b.size() && num_a < num_b)) {swap(num_a,num_b); flag = 0;} int minus = 0; for(int i = num_a.size() - 1, j = num_b.size() - 1; j >= 0; i--,j--){ int a = num_a[i] - '0'; int b = num_b[j] - '0'; if(a - b - minus < 0){ re.push_back((char)((10 + a - b - minus) minus = 1; } else{ re.push_back((char)((a - b - minus) minus = 0; } } for(int i = num_a.size() - num_b.size() - 1; i >= 0; i--){ int a = num_a[i] - '0'; if(a - minus < 0){ re.push_back((char) ((10 + a - minus) minus = 1; } else{ re.push_back((char)((a - minus) minus = 0; } } while(re[re.size() - 1] == '0') re.erase(re.end() - 1); reverse(re.begin(),re.end()); if(re.empty()) return BigNum(0); return BigNum(re); } BigNum operator *(int mul){ string re = ""; string num_a = str; int add = 0; for(int i = str.size() - 1; i >= 0; i--){ int a = str[i] - '0'; re.push_back((char)((a * mul + add) if((a * mul + add) >= 10) add = (a * mul + add) / 10; else add = 0; } if(add) re.push_back(add + '0'); reverse(re.begin(),re.end()); return BigNum(re); } void output(){ cout<<str<<endl; } }; BigNum ans[105]; int N; int main(){ FAST_IO cin>>N; ans[1] = BigNum("1"); ans[2] = BigNum("5"); for(int i = 3; i <= N; i++) ans[i] = ans[i - 1] * 3 - ans[i - 2] + BigNum("2"); ans[N].output(); return 0; }

 

Leave a Reply

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