1002: [FJOI2007]轮状病毒
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 3106 Solved: 1724
[Submit][Status][Discuss]
Description
给定n(N<=100)，编程计算有多少个不同的n轮状病毒。
Input
第一行有1个正整数n。
Output
将编程计算出的不同的n轮状病毒数输出
Sample Input
3
Sample Output
16
HINT
Source
题解：貌似考的是基尔霍夫矩阵（<-什么破玩意？）
算法引入：
给定一个无向图G，求它生成树的个数t(G);
算法思想：
(1)G的度数矩阵D[G]是一个n*n的矩阵,并且满足:当i≠j时,dij=0;当i=j时,dij等于vi的度数;
(2)G的邻接矩阵A[G]是一个n*n的矩阵,并且满足:如果vi,vj之间有边直接相连,则aij=1,否则为0;
定义图G的Kirchhoff矩阵C[G]为C[G]=D[G]-A[G];
*Matrix-Tree定理:G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值；
所谓n-1阶主子式,就是对于r(1≤r≤n),将C[G]的第r行,第r列同时去掉后得到的新矩阵,用Cr[G]表示;
*Kirchhoff矩阵的特殊性质：
(1)对于任何一个图G,它的Kirchhoff矩阵C的行列式总是0,这是因为C每行每列所有元素的和均为0;
(2)如果G是不连通的,则它的Kirchhoff矩阵C的任一个主子式的行列式均为0;
(3)如果G是一颗树,那么它的Kirchhoff矩阵C的任一个n-1阶主子式的行列式均为1;
扯了这么多，其实这道题根本用不上，只要知道这玩意能推出f[i]=(f[i-1]*3-f[i-2]+2)就行了。注意高精度。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define eps 1e-8
using namespace std;
const int maxn=;
struct bign{
int len,s[maxn];
bign(){memset(s,,sizeof(s));len=;}
bign(int num){*this=num;}
bign(const char *num){*this=num;}
bign operator = (const int num){
char s[maxn]; sprintf(s,"%d",num);
*this = s;return *this;
}
bign operator = (const char *num){
for(int i=;num[i]=='';num++);
len=strlen(num);
for(int i=;i<len;i++) s[i]=num[len-i-]-'';
return *this;
}
bign operator + (const bign &b) const{
bign c;c.len=;
for(int i=,g=;g||i<max(len,b.len);i++) {
int x=g;
if(i<len) x+=s[i];
if(i<b.len) x+=b.s[i];
c.s[c.len++]=x%;
g=x/;
} return c;
}
void clean(){while(len > && !s[len-]) len--;return;}
bign operator * (const bign &b){
bign c;
c.len=len+b.len;
for(int i=;i<len;i++) for(int j=;j<b.len;j++) c.s[i+j]+=s[i]*b.s[j];
for(int i=;i<c.len;i++){
c.s[i+]+=c.s[i]/;
c.s[i]%=;
} c.clean();return c;
}
bign operator - (const bign &b){
bign c;c.len=;
for(int i=,g=;i<len;i++){
int x=s[i]-g;if(i<b.len) x-=b.s[i];
if(x>=) g=;
else g=,x+=;
c.s[c.len++]=x;
} c.clean();return c;
}
bign operator / (const bign &b) {
bign c,f=;
for(int i=len-;i>=;i--){
f=f*;f.s[]=s[i];
while(!(f<b)) f=f-b,c.s[i]++;
} c.len=len;c.clean();return c;
}
bign operator % (const bign &b) {
bign r = *this / b;
r = *this - r*b;
return r;
}
bool operator < (const bign &b) {
if(len!=b.len) return len<b.len;
for(int i=len-;i>=;i--){
if(s[i]!=b.s[i]) return s[i]<b.s[i];
} return false;
}
bool operator > (const bign &b){
if(len!=b.len) return len>b.len;
for(int i=len-;i>=;i--){
if(s[i]!=b.s[i]) return s[i]>b.s[i];
} return false;
}
bool operator == (const bign &b){
return !(*this>b)&&!(*this<b);
}
bool operator >= (const bign &b){
return (*this>b)||(*this==b);
}
void print(){
for(int i=len-;i>=;i--) putchar(s[i]+'');return;
}
}f[maxn];
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int n;
void init(){
n=read();f[]=;f[]=;
return;
}
void work(){
for(int i=;i<=n;i++) f[i]=f[i-]*-f[i-]+;
return;
}
void print(){
f[n].print();
return;
}
int main(){init();work();print();}
然后窝萌来打表好辣~
打表代码生成器：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define eps 1e-8
using namespace std;
const int maxn=;
struct bign{
int len,s[maxn];
bign(){memset(s,,sizeof(s));len=;}
bign(int num){*this=num;}
bign(const char *num){*this=num;}
bign operator = (const int num){
char s[maxn]; sprintf(s,"%d",num);
*this = s;return *this;
}
bign operator = (const char *num){
for(int i=;num[i]=='';num++);
len=strlen(num);
for(int i=;i<len;i++) s[i]=num[len-i-]-'';
return *this;
}
bign operator + (const bign &b) const{
bign c;c.len=;
for(int i=,g=;g||i<max(len,b.len);i++) {
int x=g;
if(i<len) x+=s[i];
if(i<b.len) x+=b.s[i];
c.s[c.len++]=x%;
g=x/;
} return c;
}
void clean(){while(len > && !s[len-]) len--;return;}
bign operator * (const bign &b){
bign c;
c.len=len+b.len;
for(int i=;i<len;i++) for(int j=;j<b.len;j++) c.s[i+j]+=s[i]*b.s[j];
for(int i=;i<c.len;i++){
c.s[i+]+=c.s[i]/;
c.s[i]%=;
} c.clean();return c;
}
bign operator - (const bign &b){
bign c;c.len=;
for(int i=,g=;i<len;i++){
int x=s[i]-g;if(i<b.len) x-=b.s[i];
if(x>=) g=;
else g=,x+=;
c.s[c.len++]=x;
} c.clean();return c;
}
bign operator / (const bign &b) {
bign c,f=;
for(int i=len-;i>=;i--){
f=f*;f.s[]=s[i];
while(!(f<b)) f=f-b,c.s[i]++;
} c.len=len;c.clean();return c;
}
bign operator % (const bign &b) {
bign r = *this / b;
r = *this - r*b;
return r;
}
bool operator < (const bign &b) {
if(len!=b.len) return len<b.len;
for(int i=len-;i>=;i--){
if(s[i]!=b.s[i]) return s[i]<b.s[i];
} return false;
}
bool operator > (const bign &b){
if(len!=b.len) return len>b.len;
for(int i=len-;i>=;i--){
if(s[i]!=b.s[i]) return s[i]>b.s[i];
} return false;
}
bool operator == (const bign &b){
return !(*this>b)&&!(*this<b);
}
bool operator >= (const bign &b){
return (*this>b)||(*this==b);
}
void print(){
for(int i=len-;i>=;i--) putchar(s[i]+'');return;
}
}f[maxn];
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int n;
void init(){
f[]=;f[]=;
return;
}
void work(){
for(int i=;i<=;i++) f[i]=f[i-]*-f[i-]+;
return;
}
void print(){
freopen("dabiao.txt","w",stdout);
puts("if(n==1)puts(\"1\");");
for(int i=;i<=;i++){
printf("else if(n==%d)puts(\"",i);f[i].print();puts("\");");
}
return;
}
int main(){init();work();print();}
打表代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int n;
void init(){
n=read();
if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
else if(n==)puts("");
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}