Skip to content
Nahida-aa

combinatorics

base

Section titled “base”

例题

Section titled “例题”

超大数

Section titled “超大数”

小蓝想要构造出一个长度为 10000 的数字字符串，有以下要求:

  1. 小蓝不喜欢数字 0，所以数字字符串中不可以出现 0;
  2. 小蓝喜欢数字 3 和 7，所以数字字符串中必须要有 3 和 7 这两个数字。

请问满足题意的数字字符串有多少个？ 记作 count

这个数字会很大，你只需要输出 count 取余 10^9+7 后的结果 (res)。

MOD = 10**9 + 7
res = count % MOD

枚举解空间

Section titled “枚举解空间”
MOD = 10**9 + 7
n = 10
n0 = 0
n1 = 10**n - 1
count = 0
for num in range(n0+1, n1+1):
    s = str(num)
    if '0' in s:
        continue
    if '3' not in s or '7' not in s:
        continue
    count += 1


res = count % MOD
print(res)

组合数学法

Section titled “组合数学法”
  1. 容斥原理: -我们需要计算包含 ( 3 ) 和 ( 7 ) 的字符串数，可以通过容斥原理计算：
    • 不包含 ( 3 ) 的字符串数：( 8^n )（每个位置只能是 ( 1, 2, 4, 5, 6, 7, 8, 9 )）。
    • 不包含 ( 7 ) 的字符串数：( 8^n )。
    • 不包含 ( 3 ) 和 ( 7 ) 的字符串数：( 7^n )（每个位置只能是 ( 1, 2, 4, 5, 6, 8, 9 )）。
  • 根据容斥原理，至少包含 ( 3 ) 和 ( 7 ) 的字符串数为： 不包含的字符串数不包含的字符串数不包含和的字符串数 即：
  1. 模运算:
  • 由于 ( n = 10000 ) 非常大，直接计算 ( 9^n )、( 8^n )、( 7^n ) 会导致数值溢出，因此需要使用快速幂算法来计算这些值，并在每一步取模 ( 10^9+7 )
MOD = 10**9 + 7


# 快速幂计算 (base^exp) % mod
def fast_pow_mod(base, exp, mod):
    result = 1
    while exp > 0:
        # if exp % 2 == 1:
        if exp & 1 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        # exp //= 2
        exp >>= 1
    return result


def solve():
    n = 10000


    # 计算 9^n, 8^n, 7^n
    pow_9 = fast_pow_mod(9, n, MOD)
    pow_8 = fast_pow_mod(8, n, MOD)
    pow_7 = fast_pow_mod(7, n, MOD)


    # 根据容斥原理计算结果
    res = (pow_9 - 2 * pow_8 + pow_7) % MOD
    return res


# 输出结果
res = solve()
print(res)

村民的真话与谎言

Section titled “村民的真话与谎言”

问题描述

n 名村民围坐在一张古老的圆桌旁，参与一场思想的较量。这些村民，每一位都有着鲜明的身份：要么是誉满乡野的诚实者，要么是无可救药的说谎者。

当会议的钟声敲响，一场关于真理与谬误的辩论随之展开。每位村民轮流发言，编号为 i 的村民提出了这样的断言：坐在他之后的两位村民 — 也就是编号 i+1 和 i+2（注意，编号是环形的，所以如果 i 是最后一个，则 i+1 是第一个，以此类推）之中，一个说的是真话，而另一个说的是假话。

在所有摇曳不定的陈述中，有多少真言隐藏在谎言的面纱之后？

请你探索每一种可能的真假排列组合，并计算在所有可能的真假组合中，说谎者的总数。

输入格式

第一行输入一个整数 T，表示数据的组数。

接下来 T 行，每行包含一个整数 n，表示村落的人数。

输出格式

对于每组数据，输出一行包含一个整数，表示答案。

样例输入

1
3

样例输出

6

样例说明

在样例中，可能的组合有 「假，假，假」「真，真，假」「真，假，真」「假，真，真」，说谎者的总数为 3+1+1+1=6

评测用例规模与约定

对于 10%的评测用例，T=1，3≤n≤10

对于 40% 的评测用例，1≤T≤10^2，3≤n≤3×10^3

对于所有评测用例，1≤T≤10^5 ，3≤n≤10^18

import sys
input = lambda: sys.stdin.readline().strip()
T = int(input())
for _ in range(T):
    n = int(input())
    if n % 3 == 0:
        print(2 * n)
    else:
        print(n)

分析

n=3
[1, 1, 1] 3


[0, 1, 1] x
[1, 0, 1] x
[1, 1, 0] x


[0, 0, 1] 1
[0, 1, 0] 1
[1, 0, 0] 1


[0, 0, 0] x


res = 6
对于 4,
[1, 1, 1, 1] 4


[0, 1, 1, 1] x
[1, 0, 1, 1] x
[1, 1, 0, 1] x
[1, 1, 1, 0] x


[0, 0, 1, 1] x
[0, 1, 0, 1] x
[0, 1, 1, 0] x
[1, 0, 0, 1] x
[1, 0, 1, 0] x
[1, 1, 0, 0] x


[1, 0, 0, 0] x
[0, 1, 0, 0] x
[0, 0, 1, 0] x
[0, 0, 0, 1] x


[0, 0, 0, 0] x


res = 8
n = 5
[1, 1, 1, 1, 1] 5


[0, 1, 1, 1, 1] x
[1, 0, 1, 1, 1] x
[1, 1, 0, 1, 1] x
[1, 1, 1, 0, 1] x
[1, 1, 1, 1, 0] x


[0, 0, 1, 1, 1] x
[0, 1, 0, 1, 1] x
[0, 1, 1, 0, 1] x
[0, 1, 1, 1, 0] x
[1, 0, 0, 1, 1] x
[1, 0, 1, 0, 1] x
[1, 0, 1, 1, 0] x
[1, 1, 0 ,0 ,1] x
[1, 1, 0, 1, 0] x
[1, 1, 1, 0, 0] x


[0, 0 ,0 ,1 ,1] x
[0, 0 ,1 ,0 ,1] 2
[0, 0 ,1 ,1 ,0] x
[0, 1, 0 ,0 ,1] 2
[0, 1, 0 ,1 ,0] 2
[0, 1, 1 ,0 ,0] x
[1, 0 ,0 ,0 ,1] x
[1, 0 ,0 ,1 ,0] 2
[1, 0 ,1 ,0 ,0] 2
[1, 1 ,0 ,0 ,0] x


[0, 0 ,0 ,0 ,1] x
[0, 0 ,0 ,1 ,0] x
[0, 0 ,1 ,0 ,0] x
[0, 1 ,0 ,0 ,0] x
[1, 0, 0, 0, 1] x
[1, 0, 0, 1, 0] 2
[1, 0, 1, 0, 0] x


[0, 0 ,0 ,0 ,1] x
[0, 0 ,0 ,1 ,0] x
[0, 0 ,1 ,0 ,0] x
[0, 1 ,0 ,0 ,0] x
[1, 0 ,0 ,0 ,0] x


[0, 0 ,0 ,0 ,0] x
对于 n
不可能的情况:
[...,0,0,0,...]
[...,0,1,1,...]
可能的情况:
[...,1,0,0,...]
[...,0,1,0,...]
[...,0,0,1,...]
[...,1,1,0,...]
[...,1,0,1,...]
[...,1,1,1,...]
t1