bzoj 1002 找規律,高精度

1002: [FJOI2007]輪狀病毒

，問有多少種情況。

tags：看了題解，f[i]=f[i-1]*3-f[i-2]+2。 有基爾霍夫矩陣推的，也有dp推的，還有寫爆搜算出前幾個找規律的，

然而，本弱雞連個爆搜都寫不出來，23333

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,b,a) for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 200;

int n;
struct P { int a[N], len; }f[N];
P sub(P b, P c)
{
    b.a[1]+=2;
    int j=1;
    while(b.a[j]>9) b.a[j+1]+=b.a[j]/10, b.a[j]%=10, j++;
    rep(i,1,b.len) {
        b.a[i]-=c.a[i];
        if(b.a[i]<0) b.a[i]+=10, b.a[i+1]--;
    }
    while(b.len>1 && b.a[b.len]==0) b.len--;
    return b;
}
P mul(P b, int x)
{
    rep(i,1,b.len) b.a[i]*=x;    
    rep(i,1,b.len) {
        //b.a[i]*=x;      //很sb地在這裡卡了個bug
        b.a[i+1]+=b.a[i]/10;
        b.a[i]%=10;
    }
    if(b.a[b.len+1]) b.len++;
    return b;
}
void Init()
{
    f[1].len=f[2].len=1;
    f[1].a[1]=1, f[2].a[1]=5;
    rep(i,3,N-1) f[i]=sub(mul(f[i-1], 3), f[i-2]);
}
int main()
{
    Init();
    scanf("%d", &n);
    per(i,f[n].len,1) printf("%d", f[n].a[i]);
    puts("");

    return 0;
}      

View Code

轉載于:https://www.cnblogs.com/sbfhy/p/6481980.html