http://codeforces.com/problemset/problem/337/C
题意是给出n个题目，那个人答对了m道，然后如果连续答对了k道，就会把分数double
求最小的分数是什么。
思路是首先看看n个位置能放下多少个（k - 1），也就是先保证不double
比如8能放下多少个3 - 1？能放下3个，mx = n / k + (n % k == k - 1)
那么就是如果答对了6题的话，最小的分数将会是6。
然后如果有多余的，就只能是和前面的连接在一起，double了。
如果后面的n % k != k - 1，那么还有n % k个空位可以放。剩下的，就只能和前面的double了。
优先把前面的double，分数会最小。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int MOD = 1e9 + 9; bool check(int val) { int en = (int)sqrt(val * 1.0); for (int i = 2; i <= en; ++i) { if (val % i == 0) return false; } return true; } LL quick_pow(LL a, LL b, LL MOD) { LL base = a % MOD; LL ans = 1; while (b) { if (b & 1) { ans = (ans * base) % MOD; } base = (base * base) % MOD; b >>= 1; } return ans; } void work() { int n, m, k; scanf("%d%d%d", &n, &m, &k); if (k > m) { cout << m << endl; return; } int mx = n / k + (n % k == (k - 1)); if (mx * (k - 1) >= m) { printf("%d\n", m); return; } LL dis = m - mx * (k - 1); if (n % k != k - 1) { dis -= n % k; } if (dis <= 0) { cout << m << endl; return; } LL ans = 1LL * (mx - dis) * (k - 1) % MOD; LL tans = (quick_pow(2, dis + 1, MOD) + MOD - 2) % MOD; tans = (tans * k) % MOD; ans = (ans + tans) % MOD; if (n % k != k - 1) { ans = (ans + n % k) % MOD; } cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); #endif // cout << check(12) << endl; work(); return 0; }
7 6 3
原文：http://www.cnblogs.com/liuweimingcprogram/p/6416832.html
