可以知道对于任何数n都可以写成$n=x+[y+z+…]$,则对于任意的一个$x(0\leq x < n)$，后面的式子有${2}^{n-x-1}$种写法
假设对于给定的k，题目要求的就是$f+{n}$
则对于x有两种可能
若$x=k$，则这${2}^{n-x-1}$个式子中，因为第一项就是k，所以每一个式子至少含有1个$k$，现在就看其余项中含有多少$k$，而其余项就是求$f(n-x)$
若$x\neq k$相等，则第一项不含有$k$，就看其余项中含有含有多少$k$，依旧是求$f(n-x)$
注意到，当$k>n$是，$f(n)=0$
则可以得到
$f_{n}=\sum_{i=k}^{n-1}{f_{i}}+{2}^{n-k-1}$
于是可以求出通项公式
$f_{n}=(n-k+3)*{2}^{n-k-2}(n>k)$
官方解题报告
我们特判出$n\leq k$的情况。
对于$1\leq k < n$,我们可以等效为$n$个点排成一列，并取出其中的连续k个点。下面分两种情况考虑：第一种情况，被选出的不包含断电，那么有$n-k-1$种情况完成上述操作，剩下未被圈的点之间还有$n-k-2$个位置，可以在每个位置断开，所以共 $(n-k-1)*{2}^{n-k-2}$ 种方法。
第二种情况，即被选出的包含端点，那么有两种情况，并且剩余共$n-k-1$个位置，所以共$2*{2}^{n-k-1}$种方法。
总计$2 \times 2^{n-k-1}+(n-k-1){2}^{n-k-2}=(n-k-3){2}^{n-k-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
using namespace std;
const int mod=1e9+7;
__int64 mul(__int64 n,__int64 k)
{
__int64 ans=1;
while(k>=1)
{
if(k&1)
ans=ans*n%mod;
k=k/2;
n=n*n%mod;
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
__int64 n,k;
scanf("%I64d%I64d",&n,&k);
__int64 m=n-k;
if(m<0)
{
printf("0\n");
continue;
}
if(m==0||m==1)
{
printf("%I64d\n",m+1);
continue;
}
printf("%I64d\n",mul(2,m-2)*(m+3)%mod);
}
return 0;
}
标程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
using namespace std;
typedef long long LOL;
const LOL MOD = 1000000007ll;
LOL solve(LOL n,LOL k)
{
if(n<k) return 0;
if(n==k) return 1;
LOL ans=n-k+3;
LOL tmp=2;
k=n-k-2;
if(k==-1){
return ans/2;
}
while(k){
if(k%2){
ans=(ans*tmp)%MOD;
}
tmp=(tmp*tmp)%MOD;
k/=2;
}
return ans;
}
int main(void)
{
LOL n,k;
int T;
scanf("%d",&T);
while(T--){
cin>>n>>k;
cout<<solve(n,k)<<endl;
}
return 0;
}