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

洛谷P3214 [HNOI2011] 卡农

news 来源：原创 2024/7/1 3:14:38

题目描述

众所周知卡农是一种复调音乐的写作技法，小余在听卡农音乐时灵感大发，发明了一种新的音乐谱写规则。

他将声音分成 𝑛n 个音阶，并将音乐分成若干个片段。音乐的每个片段都是由 11 到 𝑛n 个音阶构成的和声，即从 𝑛n 个音阶中挑选若干个音阶同时演奏出来。

为了强调与卡农的不同，他规定任意两个片段所包含的音阶集合都不同。同时为了保持音乐的规律性，他还规定在一段音乐中每个音阶被奏响的次数为偶数。

现在的问题是：小余想知道包含 𝑚m 个片段的音乐一共有多少种。
两段音乐 𝑎a 和 𝑏b 同种当且仅当将 𝑎a 的片段重新排列后可以得到 𝑏b。例如：假设 𝑎a 为 {{1,2},{2,3}}{{1,2},{2,3}}，𝑏b 为 {{2,3},{1,2}}{{2,3},{1,2}}，那么 𝑎a 与 𝑏b 就是同种音乐。

答案对 108+7108+7 取模。

输入格式

仅一行两个正整数 𝑛,𝑚n,m

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

2 3

输出 #1

说明/提示

【数据范围】
对于 20%20% 的数据，1≤𝑛,𝑚≤51≤n,m≤5；
对于 50%50% 的数据，1≤𝑛,𝑚≤30001≤n,m≤3000；
对于 100%100% 的数据，1≤𝑛,𝑚≤1061≤n,m≤106。

【样例解释】
音乐为 {{1},{2},{1,2}}{{1},{2},{1,2}}

Code:

#include <bits/stdc++.h>// #define int int64_tconst int kMaxN = 1e6 + 5, kMod = 1e8 + 7;namespace Modular {
template<class T>
T qpow(T bs, T idx, T kMod) {bs %= kMod;int ret = 1;for (; idx; idx >>= 1, bs = 1ll * bs * bs % kMod)if (idx & 1)ret = 1ll * ret * bs % kMod;return ret;
}
int inv(int x, int kMod) {x %= kMod;if (!x) { std::cerr << "inv error\n"; return 0; }return qpow(x, kMod - 2, kMod);
}
template<class T, const T kMod>
T add(T x, T y) {if (x + y >= kMod) return x + y - kMod;else return x + y;
}template<class T, const T kMod>
T sub(T x, T y) {if (x - y < 0) return x - y + kMod;else return x - y;
}template<class T, const T kMod>
struct Mint {T x;Mint() { x = 0; }template<class _T> Mint(_T _x) { x = _x; }friend Mint operator +(Mint m1, Mint m2) { return Mint(Modular::add<T, kMod>(m1.x, m2.x)); }friend Mint operator -(Mint m1, Mint m2) { return Mint(Modular::sub<T, kMod>(m1.x, m2.x)); }friend Mint operator *(Mint m1, Mint m2) { return Mint(1ll * m1.x * m2.x % kMod); }friend Mint operator /(Mint m1, Mint m2) { return Mint(1ll * m1.x * inv(m2.x, kMod) % kMod); }Mint operator +=(Mint m2) { return x = Modular::add<T, kMod>(x, m2.x); }Mint operator -=(Mint m2) { return x = Modular::sub<T, kMod>(x, m2.x); }Mint operator *=(Mint m2) { return x = 1ll * x * m2.x % kMod; }Mint operator /=(Mint m2) { return x = 1ll * x * inv(m2.x, kMod) % kMod; }template<class _T> friend Mint operator +(Mint m1, _T m2) { return Mint(Modular::add<T, kMod>(m1.x, m2 % kMod)); }template<class _T> friend Mint operator -(Mint m1, _T m2) { return Mint(Modular::sub<T, kMod>(m1.x, m2 % kMod)); }template<class _T> friend Mint operator *(Mint m1, _T m2) { return Mint(1ll * m1.x * m2 % kMod); }template<class _T> friend Mint operator /(Mint m1, _T m2) { return Mint(1ll * m1.x * inv(m2, kMod) % kMod); }template<class _T> Mint operator +=(_T m2) { return x = Modular::add<T, kMod>(x, m2); }template<class _T> Mint operator -=(_T m2) { return x = Modular::sub<T, kMod>(x, m2); }template<class _T> Mint operator *=(_T m2) { return x = 1ll * x * m2 % kMod; }template<class _T> Mint operator /=(_T m2) { return x = 1ll * x * inv(m2, kMod) % kMod; }template<class _T> friend Mint operator +(_T m1, Mint m2) { return Mint(Modular::add<T, kMod>(m1 % kMod, m2.x)); }template<class _T> friend Mint operator -(_T m1, Mint m2) { return Mint(Modular::sub<T, kMod>(m1 % kMod, m2)); }template<class _T> friend Mint operator *(_T m1, Mint m2) { return Mint(1ll * m1 * m2.x % kMod); }template<class _T> friend Mint operator /(_T m1, Mint m2) { return Mint(1ll * m1 * inv(m2.x, kMod) % kMod); }friend Mint operator -(Mint &m1) { return Mint(m1.x == 0 ? (kMod - 1) : (m1.x - 1)); }friend Mint operator --(Mint &m1) { return m1 = Mint(m1.x == 0 ? (kMod - 1) : (m1.x - 1)); }friend Mint operator ++(Mint &m1) { return m1 = Mint(m1.x == (kMod - 1) ? 0 : (m1.x + 1)); }friend bool operator ==(Mint m1, Mint m2) { return m1.x == m2.x; }friend std::istream &operator >>(std::istream &is, Mint &m) {int x;is >> x;m = Mint(x);return is;}friend std::ostream &operator <<(std::ostream &os, Mint m) {os << m.x;return os;}
};
} // namespace Modularusing mint = Modular::Mint<int, kMod>;int n, m;
mint pw2, f[kMaxN];mint Fac(int n) {mint ret = 1;for (int i = 1; i <= n; ++i)ret *= i;return ret;
}void dickdreamer() {std::cin >> n >> m;pw2 = 1;for (int i = 1; i <= n; ++i)pw2 *= 2;f[0] = 1;mint A = pw2 - 1;for (int i = 2; i <= m; ++i) {f[i] = A - f[i - 1] - f[i - 2] * (i - 1) * (pw2 - i + 1);A *= pw2 - i;}std::cout << f[m] / Fac(m) << '\n';
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;// std::cin >> T;while (T--) dickdreamer();// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}