BZOJ1002 [FJOI2007]轮状病毒 【基尔霍夫矩阵和MT定理】
首先，恶补了行列式的东西。然后，感谢VFleaKing的帮助，让我理解了这个递推式。
我不知道我的原来的题解坑了多少人……算了不看了，重新来一发。
首先，参照周冬的论文《生成树的计数》，自行理解基尔霍夫矩阵和MatrixTree定理，论文讲了很清楚了。
$基尔霍夫矩阵A=无向图的度数矩阵B-无向图的邻接矩阵C$
$MatrixTree$定理：把基尔霍夫矩阵删去第$r$行第$r$列后，矩阵的行列式的绝对值就是生成树的个数
首先，本题很明显求生成树的个数。
矩阵是这样的（借用VFK的矩阵）（3轮状基）
3 -1 0 0 0 ... 0 0 0 -1
-1 3 -1 0 0 ... 0 0 0 0
0 -1 3 -1 0 ... 0 0 0 0
0 0 -1 3 -1 ... 0 0 0 0
0 0 0 -1 3 ... 0 0 0 0
... ... ... ... ... ... ... ...
0 0 0 0 0 ... 3 -1 0 0
0 0 0 0 0 ... -1 3 -1 0
0 0 0 0 0 ... 0 -1 3 -1
-1 0 0 0 0 ... 0 0 -1 3
对的就是这个矩阵，叫基尔霍夫矩阵。
上面这个设为矩阵A，然后我们再看一个矩阵B：
-1 3 -1 0 0 ... 0 0 0 0
0 -1 3 -1 0 ... 0 0 0 0
0 0 -1 3 -1 ... 0 0 0 0
0 0 0 -1 3 ... 0 0 0 0
... ... ... ... ... ... ... ...
0 0 0 0 0 ... 3 -1 0 0
0 0 0 0 0 ... -1 3 -1 0
0 0 0 0 0 ... 0 -1 3 -1
-1 0 0 0 0 ... 0 0 -1 3
3 -1 0 0 0 ... 0 0 0 -1
这个矩阵是A矩阵经过$n-1$次变换得到的，所以$A=(-1)^{n-1} \times B$。
我们观察矩阵B，发现左下面三个数很讨厌，如果消掉就是个上三角矩阵了，行列式就是对角线的乘积了。
倒数第二行，用第一行乘$-1$来消去第一个数，变成了
0 -3 1 0 0 ... 0 0 -1 3
再来，用第二行乘$-3$消去第二个数，变成了
0 0 -8 3 0 ... 0 0 -1 3
现在我们看出了点什么，把这个一般化，设正在处理的这一行的第$k$个和第$k+1$个是$F(k)$和$G(k)$，总能找到上面的一行，来乘以$F(k)$消去$F(k)$，这时候，根据假设，应该是$F(k+1)$和$G(k+1)$，那么我们根据这个可以得到2个等式：$F(k+1)=G(k)+3F(k), G(k+1)=-F(k)$，化简后$F(k+1)=3F(k)-F(k-1)$。
经过漫长的消东西，把倒数第二行变成了：
0 0 0 0 0 ... 0 0 F(n-1)-1 G(n-1)+3
这是一个很好的结果啦，马上就上三角矩阵啦！
设$f=F(n-1)-1,g=G(n-1)+3$，那么就变成了：
0 0 0 0 0 ... 0 0 f g
我们看下倒数第一行，其实是一样的，我们就一直推就好了，设$H(k),I(k)$。
其实和$F,G$的递推式一样的。
其中H(1)=3,H(2)=8.
最后变成了：
0 0 0 0 0 ... 0 0 H(n-1) I(n-1)-1
设$h=H(n-1),i=I(n-1)-1$，那么就变成了
0 0 0 0 0 ... 0 0 h i
变成了一个差一点就完美的东西，消去$h$后，容易得到
$A=-f\times i+g+h$
将$f,g,h,i$的值代入，详细见VFK的博客。
$A=H(n)+F(n-1)-2$。
设递推公式$R(n)$，则$R(n)=3R(n-1)-R(n-2)+2$。
感谢VFK：
#include<bits/stdc++.h>
using namespace std;
struct bn {
int len;
int k[110];
}f[101];
// f(i)=3f(i-1)-f(i-2)+2
bn mul(bn a) {
bn ans;
memset(ans.k,0,sizeof(ans.k));
ans.len=a.len;
for (int i=1;i<=a.len;++i) {
ans.k[i]+=a.k[i]*3;
if (ans.k[i]>=10) {
ans.k[i+1]+=ans.k[i]/10;
ans.k[i]%=10;
}
}
if (ans.k[ans.len+1]>0) ans.len++;
return ans;
}
bn addtwo(bn a) {
bn ans;
ans.len=a.len;
memset(ans.k,0,sizeof(ans.k));
for (int i=1;i<=ans.len;++i)
ans.k[i]=a.k[i];
ans.k[1]+=2;
int ka=1;
while(ans.k[ka]>=10) {
ans.k[ka+1]+=ans.k[ka]/10;
ans.k[ka++]%=10;
}
if (ka>ans.len) ans.len=ka;
return ans;
}
bn xminus(bn a, bn b) {
bn ans;
ans.len=a.len;
memset(ans.k,0,sizeof(ans.k));
for (int i=1;i<=a.len;++i) {
ans.k[i]+=a.k[i]-b.k[i];
if (ans.k[i] < 0) {
ans.k[i]+=10;
ans.k[i+1]--;
}
}
while(ans.k[ans.len]==0) ans.len--;
return ans;
}
int main() {
int n; scanf("%d",&n);
//for (int i=1;i<=n;++i) memset(f[i].k,0,sizeof(f[i].k));
f[1].k[1]=1;f[2].k[1]=5;f[1].len=1;f[2].len=1;
//bn ans=xminus(mul(f[2]),f[1]);
//for (int i=ans.len;i>=1;--i) printf("%d",ans.k[i]);
for (int i=3;i<=n;++i) f[i]=addtwo(xminus(mul(f[i-1]),f[i-2]));
//f[n]=mul(f[2]);
for (int i=f[n].len;i>=1;--i) printf("%d",f[n].k[i]);
return 0;
}
2023年4月27日 15:34
Hindi Model Question Papers Bihar School 10th Exam Board BSEB, Bihar Board 10th Class Model Papers 2023 Matric Exam Pattern, BSEB Patna Board Matric 10th Model Papers 2023 Sample Questions, Bihar Board 10th Model Papers 2023 Download, हिंदीप्रश्नपत्र.com BSEB Matric Bihar matric model paper 2023 bseb 10th sample paper 2023, bihar board 10th model paper 2023 pdf, bihar board 10th class model test paper 2023, bseb matric previous sample paper class 10th bihar board model question paper, bseb matric model question paper 2023.
2024年1月10日 13:28
The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.