HDU 2842 중국어 링 밴드 상수 매트릭스 쾌속 멱 + 사고

먼저 사내 블 로그 Orz 를 붙인다.https://blog.csdn.net/hcbbt/article/details/38363611
이 문 제 는 몇 가지 가 매우 교묘 하 다.
1. n 번 째 빼 기: f (n - 2) 를 완성 하고 n 번 째 고 리 를 빼 기;그리고 앞 (n - 2) (사실 이것 도 f (n - 2)) 에 f (n - 1) 를 더 해 주세요.
최종 적 으로 f (n) = f (n - 1) + 2 * f (n - 2) + 1 을 얻 으 면 전달 식 이다.다른: f (1) = 1, f (2) = 2 초기 화
2. 매트릭스 쾌속 멱 에서 상수 가 함 유 된 식 을 만나면 A 행렬 을 3 * 3 의 행렬 로 확장 할 수 있 습 니 다.
즉, 최종 적 으로 다음 식 을 얻 을 수 있 습 니 다.
                          |  f(n)   |     | 1  2  1 |    | f(n-1) |
                          | f(n-1) | =  | 1  0  0 | * | f(n-2) |
                          |    1     |     | 0  0  1 |   |    1     |
중간 에 있 는 것 은 A 행렬 이 고 그 다음 에 행렬 의 빠 른 속도 의 판 자 를 사용 하면 됩 니 다.AC 코드 첨부:

#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define pi acos(-1.0)

const int MOD=200907;
ll n;
typedef struct
{
    ll a[3][3];//    
}mat;
mat c,res;

mat mul(mat x,mat y,int n)
{
    mat cnt;
    memset(cnt.a,0,sizeof(cnt.a));
    for(int i=0;i0)
    {
        if(n&1)
            res=mul(res,c,3);
        c=mul(c,c,3);
        n=(n>>1);
    }
}
int main()
{
    while(cin>>n)
    {
        if(n==0)
            break;
        else if(n==1)
            cout<