生成树的计数(基尔霍夫矩阵)：BZOJ 1002 [FJOI2007]轮状病毒
2024-10-06 11:30:47
1002: [FJOI2007]轮状病毒
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 3928 Solved: 2154
[Submit][Status][Discuss]
Description
轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子
和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示
.png)
N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不
同的3轮状病毒，如下图所示
.png)
现给定n(N<=100)，编程计算有多少个不同的n轮状病毒
Input
第一行有1个正整数n
Output
计算出的不同的n轮状病毒数输出
Sample Input
3
Sample Output
16
纯属娱乐~~~
#ifndef EXTINT_H
#define EXTINT_H #include <cctype>
#include <string>
#include <istream>
#include <ostream>
#include <cassert>
#include <iomanip>
#include <iostream> class ExtInt{
friend ExtInt operator +(const ExtInt &a, const ExtInt &b);
friend ExtInt operator -(const ExtInt &a, const ExtInt &b);
friend ExtInt operator *(const ExtInt &a, const ExtInt &b);
friend ExtInt operator /(const ExtInt &a, const ExtInt &b);
friend ExtInt operator %(const ExtInt &a, const ExtInt &b);
friend bool operator <(const ExtInt &a, const ExtInt &b);
friend bool operator >(const ExtInt &a, const ExtInt &b);
friend bool operator <=(const ExtInt &a, const ExtInt &b);
friend bool operator >=(const ExtInt &a, const ExtInt &b);
friend bool operator ==(const ExtInt &a, const ExtInt &b);
friend bool operator !=(const ExtInt &a, const ExtInt &b);
friend std::istream & operator >>(std::istream &inputStream, ExtInt &data);
friend std::ostream & operator <<(std::ostream &outputStream, const ExtInt &data);
private:
static const int LIMIT = ;
static const int WIDTH = ;
int length;
bool isNegative;
struct DListNode{
int data;
DListNode *forward, *next;
DListNode(int data = ) : data(data), forward(NULL), next(NULL) {}
DListNode & remove();
DListNode & append(DListNode *data);
DListNode & append(const int &data);
DListNode & insert(DListNode *data);
DListNode & insert(const int &data);
}*low, *high;
public:
ExtInt(int data = );
ExtInt(const ExtInt &rhs);
ExtInt(const std::string &rhs);
virtual ~ExtInt(); ExtInt & operator =(const ExtInt &rhs);
ExtInt & operator +=(const ExtInt &rhs);
ExtInt & operator -=(const ExtInt &rhs);
ExtInt & operator *=(const ExtInt &rhs);
ExtInt & operator /=(const ExtInt &rhs);
ExtInt & operator %=(const ExtInt &rhs);
//ExtInt & operator ++();
//ExtInt & operator ++(int);
//ExtInt & operator --();
//ExtInt & operator --(int);
}; #endif ExtInt::DListNode & ExtInt::DListNode::remove() {
DListNode *tmp = this -> forward;
tmp -> forward -> next = this;
this -> forward = tmp -> forward;
delete tmp;
return *this;
}
ExtInt::DListNode & ExtInt::DListNode::append(DListNode *data) {
data -> next = this -> next;
data -> forward = this;
if (this -> next != NULL) {
this -> next -> forward = data;
}
this -> next = data;
return *this;
}
ExtInt::DListNode & ExtInt::DListNode::append(const int &data) {
return append(new DListNode(data));
}
ExtInt::DListNode & ExtInt::DListNode::insert(DListNode *data) {
data -> next = this;
data -> forward = this -> forward;
if (this -> forward != NULL) {
this -> forward -> next = data;
}
this -> forward = data;
return *this;
}
ExtInt::DListNode & ExtInt::DListNode::insert(const int &data) {
return insert(new DListNode(data));
} ExtInt::ExtInt(int data) {
low = new DListNode;
high = new DListNode;
low -> append(high);
length = ;
isNegative = false;
if (data < ) {
isNegative = true;
data = -data;
}
while (data >= ExtInt::LIMIT) {
high -> insert(data % ExtInt::LIMIT);
data /= ExtInt::LIMIT;
length++;
}
if (length == || data > ) {
high -> insert(data);
length++;
}
}
ExtInt::ExtInt(const ExtInt &rhs) {
low = new DListNode;
high = new DListNode;
low -> append(high);
length = ;
isNegative = rhs.isNegative;
for (DListNode *it = rhs.low -> next; it != rhs.high; it = it -> next) {
high -> insert(it -> data);
length++;
}
}
ExtInt::ExtInt(const std::string &rhs) {
low = new DListNode;
high = new DListNode;
low -> append(high);
length = ;
isNegative = false;
if (rhs[] == '-') {
isNegative = true;
}
for (int i = rhs.length() - ; i >= ; i -= WIDTH) {
int value = ;
for (int j = std::max(, i - WIDTH + ); j <= i; j++) {
if (j == && isNegative) continue;
assert(isdigit(rhs[j]));
value = value * + rhs[j] - '';
}
high -> insert(value);
length++;
}
while (length > && high -> forward -> data == ) {
high -> remove();
length--;
}
}
ExtInt & ExtInt::operator =(const ExtInt &rhs) {
if (this == &rhs) return *this;
if (low != NULL || high != NULL) {
this -> ~ExtInt();
}
low = new DListNode;
high = new DListNode;
low -> append(high);
length = ;
isNegative = rhs.isNegative;
for (DListNode *it = rhs.low -> next; it != rhs.high; it = it -> next) {
high -> insert(it -> data);
length++;
}
return *this;
}
ExtInt::~ExtInt() {
for (DListNode *it = low; it != NULL;) {
DListNode *tmp = it -> next;
delete it;
it = tmp;
}
} std::istream & operator >>(std::istream &inputStream, ExtInt &data) {
std::string tmp;
inputStream >> tmp;
data = ExtInt(tmp);
return inputStream;
}
std::ostream & operator <<(std::ostream &outputStream, const ExtInt &data) {
if (data.isNegative) {
outputStream << "-";
}
ExtInt::DListNode *it = data.high -> forward;
outputStream << it -> data;
for (it = it -> forward; it != data.low; it = it -> forward) {
outputStream << std::setfill('') << std::setw(ExtInt::WIDTH) << it -> data;
}
return outputStream;
} bool operator <(const ExtInt &a, const ExtInt &b) {
if (a.isNegative && !b.isNegative) return true;
if (!a.isNegative && b.isNegative) return false;
bool flag = false;
if (a.isNegative && b.isNegative) flag = true;
if (a.length < b.length) return flag ^ true;
if (a.length > b.length) return flag ^ false;
ExtInt::DListNode *itA = a.high, *itB = b.high;
for (; itA != a.low && itB != b.low; itA = itA -> forward, itB = itB -> forward) {
if (itA -> data < itB -> data) return flag ^ true;
if (itA -> data > itB -> data) return flag ^ false;
}
return false;
}
bool operator >(const ExtInt &a, const ExtInt &b) {
if (a.isNegative && !b.isNegative) return false;
if (!a.isNegative && b.isNegative) return true;
bool flag = false;
if (a.isNegative && b.isNegative) flag = true;
if (a.length < b.length) return flag ^ false;
if (a.length > b.length) return flag ^ true;
ExtInt::DListNode *itA = a.high, *itB = b.high;
for (; itA != a.low && itB != b.low; itA = itA -> forward, itB = itB -> forward) {
if (itA -> data < itB -> data) return flag ^ false;
if (itA -> data > itB -> data) return flag ^ true;
}
return false;
}
bool operator >=(const ExtInt &a, const ExtInt &b) {
return !(a < b);
}
bool operator <=(const ExtInt &a, const ExtInt &b) {
return !(a > b);
}
bool operator ==(const ExtInt &a, const ExtInt &b) {
if (a.isNegative != b.isNegative) return false;
if (a.length != b.length) return false;
ExtInt::DListNode *itA = a.low, *itB = b.low;
for (; itA != a.high && itB != b.high; itA = itA -> next, itB = itB -> next) {
if (itA -> data != itB -> data) return false;
}
return true;
}
bool operator !=(const ExtInt &a, const ExtInt &b) {
return !(a == b);
} ExtInt operator +(const ExtInt &a, const ExtInt &b) {
if (b.isNegative) {
ExtInt tmp = b;
tmp.isNegative = false;
return a - tmp;
}
if (a.isNegative) {
ExtInt tmp = a;
tmp.isNegative = false;
return b - tmp;
}
ExtInt ret = a;
ExtInt::DListNode *itA = ret.low -> next, *itB = b.low -> next;
for (; itB != b.high; itA = itA -> next, itB = itB -> next) {
if (itA == ret.high) {
itA -> insert();
ret.length++;
itA = itA -> forward;
}
itA -> data += itB -> data;
if (itA -> data >= ExtInt::LIMIT) {
if (itA -> next == ret.high) {
itA -> append();
ret.length++;
}
itA -> next -> data += itA -> data / ExtInt::LIMIT;
itA -> data %= ExtInt::LIMIT;
}
}
return ret;
}
ExtInt operator -(const ExtInt &a, const ExtInt &b) {
if (b.isNegative) {
ExtInt tmp = b;
tmp.isNegative = false;
return a + tmp;
}
if (a.isNegative) {
ExtInt tmp = a;
tmp.isNegative = false;
tmp = tmp + b;
tmp.isNegative = true;
return tmp;
}
if (a < b) {
ExtInt tmp = b - a;
tmp.isNegative = true;
return tmp;
}
ExtInt ret = a;
ExtInt::DListNode *itA = ret.low -> next, *itB = b.low -> next;
for (; itA != ret.high && itB != b.high; itA = itA -> next, itB = itB -> next) {
itA -> data -= itB -> data;
if (itA -> data < ) {
itA -> data += ExtInt::LIMIT;
itA -> next -> data--;
}
}
for (; itA != ret.high; itA = itA -> next) {
if (itA -> data < ) {
itA -> data += ExtInt::LIMIT;
itA -> next -> data--;
}
}
while (ret.length > && ret.high -> forward -> data == ) {
ret.high -> remove();
ret.length--;
}
return ret;
}
ExtInt operator *(const ExtInt &a, const ExtInt &b) {
if (a == ExtInt() || b == ExtInt()) return ExtInt();
ExtInt ret, tmp;
ExtInt::DListNode *itB = b.low -> next;
for (int value = ; itB != b.high; itB = itB -> next, value++) {
if (itB -> data == ) {
continue;
}
tmp = a;
ExtInt::DListNode *itA = tmp.low -> next;
for (long long r = ; itA != tmp.high; itA = itA -> next) {
long long now = 1ll * itA -> data * itB -> data + r;
itA -> data = now % ExtInt::LIMIT;
r = ;
if (now >= ExtInt::LIMIT) {
if (itA -> next == tmp.high) {
itA -> append();
tmp.length++;
}
r = now / ExtInt::LIMIT;
}
}
for (int i = ; i <= value; i++) {
tmp.low -> append();
tmp.length++;
}
//std::cerr << ret << std::endl;
//std::cerr << tmp << std::endl;
//std::cerr << tmp.length << std::endl;
ret = ret + tmp;
}
ret.isNegative = a.isNegative ^ b.isNegative;
return ret;
}
ExtInt operator /(const ExtInt &a, const ExtInt &b) {
assert(b != ExtInt());
if (a == ExtInt()) return ExtInt();
ExtInt ret, tmp, div = b;
ret.high -> remove();
ret.length = ;
tmp.high -> remove();
tmp.length = ;
div.isNegative = false;
ExtInt::DListNode *itA = a.high -> forward;
for (; itA != a.low; itA = itA -> forward) {
tmp.low -> append(itA -> data);
tmp.length++;
if (tmp >= div) {
int left = , right = ExtInt::LIMIT - ;
while (left < right) {
int middle = (left + right >> ) + ;
if (tmp >= div * middle) {
left = middle;
} else {
right = middle - ;
}
}
//std::cerr << tmp << " " << div * left << std::endl;
ret.low -> append(left);
ret.length++;
tmp = tmp - div * left;
} else {
ret.low -> append();
ret.length++;
}
if (tmp == ExtInt()) {
tmp.high -> remove();
tmp.length = ;
}
}
while (ret.length > && ret.high -> forward -> data == ) {
ret.high -> remove();
ret.length--;
}
ret.isNegative = a.isNegative ^ b.isNegative;
if (ret.isNegative && tmp.low -> next != tmp.high) {
ret = ret - ;
}
return ret;
}
ExtInt operator %(const ExtInt &a, const ExtInt &b) {
return a - a / b * b;
} ExtInt & ExtInt::operator +=(const ExtInt &rhs) {
*this = *this + rhs;
return *this;
}
ExtInt & ExtInt::operator -=(const ExtInt &rhs) {
*this = *this - rhs;
return *this;
}
ExtInt & ExtInt::operator *=(const ExtInt &rhs) {
*this = *this * rhs;
return *this;
}
ExtInt & ExtInt::operator /=(const ExtInt &rhs) {
*this = *this / rhs;
return *this;
}
ExtInt & ExtInt::operator %=(const ExtInt &rhs) {
*this = *this % rhs;
return *this;
}
#include <iostream>
#include <cstdio>
using namespace std;
int n;
const int maxn=;
ExtInt C[maxn][maxn];
void abs(ExtInt &x){
if(x<)x=x*(-);
}
void Solve(){
for(int i=;i<n;i++){
for(int j=i+;j<n;j++)
while(C[j][i]!=){
ExtInt r=C[i][i]/C[j][i];
for(int k=i;k<n;k++)
C[i][k]-=C[j][k]*r;
swap(C[i],C[j]);
}
}
ExtInt ans=;
for(int i=;i<n;i++)
ans*=C[i][i];
abs(ans);
cout<<ans<<endl;
return;
}
int main(){
scanf("%d",&n);n++;
if(n!=)
for(int i=;i<n;i++){
C[i][i%(n-)+]-=;
C[i%(n-)+][i]-=;C[i][i]+=;
C[i%(n-)+][i%(n-)+]+=;
}
for(int i=;i<n;i++){
C[i][n]=-;
C[n][i]=-;
C[i][i]+=;
C[n][n]+=;
}
Solve();
return ;
}
最新文章
- apt-get update更新源时，出现“Hash Sum mismatch”问题
- 【转载】Ubuntu 系列安装 Docker
- h-ui前端框架
- 解决连接MySql速度慢的方法
- Machine Learning for hackers读书笔记(十二)模型比较
- 开发一个iOS应用没有那么容易
- Windows server2008/2012 安装oracle 11 创建实例HANG住在百分之2
- java中setDate(Date date)方法和String与Date之间的转换
- operator模块
- Farpoint Spread 常用事件
- 解决使用web开发手机网页关于分辨率被缩放的坑
- centos7 更新Firefox版本
- 操作系统中 heap 和 stack 的区别
- 如何简单快速的修改Bootstrap
- 如何花样展示自己的摄影作品？强大的WebGL能力展示
- Python异常处理回顾与总结
- SQL数据缓存依赖总结
- Markdown学习（一）
- C语言文本处理
- Django配置celery执行异步任务和定时任务