题面:不互质的数

大秦 为你打开 题目传送门

备用题面

看不了题目的看下面喵!

对于给定的 N,定义 S(k)(x1,x2,,xk) 的数量。
(x1,x2,,xk) 满足以下条件:

  1. (x1,x2,,xk) 为正整数
  2. x1+x2++xk=N

现在需要你找到 (S(1)+S(2)++S(N))mod109+7

思路

不难注意到对于 N 而言 S(k)=CN1k1,我们要求的式子就可以化为 i=0N1CN1i=2N1。但是 N 特别大,大到需要高精度怎么办?快速幂显然不行,注意到 2P1=1(modP) 所以不断地从 N 中提取出 P1 即可。

代码

cpp
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;
}