小彩的1024“签到”题 - 题解

题目描述

给定一个正整数 n，你需要构造一个长度为 n 的序列。构造规则如下：

  1. 序列中可以包含尽可能多的非重叠子串 "1024"。
  2. 在填入最大数量的 "1024" 后，剩余的空位（我们称之为“自由位”）可以用 0-9 中的任意数字填充。
  3. 请计算，总共能构造出多少种不同的序列。由于答案可能很大，请对 取模。

输入： 一个正整数 n。

输出： 构造方案的总数。

算法思路

核心观察

要解决这个问题，我们需要抓住题目的核心——“尽可能多的1024”。

  1. 周期性结构：一个 "1024" 子串恰好占据4个位置。这意味着问题的本质与周期 4 相关。
  2. 剩余位置：当我们在长度为 n 的序列中填充尽可能多的 "1024" 后，会剩下 n % 4 个位置。这些就是“自由位”。

关键转化

直接去计算如何排列 floor(n/4) 个 "1024" 子串和 n%4 个自由位是一个非常复杂的排列组合问题。一个更聪明的想法是 逆向思维：我们不考虑放置 "1024" 模块，而是考虑放置数量更少的“自由位”。

整个问题可以转化为：在一个长度为 n 的空序列中，我们首先需要为 n % 4 个自由位确定位置，然后再确定这些位置上要填入什么数字。

算法步骤

1. 确定“自由位”的数量

首先，我们计算出自由位的确切数量。 令 。 这个 p 就是我们需要处理的自由位的个数。

2. 为“自由位”选择位置

接下来，我们需要从总共 n 个位置中，选出 p 个位置来安放我们的自由位。这是一个经典的组合问题，方案数即为从 n 个元素中选取 p 个的组合数：

3. 填充“自由位”

根据题目描述，每个自由位都可以用 0-9 中的任意数字填充。这意味着每个自由位都有 10 种选择。 对于 p 个自由位，根据乘法原理，总的填充方案数为：

4. 构造答案

将“选择位置”的方案数和“填充内容”的方案数相乘，即可得到最终答案。 其中 。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int power(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
int inv(int x){
    return power(x,mod-2);
}
int C(int n,int m){
    int res=1,i;
    for(i=1;i<=m;i++){
        res=res*(n-i+1)%mod;
        res=res*inv(i)%mod;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    long long i,j,k,c1=0,c2=0,x,y,z,ii,jj,kk;
    
    int _=1;
    while(_--){
        int n,k,m,q;
        cin>>n;
        int p=n%4;
        n%=mod;
        cout<<C(n,p)*power(10,p)%mod;
    }
}
/*
2 1
5 99
2 1 2
*/

算法分析

时间复杂度

  • O(p * log(mod))，其中 。由于 p 的最大值仅为 3，所以对于每次查询，计算组合数和快速幂的时间复杂度都是常数级别的。

空间复杂度

  • O(1)，只使用了固定的几个变量。

关键点与常见错误

1. 为什么是选择“自由位”？

这是一个核心的思维转换。如果尝试去排列 floor(n/4) 个 "1024" 和 p 个自由位，会陷入非常复杂的“多重集排列”问题。而通过选择少数的“自由位”，问题被极大地简化了。

2. 忘记填充自由位

// 错误：只计算了位置的选择
cout << C(n, p);

// 正确：需要乘上每个位置的填充方案
cout << C(n, p) * power(10, p) % mod;

一个常见的错误是只计算了 ，忘记了每个自由位还有 10 种填充方案，导致遗漏了 这一重要部分。

3. 组合数计算中的取模

// 错误：直接使用 n
C(n, p);

// 正确：需要对 n 本身也取模，因为它参与乘法
n %= mod;
cout << C(n, p) * ...

在计算组合数 的过程中，n 会作为乘数出现，因此 n 本身也需要先对 mod 取模，防止中间过程溢出。

总结

这道题表面上是一个复杂的序列构造问题，但实际上考察的是：

  1. 模型转换能力： 将问题从“放置多数元素”转化为“放置少数元素”。
  2. 组合数学： 熟练运用组合数公式 和乘法原理。
  3. 数论基础： 使用快速幂和费马小定理（求逆元）来处理大数取模。

关键在于识别出 n % 4 这个核心规律，并围绕它建立起正确的组合计数模型。