本文涉及知识点

组合数学汇总

LeetCode2550. 猴子碰撞的方法数

现在有一个正凸多边形，其上共有 n 个顶点。顶点按顺时针方向从 0 到 n - 1 依次编号。每个顶点上 正好有一只猴子 。下图中是一个 6 个顶点的凸多边形。

每个猴子同时移动到相邻的顶点。顶点 i 的相邻顶点可以是：
顺时针方向的顶点 (i + 1) % n ，或
逆时针方向的顶点 (i - 1 + n) % n 。
如果移动后至少有两只猴子停留在同一个顶点上或者相交在一条边上，则会发生 碰撞 。
返回猴子至少发生 一次碰撞 的移动方法数。由于答案可能非常大，请返回对 109+7 取余后的结果。
注意，每只猴子只能移动一次。
示例 1：
输入：n = 3
输出：6
解释：共计 8 种移动方式。
下面列出两种会发生碰撞的方式：

• 猴子 1 顺时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 2 碰撞。
• 猴子 1 逆时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 3 碰撞。
  可以证明，有 6 种让猴子碰撞的方法。
  示例 2：
  输入：n = 4
  输出：14
  解释：可以证明，有 14 种让猴子碰撞的方法。
  提示：
  3 <= n <= 10⁹

乘法原理

每只猴子都有两种选择，彼此独立，故共有2ⁿ种方案。只有两种方案（全顺时针和全逆时针）不会相撞，其它方案至少有一个猴子相撞。

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator/(const C1097Int& o)const
	{
		return *this * o.PowNegative1();
	}
	C1097Int& operator/=(const C1097Int& o)
	{
		*this /= o.PowNegative1();
		return *this;
	}
	bool operator==(const C1097Int& o)const
	{
		return m_iData == o.m_iData;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return m_iData;
	}
private:
	int m_iData = 0;;
};

	class Solution {
		public:
			int monkeyMove(int n) {
				auto ans = C1097Int<>(2).pow(n) - 2;
				return ans.ToInt();
			}
		};

单元测试

TEST_METHOD(TestMethod11)
		{
			auto res = Solution().monkeyMove(3);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().monkeyMove(4);
			AssertEx(14, res);
		}