A dreamstart的催促 (快速幂) B TRDD got lost again
2024-09-05 22:35:30
链接:https://ac.nowcoder.com/acm/contest/322/A
来源:牛客网
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
题目描述
有一天集训队的学弟们正在计算一堆数,但是dreamstart感觉他们算的太慢了,就让他们坐在一起想出一个快速计算的方法,但是由于他们一时想不出来,想让你帮助他们。他们说现在有一个数列,要算出第 i 个数的 i 次幂并且把每个数计算出来的值加到一起,最后答案模10000019。
聪明的你可以帮助他们吗?
输入描述:
第一行有一个整数n,n <= 1e5 接下来一行有n个数,每个数的大小不超过1e16
输出描述:
输出取模之后的和
示例1
输出
21502 快速幂求解就行
/**
/*快速幂板子
/*
*/
ll mod_pow(ll x , ll n ,ll mod){
if(n==) return ;
ll res = mod_pow(x * x % mod, n / , mod);
if(n % ) res = res * x % mod;
return res;
}
//快速幂
typedef long long ll;
ll mod_pow(ll x ,ll n , ll mod){
ll res;
while(n > ){
if(n & ) res = res * x % mod;
x = x * x % mod;
n >>=;
}
return res;
}
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
long long a[+];
const long long mod=;
int poww(int a, int b) {
ll ans = , base = a;
while (b != ) {
if (b & != )
ans = ans*base%mod;
// base = base*base%mod;
b >>= ;
}
return ans;
} int main() {
//long long x;
int n; scanf("%d",&n);
long long sum = ;
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
//a[i] %= mod;
sum=(sum +poww(a[i],i))%mod;
}
//int num = sum;
printf("%lld\n",sum); return ;
}
X城市是一个交通十分不便利的城市,城市可以看成一个n * m大小的矩阵, 现在TRDD手里有该城市的地图:一个2*n+1行, 2 *m+1列大小的地图。现在TRDD所在的格子用S表示,机场所在的格子用T表示。 其他格子用空格表示,地图上左右相邻的两个格子如果不能通行用"|"表示, 上下相邻的两个点如果不能通行用"-"表示,”+“表示格子的四个角。 题目保证城市X最外圈无法通行(具体请看样例输入)。
为了能尽快赶到机场,TRDD想请你帮忙计算出他到达机场最少需要走过多少个格子(包括起点S和终点T)。
如果无法到达机场T,则输出"TRDD Got lost...TAT"(不包括双引号)。
链接:https://ac.nowcoder.com/acm/contest/322/B
来源:牛客网
来源:牛客网
示例1
示例2
备注:
由于数据量过大,建议不要使用scanf("%c")读入,否则可能会TLE。
如果输入样例显示格式有误, 请参考图片:
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=;x=;int f=;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*+ch-'',ch=getchar();x*=f;Finish_read=;}
template<class T>inline void print(T x){if(x/!=)print(x/);putchar(x%+'');}
template<class T>inline void writeln(T x){if(x<)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int step[][]={{,},{,},{-,},{,-}};
char mp[][];
string now;
int n,m,sx,sy,ex,ey,dis[][];
typedef pair<int,int>pii;
#define fi first
#define se second
int main() {
ios::sync_with_stdio(false);
cin.tie(),cout.tie();
cin>>n>>m;
getline(cin,now);
for(int i=;i<=*n+;++i) {
getline(cin,now);
for(int j=;j<=*m+;++j) {
mp[i][j]=now[j-],dis[i][j]=1e9;
if(mp[i][j]=='S')
sx=i,sy=j;
if(mp[i][j]=='T')
ex=i,ey=j;
}
}
queue<pii>q;
q.push(pii(sx,sy)),dis[sx][sy]=;
for(pii u;!q.empty();q.pop()) {
u=q.front();
int x=u.fi,y=u.se;
if(x==ex&&y==ey)
return *printf("%d\n",dis[x][y]/+);
for(int k=;k<;++k) {
int nx=x+step[k][],ny=y+step[k][];
if((mp[nx][ny]==' '||mp[nx][ny]=='T')&&dis[nx][ny]>dis[x][y]+)
dis[nx][ny]=dis[x][y]+,q.push(pii(nx,ny));
}
}
puts("TRDD Got lost...TAT");
}
最新文章
- xampp 配置虚拟主机
- 网站微信登录授权 ASP.NET
- 编写Java应用程序。首先,定义描述学生的类——Student,包括学号(int)、 姓名(String)、年龄(int)等属性;二个方法:Student(int stuNo,String name,int age) 用于对对象的初始化,outPut()用于输出学生信息。其次,再定义一个主类—— TestClass,在主类的main方法中创建多个Student类的对象,使用这些对象来测 试Stud
- Mysql学习笔记(三)对表数据的增删改查。
- windows核心编程---第一章 谈谈windows中的错误处理机制
- Ninx虚拟主机的配置
- Java:集合框架的工具类
- Thread.sleep() &; SystemClock.sleep()
- 如何自动拼接 Update语句,仅Update已修改的字段
- JQUERY1.9学习笔记 之基本过滤器(十二) 根元素选择器
- 代码发布架构方案(SVN)
- 关于Oracle中查询结果为未选定行
- js 关键字 in
- 使用bootstrap建立响应式网页——头部导航栏
- Python爬虫(十五)_案例:使用bs4的爬虫
- OpenStack构架简介
- HRBUST - 2347 - 递归画图 - vj大一上寒假训练2.11
- ASP.NET C# 实现钉钉签名算法
- 解决ios兼容性问题
- windows下使用vscode编写运行以及调试C/C++