专栏首页ACM小冰成长之路有4种颜色,填入5个组成环的块中

有4种颜色,填入5个组成环的块中

描述

##题解 这个题按题意应该是不用考虑置换群的,一道数论题。

首先我们考虑不是环的情况,也就是说 AAA 和 EEE 断开的情况下,AAA 可以填入 nnn 种颜色,然后剩下的 m−1m - 1m−1 个都只能填入 n−1n - 1n−1 种,所以总情况数为 n∗(n−1)m−1n * (n - 1)^{m - 1}n∗(n−1)m−1。

这时我们来考虑环的情况,环的情况的话在链的基础上需要考虑首尾是否相同,设首尾相同的情况数为 A(m)A(m)A(m),不同的情况数为 B(m)B(m)B(m),设所有情况为 C(m)C(m)C(m),已知 C(m)=A(m)+B(m)=n∗(n−1)m−1C(m) = A(m) + B(m) = n * (n - 1)^{m - 1}C(m)=A(m)+B(m)=n∗(n−1)m−1。另外当首尾相同时,我们可以将首尾看做同一块,那么 A(m)=B(m−1)A(m) = B(m - 1)A(m)=B(m−1),所以 C(m)=B(m−1)+B(m)C(m) = B(m - 1) + B(m)C(m)=B(m−1)+B(m),继而可得 B(m)=C(m)−B(m−1)=n∗(n−1)m−1−B(m−1)B(m) = C(m) - B(m - 1) = n * (n - 1)^{m - 1} - B(m - 1)B(m)=C(m)−B(m−1)=n∗(n−1)m−1−B(m−1)。

于是可以递归求解该题。

当然,这个题还可以用 dfsdfsdfs 来解。

##代码

#include <iostream>
#include <cmath>

using namespace std;

int n, m;

long long B(int m)
{
    if (m == 1)
    {
        return 0;
    }
    long long t = n * pow(n - 1, m - 1);
    return t - B(m - 1);
}

long long solve(int n, int m)
{
    if (m == 1)
    {
        return n;
    }
    else
    {
        return B(m);
    }
}

int main()
{
    n = 4;
    m = 5;
    
    cout << solve(4, 5) << '\n';
    
    return 0;
}

最后答案为:240240240。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一篇文章教会你使用HTML打造一款颜色配对游戏

    createjs是一个基于canvas的制作H5游戏、动画、交互的库。包括EaselJs、TweenJs、SoundJs、 PreloadJs四个部分。它基于...

    前端皮皮
  • #18 turtle模块

    这一节继续记录模块,本节将记录Python中一个非常重要的画图模块——turtle,Here we go!

    py3study
  • 前端 + AI —— 走进无码时代

    导语:前端智能化,就是通过AI/CV技术,使前端工具链具备理解能力,进而辅助开发提升研发效率,比如实现基于设计稿智能布局和组件智能识别等。

    Y.one
  • 科研绘图系列:(3)使用PPT绘制免疫系统细胞(二维)

    我们大致可以将细胞分为4类: 第一类,比较规律的椭圆或者圆形的细胞,T细胞和B细胞 第二类,细胞外形近似椭圆但是同时细胞核非椭圆的细胞,例如巨噬细胞,中性粒...

    用户1359560
  • python3 pygame简单使用

    实际上pygame.display.set_mode()这个函数会返回一个Surface对象,他是位图的一种。

    周小董
  • python 将图像转换为乐高积木风格图片(上)

    今天早上起来,看到一张乐高人的图片,突然萌生一个想法,能不能将任意一张图片转换成乐高积木风格图片。

    叶子陪你玩
  • circos 可视化手册-tile 篇

    tile用来展示基因组上区域的分布,和之前介绍过的highlight不同,这些区域在图中并不是位于同一层的。为了避免不同区域之间的重叠,tile会将有重叠的区域...

    生信修炼手册
  • OpenGL ES 2.0 (iOS)[01]: 一步从一个小三角开始

    1). 三个什么端点(屏幕坐标点)? 要回答这个问题要先了解 OpenGL ES 的坐标系在屏幕上是怎样分布的:

    半纸渊
  • 基于tkinter的GUI编程

    tkinter:tkinter是绑定了Python的TKGUI工具集,就是Python包装的Tcl代码,通过内嵌在Python解释器内部的Tcl 解释器实现的,...

    py3study

扫码关注云+社区

领取腾讯云代金券