Problem S4: Interesting Numbers 加强版（数论）

谁践踏了优雅 2022-06-18 05:10 146阅读 0赞

### Problem Description ###

### 　　We call a number interesting, if and only if: ###

### 　　1. Its digits consists of only 0, 1, 2 and 3, and all these digits occurred at least once. ###

### 　　2. Inside this number, all 0s occur before any 1s, and all 2s occur before any 3s. ###

### 　　Therefore, the smallest interesting number according to our definition is 2013. There are two more interseting number of 4 digits: 2031 and 2301. ###

#### 　　Your task is to calculate the number of interesting numbers of exactly n digits. As the answer might be very large, you only need to output the answer modulo 1000000007. ####

Input Format

### 　　The input has one line consisting of one positive integer n (4 ≤ n ≤ 10^15). ###

### Output Format ###

### 　　The output has just one line, containing the number of interesting numbers of exactly n digits, modulo 1000000007. ###

### Input Sample ###

### Output Sample ###

### 题意：求同时满足这样两个条件的n位数的数量： ###

### 1. 0、1、2、3这几个数都出现过。 ###

### 2. 所有0都在1之前，所有2都在3之前。 ###

### 比如样例：4位数：2013，2031，2301。 ###

### 题解： ###

#### 我们很容易看出，数的第一位必然是2，因为第一位不可能是0，而1和3显然也是不行的。 ####

#### 所以我们只需要考虑后面 n−1位，设\{0，1\}在剩余n−1位中占用x个数字，那么\{2,3\}占用n−1−x个数。所以\{0，1\}有x−1种数的安排方法（考虑0出现的次数），\{2，3\}则有 n−1−x种数的安排方法。我们设一下吧，m=n−1。所以这些数的安排方法有f\[x\]=(n−1x)∗(x−1)∗(n−1−x)=(mx)∗(x−1)∗(m−x)。 ####

#### 有i个位置放\{0,1\}，m−i个位置放\{2,3\}。对于，2<=i<=m−1，ans=∑m−1i=2(n−1i)∗(i−1)∗(m−i) ####

#### 因为：f\[0\]=−m，f\[1\]=f\[m\]=0。 ####

#### 所以：ans−m=∑mi=0(n−1i)∗(i−1)∗(m−i)=∑mi=0(n−1i)∗(−i2\+i\+m∗i−m)。 ####

#### 又因为：(1\+x)m=∑mi=0(mi)∗xi ####

#### 令x=1，2m=∑mi=0(mi) ####

#### 对(1\+x)m求导，得m∗(1\+x)m−1=∑mi=1i∗(mi)∗xi−1 ####

#### 两边乘上x，得m∗x∗(1\+x)m−1=∑mi=0i∗(mi)∗xi ####

#### 令x=1，所以：m∗(2)m−1=∑mi=0i∗(mi)。 ####

#### 对m∗x∗(1\+x)m−1=∑mi=0i∗(mi)∗xi。 ####

#### 两边求导并乘上x得：m∗(1\+x)m−1\+m∗(m−1)∗(1\+x)m−2=∑mi=0i2∗(mi)∗xi。 ####

#### 这时，令x=1，m∗2∗(2)m−2\+m∗(m−1)∗(2)m−2=∑mi=0i2∗(mi) ####

#### 化简：(m2\+m)∗(2)m−2=∑mi=0i2∗(mi) ####

#### 所以：ans=−(m2\+m)∗2m−2\+(m\+1)∗m∗2m−1−m∗2m\+m ####

#### 化简：ans=(m2−3∗m)∗2m−2\+m，其中m=n−1。 ####

#### 然后，快速幂就可以解决啦。复杂度O(logN)。 ####

#### 代码： ####

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int mod=1e9+7;
    ll q_mod(ll a,ll b)
    {
        ll ans1=1;
        ll tmp=a;
        while(b>0)
        {
            if(b&1) ans1 = ans1 * tmp % mod;
            b>>=1; 
            tmp = tmp * tmp % mod;
        }
        return ans1;
    }
    int main()
    {
        ll ans=0,tmp=0;
        ll n;
        cin>>n;
        n--;
        ans = (n % mod) * (n % mod);
        ans = ((ans - 3 * n) % mod + mod) %mod;
        tmp = q_mod(2,n-2);
    //  cout<<tmp<<endl;
        ans = ans * tmp % mod;
        ans = (ans + n) % mod;
        cout<<ans<<endl;
        return 0;
    }