BZOJ 1002([FJOI2007]輪狀病毒-基爾霍夫矩陣)

1002: [FJOI2007]輪狀病毒
Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 1402  Solved: 758
[Submit][Status][Discuss]
Description
 給定n(N<=100)，編程計算有多少個不同的n輪狀病毒。
Input
第一行有1個正整數n。
Output
將編程計算出的不同的n輪狀病毒數輸出
Sample Input
3

Sample Output
16

HINT

Source

[Submit][Status][Discuss]


  給定n(N<=100)，編程計算有多少個不同的n輪狀病毒

不想吐槽了，kUbuntu各種坑人……

各種卡機子不說，好像Google的詞庫也沒法用。

Codeblock根本進不了Win盤（沒權限估計）

話說看PPT那種換一頁等3s真不是人受的

話說我到底有沒有寫題解啊！（1G內存黨傷不起）

至於基爾霍夫矩陣什麼的我才不知道呢

[cpp]
#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
#include<cmath>  
#include<cctype>  
using namespace std; 
#define For(i,n) for(int i=1;i<=n;i++)  
#define Rep(i,n) for(int i=0;i<n;i++)  
#define Fork(i,k,n) for(int i=k;i<=n;i++)  
#define ForD(i,n) for(int i=n;i;i--)  
#define Forp(x) for(int p=pre[x];p;p=next[p])  
#define RepD(i,n) for(int i=n;i>=0;i--)  
#define MAXN (100+10)  
#define F (10000)  
int n; 
struct Highn 
{ 
    int a[10000],len; 
    Highn(){len=0;memset(a,0,sizeof(a));} 
    Highn(int b) 
    { 
        len=0;memset(a,0,sizeof(a)); 
        while (b) a[++len]=b%F,b/=F; 
        if (len==0) len=1; 
    } 
    friend Highn operator*(int b,Highn a) 
    { 
        For(i,a.len) a.a[i]*=b; 
        For(i,a.len) a.a[i+1]+=a.a[i]/F,a.a[i]%=F; 
        if (a.a[a.len+1]) a.len++; 
        return a; 
    } 
    friend Highn operator+(Highn b,Highn a) 
    { 
        Highn c; 
        c.len=max(a.len,b.len); 
        For(i,c.len) 
        { 
            c.a[i]+=a.a[i]+b.a[i]; 
            c.a[i+1]+=c.a[i]/F; 
            c.a[i]%=F; 
        } 
        c.len++; 
        while (!c.a[c.len]) c.len--; 
        return c; 
    } 
    friend Highn operator-(Highn a,Highn b) 
    { 
        Highn c; 
        c.len=max(a.len,b.len); 
        For(i,c.len) 
        { 
            c.a[i]+=a.a[i]-b.a[i]; 
            if (c.a[i]<0) c.a[i]+=F,c.a[i+1]--; 
        //  c.a[i+1]+=c.a[i]/F;  
        //  c.a[i]%=F;  
        } 
        while (!c.a[c.len]) c.len--; 
        return c; 
    } 
 
    void print() 
    { 
        printf("%d",a[len]); 
        ForD(i,len-1) 
        { 
            printf("%04d",a[i]); 
        } 
        puts(""); 
    } 
}f[MAXN]; 
int main() 
{ 
//  freopen(".in","r",stdin);  
//  freopen(".out","w",stdout);  
    scanf("%d",&n); 
    f[1]=1,f[2]=5; 
    if (n<=2) f[n].print(); 
    else 
    { 
        Fork(i,3,n) f[i]=3*f[i-1]-f[i-2]+2; 
        f[n].print(); 
    } 
 
 
    return 0; 
} 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MAXN (100+10)
#define F (10000)
int n;
struct Highn
{
    int a[10000],len;
    Highn(){len=0;memset(a,0,sizeof(a));}
    Highn(int b)
    {
        len=0;memset(a,0,sizeof(a));
        while (b) a[++len]=b%F,b/=F;
        if (len==0) len=1;
    }
    friend Highn operator*(int b,Highn a)
    {
        For(i,a.len) a.a[i]*=b;
        For(i,a.len) a.a[i+1]+=a.a[i]/F,a.a[i]%=F;
        if (a.a[a.len+1]) a.len++;
        return a;
    }
    friend Highn operator+(Highn b,Highn a)
    {
        Highn c;
        c.len=max(a.len,b.len);
        For(i,c.len)
        {
            c.a[i]+=a.a[i]+b.a[i];
            c.a[i+1]+=c.a[i]/F;
            c.a[i]%=F;
        }
        c.len++;
        while (!c.a[c.len]) c.len--;
        return c;
    }
    friend Highn operator-(Highn a,Highn b)
    {
        Highn c;
        c.len=max(a.len,b.len);
        For(i,c.len)
        {
            c.a[i]+=a.a[i]-b.a[i];
            if (c.a[i]<0) c.a[i]+=F,c.a[i+1]--;
        //  c.a[i+1]+=c.a[i]/F;
        //  c.a[i]%=F;
        }
        while (!c.a[c.len]) c.len--;
        return c;
    }

    void print()
    {
        printf("%d",a[len]);
        ForD(i,len-1)
        {
            printf("%04d",a[i]);
        }
        puts("");
    }
}f[MAXN];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
    scanf("%d",&n);
    f[1]=1,f[2]=5;
    if (n<=2) f[n].print();
    else
    {
        Fork(i,3,n) f[i]=3*f[i-1]-f[i-2]+2;
        f[n].print();
    }

 return 0;
}