每个 m 元子集恰好给出 2 个合法数列,答案为 2^(n+1)-n^2-n-2;n 有 5000 位,按字符串读入并用费马小定理降幂。
OJ: roj
题目 ID: 1799
难度:提高+/省选-
标签:数学组合计数费马小定理大整数python
创建: 2026-10-08 03:52
更新: 2026-10-08 03:52
形式化题目
从
即
正解
思路
先看暴力能给我们什么。 直接按定义搜索:顺序枚举
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|
| 2 | 10 | 32 | 84 | 198 | 438 | 932 | 1936 |
暴力为什么撑不住。 搜索树在第
关键观察:合法数列由元素集合唯一决定(只差一个朝向)。 把条件改写成相邻差的形式。
令
也就是说:相邻差必须符号交替,并且绝对值严格递增。由此可以顺着读下去:
:先定朝向。若 ,则 、 ; : ,所以必须 且 ,于是 。 此时四条大小关系被锁死为 ; : ,所以必须 且 , 由 得 ,故 ; 又 结合 的位置可进一步确定 ,链条扩展为 。
每加一项,大小顺序都是被前两项唯一决定的:峰值只可能往右往高走、谷值只可能往左往低走, 交替进行。于是:
- 所有
必两两不同; - 一旦
的朝向确定( 或 ), 后面每一项在完整有序链中的位置就被唯一确定。
于是得到双射。 从
闭式。 对所有
用上面的暴力表逐点核对:
剩下的问题只是算这个式子。
用来算多项式部分 ; 配合费马小定理给指数降幂:因 为素数且 , 有 ,故 。
两个模数不能混用:指数只能对
代码
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 03:52
* update_at: 2026-10-08 03:52
*/
// main.cpp:数列 —— 每个 m 元子集恰好对应 2 个合法数列(首三项的两种朝向),
// 故答案为 2 * sum_{m=3}^{n} C(n,m) = 2^(n+1) - n^2 - n - 2。
// n 最多 5000 位十进制,只能按字符串读入;指数用费马小定理降到模 (p-1)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL; // 取模质数 p
const ll PERIOD = MOD - 1; // 费马小定理给出的 2 的指数周期 p-1
// 十进制大串按 Horner 法逐位取模,得到 n mod m
ll mod_of_digits(const string &s, ll m) {
ll r = 0;
for (char c : s) r = (r * 10 + (c - '0')) % m;
return r;
}
// 快速幂:base^e mod MOD
ll power(ll base, ll e) {
ll r = 1;
base %= MOD;
while (e > 0) {
if (e & 1) r = r * base % MOD;
base = base * base % MOD;
e >>= 1;
}
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
if (!(cin >> s)) return 0;
size_t pos = s.find_first_not_of('0'); // 题面保证 n>=3,这里只做健壮性处理
s = (pos == string::npos) ? string("0") : s.substr(pos);
ll np = mod_of_digits(s, MOD); // n mod p,用于多项式部分 n^2+n+2
ll nm1 = mod_of_digits(s, PERIOD); // n mod (p-1),用于指数部分
ll exponent = (nm1 + 1) % PERIOD; // (n+1) mod (p-1)
ll pow2 = power(2, exponent); // 2^(n+1) mod p
ll poly = (np * np % MOD + np + 2) % MOD; // n^2 + n + 2 mod p
ll ans = (pow2 - poly + MOD) % MOD;
cout << ans << '\n';
return 0;
}Python 版本同一算法:用 Python 的任意精度整数做外层减法,但降幂的字符串取模仍按位进行,
不依赖 int() 解析超大十进制串(避免 CPython 3.11+ 的 4300 位转换上限)。
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 03:52
# update_at: 2026-10-08 03:52
import sys
MOD = 10 ** 9 + 7 # 取模质数 p;指数降幂用它的周期 p-1
PERIOD = MOD - 1
def reduce_mod(digits: str, m: int) -> int:
"""把十进制数字串按 Horner 法逐位取模,避开 int() 的 4300 位字符串上限。"""
r = 0
for ch in digits:
r = (r * 10 + (ord(ch) - 48)) % m
return r
def solve() -> None:
# 输入只有一行一个大整数:取出该 token,去掉前导零(题面保证 n >= 3)。
token = next(iter(sys.stdin.buffer.read().split()))
n_digits = token.decode().lstrip('0') or '0'
n_mod_p = reduce_mod(n_digits, MOD) # n mod p,用于 n^2 + n + 2
n_mod_pm1 = reduce_mod(n_digits, PERIOD) # n mod (p-1),费马小定理降幂用
exponent = (n_mod_pm1 + 1) % PERIOD # (n+1) mod (p-1)
ans = (pow(2, exponent, MOD) - n_mod_p * n_mod_p - n_mod_p - 2) % MOD
print(ans)
if __name__ == "__main__":
solve()复杂度
- 时间:字符串逐位取模
( 为 的十进制位数), 快速幂 ,合计 。 - 空间:
存输入串(逐位处理则 )。
总结
这道题的难点完全在发现结构而不是计算:条件看似是局部约束,但写成分差
一旦拿到闭式,剩下的只是工程细节:读 5000 位十进制串取模、用费马小定理给指数降幂、
注意指数模
关于数据的说明:本仓库该题的 data/ 由素材源自带的 data.py 生成,
题面来自网络重建(素材源里注明检索题解未果,std.cpp 为自研),
因此出题意图与官方原题可能存在偏差;但闭式已用 std.cpp(等价地写成