这道题第一眼是生成树计数，n是100，是可以用O(n^3)的求基尔霍夫矩阵的n-1阶的子矩阵的行列式求解的，但是题目中并没有说取模之类的话，就不好办了。
用高精度？有分数出现。
用辗转相除的思想，让它不出现分数。但过程中会出现负数，高精度处理负数太麻烦。
用Python打表？好吧，Python还不熟，写不出来。。。。。
所以，如果这道题我考场上遇到，最多用double骗到n<=20的情况的部分分。
最终只能求助于题解了。。。
好像是通过观察行列式的特点，推导出关于答案f(n)的递推式（f(n)=3*f(n-1)-f(n-2)+2）
这道题就这样水过了，收获是：
1、题目可能属于某一类问题，该类问题又有通法可解，但题目一般不能直接套用之，此时就只能观察题目较之一般问题的特殊之处，尝试利用它帮助解题。
2、当1行不通时，可以先用暴力把规模较小的解跑出来，再看看可否推出规律。
回顾一下高精：
#include <cstdio>
#include <cstring>
#include <iostream>
#define M 10
using namespace std; struct Num {
int v[], len;
Num(){}
Num( int n ) {
memset( v, , sizeof(v) );
if( n== ) {
len = ;
return;
}
len = ;
while( n ) {
len++;
v[len] = n%M;
n /= M;
}
}
Num operator+( const Num &b ) const {
Num rt();
rt.len = max( len, b.len ) + ;
for( int i=; i<=rt.len; i++ ) {
rt.v[i] += v[i]+b.v[i];
rt.v[i+] += rt.v[i]/M;
rt.v[i] %= M;
}
while( rt.len> && rt.v[rt.len]== ) rt.len--;
return rt;
}
Num operator-( const Num &b ) const {
Num rt();
rt.len = len;
for( int i=; i<=rt.len; i++ ) {
rt.v[i] += v[i]-b.v[i];
if( rt.v[i]< ) {
rt.v[i]+=M;
rt.v[i+]--;
}
}
while( rt.len> && rt.v[rt.len]== ) rt.len--;
return rt;
}
int count_bit( int b ) const {
int rt = ;
while( b ) {
rt++;
b/=M;
}
return rt;
}
Num operator*( int b ) const {
Num rt();
rt.len = len+count_bit(b)+; // b==3
for( int i=; i<=rt.len; i++ ) {
rt.v[i] += v[i]*b;
rt.v[i+] += rt.v[i]/M;
rt.v[i] %= M;
}
while( rt.len> && rt.v[rt.len]== ) rt.len--;
return rt;
}
void print() {
for( int i=len; i>=; i-- )
printf( "%d", v[i] );
printf( "\n" );
}
}; int n;
Num dp[]; int main() {
scanf( "%d", &n );
dp[] = Num();
dp[] = Num();
for( int i=; i<=n; i++ )
dp[i] = dp[i-]* +Num() - dp[i-];
dp[n].print();
}
——————————————————————————————————————————
去补习了一下python，用python写了一个用辗转相除思想算行列式的算法（感觉python还是挺快的，还有高精度支持）
#!/usr/bin/python from math import * def swap( a, b ):
return b, a
def abs( a ) :
if a<0 :
return -a
else:
return a
def det( a, n ):
for i in range(0,n):
if a[i][i]==0:
return 0
for j in range(i+1,n):
while a[j][i]!=0 :
d = a[i][i]//a[j][i]
for k in range(i,n) :
a[i][k] = a[i][k]-a[j][k]*d
a[j][k],a[i][k] = swap( a[j][k],a[i][k] )
ans = 1
for i in range(0,n):
ans = ans * a[i][i]
return abs(ans) def mod( a, m ):
return (a%m+m)%m def main():
for n in range( 1, 101 ):
if n==1 :
print 1
continue
if n==2 :
print 5
continue i = j = 0
a = [ [ 0 for j in range(n) ] for i in range(n) ]
i = 0
for i in range(0,n):
a[i][i] = 3
a[i][mod(i-1,n)] = -1
a[i][mod(i+1,n)] = -1
print det(a,n)
main()
将文件保存到bzoj1002.py，执行
chmod +x hzoj1002.py
./hzoj1002.py