当前位置：首页 > news >正文

2019 ICPC Greater New York Region J - Unicycles （规律+递推+矩阵快速幂）

news 来源：原创 2024/5/10 13:51:23

题目链接

题目大意

给出如图所示那种正 $n$ 边形然后在中心添加一个点构成，现在需要找到一种 $u n i c y c l e$ ，定义为第 $n$ 个图的生成树再连接一条边，问 $n$ 边形有多少种 $u n i c y c l e$ ?

解题思路

比赛时没推到规律，空间想象力不强真的没有一点办法，先看题解怎么说吧：
在这里插入图片描述
最难的地方在 $M (i)$ 的基础上添加一个点推 $M (i + 1)$ ，一旦推出公式，我们得到：

$M (n) = 1, 3, 8, 21 . . .$

而斐波那契数列为：

$F (n) = 1, 1, 2, 3, 5, 8, 13, 21, 34 . . .$

不难发现对于 $M (i)$ ，刚好对应斐波那契数列的 $F (2 * i)$ ，而如果对 $M (n)$ 求和得到前缀和 $S (n)$ 为： $1, 4, 12, 33, . . .$
我们不难发现对于每个 $S (i)$ ，对于斐波那契数列的 $F (2 * i + 1) - 1$ ，那么对于上面的第 $n$ 个图， $ans={ 1,M(1),M(2),...M(n-1) }$ ，而 $S (n - 1) = F (2 * (n - 1) + 1) - 1$ ，最后再加上 $1$ ，那么最终的答案就是 $n * F (2 * n - 1)$ ，使用矩阵加速求解即可

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=100007;
const int maxn=2e5+10;
struct Matrix{
    ll matrix[105][105];
};
int n;

Matrix mul(Matrix a,Matrix b){
    Matrix res;
    memset(res.matrix,0,sizeof res.matrix);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++){
        res.matrix[i][j]=(res.matrix[i][j]+(a.matrix[i][k]*b.matrix[k][j])%Mod)%Mod;
    }
    return res;
}

Matrix quick_pow(Matrix mx,ll x){
    Matrix ans;
    memset(ans.matrix,0,sizeof ans.matrix);
    for(int i=1;i<=n;i++) ans.matrix[i][i]=1;
    while(x){
        if(x&1) ans=mul(ans,mx);
        mx=mul(mx,mx);
        x>>=1;
    }
    return ans;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int q;
    Matrix m; n=2;
    m.matrix[1][1]=1,m.matrix[1][2]=1;
    m.matrix[2][1]=1,m.matrix[2][2]=0;
    cin>>q;
    m=quick_pow(m,2*q-1);
    ll ans=m.matrix[2][1];
    cout<<(ans*q)%Mod<<endl;
    return 0;
}