題目描述
輪狀病毒有很多變種。許多輪狀病毒都是由一個輪狀基産生。一個n輪狀基由圓環上n個不同的基原子和圓心的一個核原子構成。2個原子之間的邊表示這2個原子之間的資訊通道,如圖1。
n輪狀病毒的産生規律是在n輪狀基中删除若幹邊,使各原子之間有唯一一條資訊通道。例如,共有16個不同的3輪狀病毒,入圖2所示。
給定n(N<=100),程式設計計算有多少個不同的n輪狀病毒。
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIn5GcuEzYyQjY3EWOjZGNlhDOlRWZ2MGMycjMhVDMmNWZllDNfdWbp9CXt92Yu4GZjlGbh5SZslmZxl3Lc9CX6MHc0RHaiojIsJye.png)
輸入輸出格式
輸入格式:
第一行有1個正整數n。
輸出格式:
将程式設計計算出的不同的n輪狀病毒數輸出
輸入輸出樣例
輸入樣例#1:
3
輸出樣例#1:
16
吐槽
今天(應該是昨天了)我的ubuntu感染wncry(想哭)2.0(慘痛經曆),重裝了快一整個前半夜的系統,我感到極端的不爽,于是想把這道WC2017時就想a掉但一直擱置的題切了,發洩心中的郁悶。
解題思路
%%%伏特跳蚤國王VFK大佬的部落格
http://vfleaking.blog.163.com/blog/static/17480763420119685112649/答案是求一個行列式的值,經過一大長串的公式推導化簡(留坑),得到一個遞推式——f[1]=1,f[2]=5,f[n+2]=f[n+1]*3-f[n]+2,n>=1(或者f[n]=f[n-1]*3-f[n-2]+2,n>=3),于是開始敲吧。
源代碼
一開始我寫了個__in128版本的
#include<bits/stdc++.h>
using namespace std;
int n;
__int128 a,b,c;
void print(__int128 x)
{
if (x==0) return;
if (x) print(x/10);
putchar(x%10+'0');
}
int main()
{
a=1,b=5;
cin>>n;
if(n==1)
{
printf("1\n");
return 0;
}
if(n==2)
{
printf("5\n");
return 0;
}
n-=2;
while(n--)
{
c=b*3-a+2;
a=b;
b=c;
}
print(c);
printf("\n");
return 0;
}
得了90分(
評測記錄)。第二個n=99的點wa了,n=99時__int128都爆了,但由于不想寫高精,換成了unsigned __int128,照wa不誤(
)
而且BZOJ還不支援C++11,于是隻得寫高精了
#include<bits/stdc++.h>
using namespace std;
int n;
int a[50],b[50],c[50];
void print(int * c)
{
int i=49;
while(c[i]==0) i--;
while(i>=0) printf("%d",c[i--]);
}
int main()
{
a[0]=1,b[0]=5;
scanf("%d",&n);
if(n==1)
{
printf("1\n");
return 0;
}
if(n==2)
{
printf("5\n");
return 0;
}
for(int k=3;k<=n;k++)
{
int len=49;
while(b[len]==0) len--;
for(int i=0;i<=len;i++)
{
c[i]=b[i]*3-a[i];
}
c[0]+=2;
for(int i=0;i<50;i++)
{
if(c[i]>9)
{
c[i+1]+=c[i]/10;
c[i]%=10;
}
if(c[i]<0)
{
while(c[i]<0)
c[i]+=10,c[i+1]--;
}
}
for(int i=0;i<50;i++)
{
a[i]=b[i],b[i]=c[i];
}
}
print(c);
printf("\n");
return 0;
}
想想也有幾個月沒寫過高精了,這麼基礎的姿勢居然都忘的差不多了,我硬是調了快1個小時……在刷裸題學習新算法的時候還是不能忘記基礎啊,還要多做點綜合性的題目才行啊!