CF337C-Quiz-数学&模拟

题目链接

https://www.luogu.org/problemnew/show/CF337C

题意:有n个问题,回答对一个得一分,而且连续k个问题回答正确分数翻倍(之后连续的计数器重置为0计算),你回答对了m个,求你最小的可能得分

分析

CF前几题常见套路,给你一个非常简单但有点烦人的问题,但总是有各种坑点让你$fst$

我们肯定是尽量不让它连续回答对k个,于是分成$n/k$组(余下的那部分先不管,因为根本达不到$k$个),如果每组中能满足至少一道错题,那么答案显然就是$m$

那如果不是呢？根据贪心的思路,就是尽量早点让分数翻倍,不然后面分数会更大,然后我们发现如果$x$组问题(当然按照贪心思路这x组肯定从第一组开始)不可避免地全回答对,那么获得的分数为$2k+4k+8k+…+2^x k$,于是转化为等比数列求和公式求和,再处理剩下的问题就好了

注意

最后这里:

1
ans=(z+m-y*k%p+p)%p;

可能出现负数,$y * k$要取模或者加上模数$p$,又被坑到了,查了好久的错。。。

代码

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <iostream>
#define ll long long 
#define ri register int 
using std::min;
using std::max;
template <class T>inline void read(T &x){
	x=0;int ne=0;char c;
	while(!isdigit(c=getchar()))ne=c=='-';
	x=c-48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
	x=ne?-x:x;return ;
}
const int maxn=100005;
const ll inf=1e17;
const ll p=1e9+9;
ll n,m,k;
inline ll ksm(ll a,ll c){
	ll ans=1;
	while(c){
		if(c&1)ans=ans*a%p;
		a=a*a%p;
		c=c>>1;
	}
	return ans%p;
}
int main(){
	ll x,y,z,a,b,ans=0;
	while(scanf("%I64d %I64d %I64d",&n,&m,&k)!=EOF){
		x=n/k;//分组的组数
		if((k-1)*x+(n-x*k)>=m){//有足够错题
      //n-x*k是余下的问题,他们全对也不会分数翻倍
			printf("%I64d\n",m);
		}
		else{
			y=x-(n-m);//全做对的组别数 
			z=(k*(ksm(2,y+1)-2))%p;//等比数列求和
			ans=(z+m-y*k%p+p)%p;//m-y*k是除了全做对的组别外剩下做对的题 
			printf("%I64d\n",ans);
		}
	}
	return 0;
}