6
14
2016
0

【比赛】Educational Codeforces Round 13

关于Educational Codeforces Round :

1、定位于新人学习和训练= =

2. 题目不仅有比赛的problems,还可能会有训练的exercises

3. 题目的考察点可能会被反复使用

4. 不参与计算rating(至少目前是)

5. 比赛的编码阶段和hack阶段分开,编码结束之后的结果是暂时的

6. 编码阶段结束之后,开放24小时的hack,hack的数据可能会被添加到最终的测试数据中去

7. 最终测试数据确定之后的测试结果作为比赛结果

A.Johny Likes Numbers

求大于n的最小的K的倍数。(1<=n,k<=10^9)

O(1)公式题

ans=(n/K+1)*K. 注意K与n大小关系不确定.

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,K;
int main()
{
	scanf("%lld%lld",&n,&K);
	printf("%lld",(n/K+1)*K);
	return 0;
}


B. The Same Calendar

求给出年份y之后第一个与y的日期(星期几)完全相同的年份。注意闰年。(1000<=y<=1000,000)

我赛后被hack了!【数据待补充】

要求的年份与y相差天数%7==0,且平/闰年一致。

bool check(int p)
{
    if(p%400==0)return 1;
    if(p%4==0&&p%100!=0)return 1;
    return 0;
}

【待改正】


C. Joty and Chocolate

1~n的序列,编号为a倍数的元素可获得p块巧克力,编号为b倍数的元素可获得q块巧克力,满足的条件不可累加,求最多获得的巧克力数。(1 ≤ n, a, b, p, q ≤ 10^9)

将编号为lcm(a,b)的元素分给获得巧克力数多的那个,整体计算。

LL gcd(LL x,LL y)
{
	if(!y) return x;
	return gcd(y,x%y);
}
LL lcm(LL x,LL y)
{
	return x*y/gcd(x,y);
}

D. Iterated Linear Function

定义函数f(x)=A*x+B,

g(0)(x)=x;

g(n)(x)=f(g(n-1)(x)),(n>0)

给定A,B,n,x求g(n)(x)%(10^9+7)

1 ≤ A, B, x ≤ 10^9, 1 ≤ n ≤ 10^18

非常经典的题目了吧!O(logN)的做法有两种:

1、矩阵乘法:初始矩阵S=[x,1],转移矩阵T=[[A,0],[B,1]],S*T^n%MOD

2、等比数列求和推通项公式,结合快速幂,费马小定理求逆元。

注意要特判A==1的情况!

#include<bits/stdc++.h>
#define F(i,s,t) for(int i=(s);i<=(t);i++)
#define mec(a,x) memset(a,x,sizeof(a)) 
#define MOD 1000000007
using namespace std;
typedef long long LL;
LL A,B,x,n;
struct matrix{
	LL c[3][3];//大一点木事 
	void init(){mec(c,0);}
	friend matrix operator *(const matrix &S,const matrix &T){
		matrix res;
		F(i,1,2) F(j,1,2){
			res.c[i][j]=0;
			F(k,1,2) res.c[i][j]=(res.c[i][j]+S.c[i][k]*T.c[k][j])%MOD;
		}
		return res;
	}
}t,ans;
void matrix_pow()
{
	ans.c[1][1]=x;ans.c[1][2]=1;
	while(n){
		if(n&1) ans=ans*t;
		t=t*t;
		n>>=1;
	}
}
int main()
{
	scanf("%lld%lld%lld%lld",&A,&B,&n,&x);
	t.init();ans.init();
	t.c[1][1]=A;t.c[2][1]=B;
	t.c[1][2]=0;t.c[2][2]=1;
	matrix_pow();
	printf("%lld\n",ans.c[1][1]);
	return 0;
}
Category: 比赛 | Tags: 公式题 数论 矩阵乘法 | Read Count: 566

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com