codeforces 196 div.1

本文从WordPress迁移而来, 查看全部WordPress迁移文章

A.题意略,摆放的策略是尽量避免翻倍,因为每K个后就翻倍,所以贪心地摆放就是每摆放K-1个,空一格空格,然后再放K-1个,以此类推,直到放完。可知这样放一次翻倍都没有,放了几个分数就是多少,最多的摆放个数是M = n - n/k,如果 m <= M,那么答案就是m本身(不存在翻倍)

当m > M,那么只能把剩下在放在那些空格里,剩下的空格数是n/K,剩下要放的个数是m-M,其实每放在一个空格,就会产生一次翻倍,例如
n = 15 , K = 5,一开始摆放的状态为

4 ,空格,4,空格,4,空格 一共放了12个

第13个放在第1个空格里,状态变为 9,空格,4,空格 (9可以看成5+4)

值得注意的是9,前5个产生了翻倍,5—-10,后面的一共就是10+4+4=18,最后分数是18

第14个放在第2个空格里,状态变为 14,空格,(14可以看成 5 + 5 + 4)

前面产生了翻倍,5—-10 , 10+5=15,15—-30,30+4=34,最后得分是34

这时候,看看翻倍的怎么算,就很明白了

如果整个序列中

需要翻倍一次,翻倍部分的值为 2K;二次,翻倍部分的值为 6K
14K
F1 = 2K , F2 = 6K , F3 = 14K , Fn = 2 * Fn-1 + 2K

这种递推式子就可以用矩阵快速幂来求解

记得求解完需要翻倍的部分后,还要算上剩下的部分,即那些不同翻倍有多少个就有多少分的部分,代码中的re变量就是记录那些值

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
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define MOD 1000000009LL

const LL mat[2][2] = {2,0,1,1};
LL A[2][2];

void POW(LL m){
if(m == 1) return ;
POW(m>>1);
LL C[2][2];
for(int r = 0; r < 2; r++)
for(int c = 0; c < 2; c++){
C[r][c] = 0LL;
for(int k = 0 ; k < 2; k++)
C[r][c] = (C[r][c]+(A[r][k] * A[k][c])%MOD)%MOD;
}
if(m&1){
for(int r = 0; r < 2; r++)
for(int c = 0; c < 2; c++){
A[r][c] = 0LL;
for(int k = 0; k < 2; k++)
A[r][c] = (A[r][c]+(C[r][k] * mat[k][c])%MOD)%MOD;
}
}
else{
for(int r = 0; r < 2; r++)
for(int c = 0 ; c < 2; c++)
A[r][c] = C[r][c];
}
}

int main(){
LL n,m,K;
while(cin >> n >> m >> K){
LL M = n - n/K;
if(m <= M){
cout << m << endl;
continue;
}
LL d = m - M;
LL re = m - d*K;
for(int i = 0 ; i < 2; i++)
for(int j = 0; j < 2; j++)
A[i][j] = mat[i][j];
POW(d);
LL ans = ((((A[1][0]*2)%MOD)*K)%MOD + re) % MOD;
cout << ans << endl;
}
return 0;
}