牛客多校Round 4
2024-09-30 21:55:54
Soved:3
rank:133
A.Ternay String
欧拉降幂一下 但是反复求phi会超时 但mod是同一个就可以记忆化一下
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + ; char s[];
int len;
map<ll, ll> mp; ll getphi(ll o)
{
if(mp[o]) return mp[o];
ll res = o;
ll n = o;
for(ll i = ; i * i <= n; i++)
{
if(n % i == )
{
res -= res / i;
while(n % i == ) n /= i;
}
}
if(n > ) res -= res / n;
mp[o] = res;
return res;
} ll pow_mod(ll x, ll y, ll mo)
{
ll res = ;
while(y)
{
if(y & ) res = res * x % mo;
y >>= ;
x = x * x % mo;
}
return res;
} ll dfs(ll x, ll m)
{
if(x < ) return ;
if(m == ) return ;
if(s[x] == '')
{
ll p = getphi(m);
ll tmp = (dfs(x - , p) + p) % p;
tmp = pow_mod(, tmp, m);
return (6LL * tmp % m - 3LL + m) % m;
}
if(s[x] == '') return (dfs(x - , m) + 1LL) % m;
if(s[x] == '') return (dfs(x - , m) * 2LL + 2LL) % m;
return ;
} int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%s", s);
len = strlen(s);
ll ans = dfs(len - , mod);
printf("%lld\n", ans);
}
return ;
}
最新文章
- 找出A字符串中出现B字符串的起始位置
- python中paramiko模块的使用
- 超级强大的formValidator
- JSONP - 跨域AJAX
- Javascript对象、Jquery扩展简单应用
- js中的 !!
- C++14使用std::integer_sequence展开tuple作为函数的参数
- 后台动态设置前台标签内容和属性(转自http://www.wzsky.net/html/Program/net/26171.html)
- U3D 实现子弹发射效果
- chrome浏览器调试
- 【Android 应用开发】Android 开发 之 JNI入门 - NDK从入门到精通
- Centos7下面配置客户端OpenVPN
- python基础之Day20part1
- 转://如何增加linux根目录的磁盘空间(基于LVM)?
- 059、安装配置flannel(2019-03-28 周四)
- 20172325 2018-2019-2 《Java程序设计》第六周学习总结
- SQLServer转PowerDesigner(转载)
- Log4j rootLogger配置
- Git学习系列之Windows上安装Git之后的一些配置(图文详解)
- 全局 SqlConnection
热门文章
- Linux操作系统改动PATH的方法
- <;form>; 标签的entype属性
- HDU1052Tian Ji -- The Horse Racing
- 下载、编译、运行android 7.1系统(ubuntu 16.0.4)【转】
- 求欧拉回路 UOJ117
- CodeFirst建模:DataAnotation
- nginx开发(二)配置mp4文件在线播放
- 如何给mysql用户分配权限+增、删、改、查mysql用户
- 使用inet_ntoa() 时编译提示错误:
- 8. Ext文本输入框:Ext.form.TextField属性汇总