题面：不互质的数

大秦 为你打开 题目传送门

备用题面

看不了题目的看下面喵！

对于给定的 $N$，定义 $S(k)$ 为 $(x_1,x_2,…,x_k)$ 的数量。
$(x_1,x_2,…,x_k)$ 满足以下条件：

  1. $(x_1,x_2,…,x_k)$ 为正整数
  2. $x_1+x_2+…+x_k=N$

现在需要你找到 $(S(1)+S(2)+…+S(N)) \bmod 10^9+7$

思路

不难注意到对于 $N$ 而言 $S(k)=C_{N-1}^{k-1}$，我们要求的式子就可以化为 $\sum_{i=0}^{N-1}C_{N-1}^i=2^{N-1}$。但是 $N$ 特别大，大到需要高精度怎么办？快速幂显然不行，注意到 $2^{P-1}=1\pmod P$ 所以不断地从 $N$ 中提取出 $P-1$ 即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int N = 1e5+5;
const ll mod= 1e9+7;
 
string s;
int num[N];

void Input() {
    cin>>s;
}

ll chuli() {
    ll ans = 0;
    for(int i = 0; i < s.length(); i++) num[i] = s[i] - '0';
    int len = s.length();
    for(int i = 0; i < len; i++) {
        ans *= 10;  
        ans += num[i];
        ans %= (mod - 1);
    }
    ans -= 1;
    ans = (ans + mod - 1) % (mod - 1);
    return ans;
}
 
ll quick_pow(ll a,ll k) {
    ll ans = 1;
    while(k) {
        if(k & 1) {
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        k /= 2;
    }
    return ans % mod;
}

void Work() {
    ll k = chuli();
    ll ans = quick_pow(2, k);
    ans = (ans + mod) % mod;
    cout << ans << endl;
}

int main() {
    Input();
    Work();
    return 0;
}