codeforce 185 A——Plant

古城微笑少年丶 2022-07-27 14:49 150阅读 0赞

题意：给定一个大三角形，然后每次按照图片分割成4个小三角形，问n次后有多少个向上的三角形。

思路：矩阵快速幂，可以发现，每一个向上的的可以在下一次产生3个向上的，1个向下的，向下的每次可以产生一个向上的和三个向下的。这刚好是矩阵的应用。注意0的情况。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const ll mod=1e9+7;
    
    struct node
    {
        ll v[5];
        node (){v[1]=3;v[2]=1;v[3]=1;v[4]=3;}
        node mul(node t)
        {
            node p;
            p.v[1]=(v[1]*t.v[1]+v[2]*t.v[3])%mod;
            p.v[2]=(v[1]*t.v[2]+v[2]*t.v[4])%mod;
            p.v[3]=(v[3]*t.v[1]+v[4]*t.v[3])%mod;
            p.v[4]=(v[3]*t.v[2]+v[4]*t.v[4])%mod;
            return p;
        }
        void print()
        {
            cout<<v[1]<<" "<<v[2]<<endl;
            cout<<v[3]<<" "<<v[4]<<endl;
        }
    };
    
    node mi(node k,ll n)
    {
        if (n==1) return k;
        node t=mi(k,n/2);
        //t.print();
        t=t.mul(t);// t.print();
        if (n%2==1) t=t.mul(k);
        return t;
    }
    
    int main()
    {
        ll n;
        cin>>n;
        if (n==0) {puts("1");return 0;}
        node t;
        t=mi(t,n);
        cout<<t.v[1]%mod<<endl;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，150人围观）

还没有评论，来说两句吧...

相关阅读

相关 185.数据库复制-备份

use master go if exists (select from dbo.sysobjects where id = object_

- 日理万妓/ 2024年01月20日 07:01/ 0 赞/ 2 阅读

相关个人作业——A001-185-2513-吴光华

课程名称软件建模与分析班级 18级软件工程5班实验名称我对需求分析与建模的认识与应有建议教导教师董瑞生姓名吴光华学号 1814080902513 组号

爱被打了一巴掌/ 2023年01月01日 07:56/ 0 赞/ 122 阅读

相关个人作业——A002-185-2513-吴光华

软件建模与分析专题报告课程名称需求分析与建模班级 18软件工程5班实验名称专题报告教导教师董瑞生姓名吴光华学号 1814080902513 日期

浅浅的花香味﹌/ 2023年01月01日 07:56/ 0 赞/ 91 阅读

相关 185-将罗马数字转成整数

题目如下：罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。字符数值 I 1 V 5 X 10 L 50 C 100 D

朱雀/ 2022年10月29日 11:27/ 0 赞/ 177 阅读

相关 185.简单的css3页面过渡

效果 (源码网盘地址在最后) ![f66a590430f95a6bafa4ae3093c1b7be.gif][] 源码 index.html <!DOC

朱雀/ 2022年08月29日 05:45/ 0 赞/ 179 阅读

相关 codeforce 185 A——Plant

题意：给定一个大三角形，然后每次按照图片分割成4个小三角形，问n次后有多少个向上的三角形。思路：矩阵快速幂，可以发现，每一个向上的的可以在下一次产生3个向上的，1

古城微笑少年丶/ 2022年07月27日 14:49/ 0 赞/ 151 阅读

相关【leetcode Database】185. Department Top Three Salaries

题目： The `Employee` table holds all employees. Every employee has an Id, and there is al

梦里梦外;/ 2022年07月19日 01:52/ 0 赞/ 131 阅读

相关 Codeforces

Checking the Calendar You are given names of two days of the week. Please, determine w

电玩女神/ 2022年07月16日 06:16/ 0 赞/ 193 阅读

相关 CodeForces 185A Plant（公式推导+快速幂）

Dwarfs have planted a very interesting plant, which is a triangle directed "upwards". Th

柔光的暖阳◎/ 2022年06月03日 10:58/ 0 赞/ 184 阅读

相关 Codeforces 185B（玄学）

B. Mushroom Scientists time limit per test 2 seconds memory limit per test 256 megab

男娘i/ 2022年06月03日 10:56/ 0 赞/ 339 阅读