牛客多校 Ternary String (数论)

2024-02-18 05:38

本文主要是介绍牛客多校 Ternary String (数论),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链接:https://www.nowcoder.com/acm/contest/142/A
来源:牛客网

A ternary string is a sequence of digits, where each digit is either 0, 1, or 2. Chiaki has a ternary string s which can self-reproduce. Every second, a digit 0 is inserted after every 1 in the string, and then a digit 1 is inserted after every 2 in the string, and finally the first character will disappear. For example, ``212'' will become ``11021'' after one second, and become ``01002110'' after another second. Chiaki would like to know the number of seconds needed until the string become an empty string. As the answer could be very large, she only needs the answer modulo (109 + 7).
输入描述:
There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:The first line contains a ternary string s (1 ≤ |s| ≤ 105).It is guaranteed that the sum of all |s| does not exceed 2 x 106.
输出描述:
For each test case, output an integer denoting the answer. If the string never becomes empty, output -1 instead.

示例1

输入
复制

3
000
012
22

输出
复制

3
93
45

思路:

1. 如果遇到了 0, t++

2. 如果遇到了1,t = t*2+2

因为之前经历了t,那么就会派生出来t个0,加上一个1的时间 2 就是上式了

3. 如果遇到了2,t = 3*(2^t -1) 

可以类似于2来想,经过了t后到了一个2

会变成这样 21101001000100001.......

再过一秒会变成1101001000100001000001.......   // **** 等了一秒

观察这个序列可以发现:该序列满足2的结论 。

消灭到第一个1和他后面的0  需要  a1 = 2

消灭到第二个1和他后面的0  需要  a2 = 2*a1+2 + 2-1 = 7 

消灭到第三个1和他后面的0  需要  a3 = 2*a2+2 + 3-1 = 18

消灭到第 i 个1和他后面的0  需要  a[i] = 2*a[i-1]+2+i-1 = 2*a[i-1]+i+1

有了 a[i+1] = 2*a[i]+i+2,a[1] = 2, 就可以求a[n] 了

两边同时加 i+4 得到  a[i+1]+(i+1)+3 = 2(a[i]+i+3)

令b[n] = a[n]+n+3 , b1 = a1+4 = 6;

b[n+1]/b[n] = 2;  

得到 b[n] = 6*2^(n-1) = 3*2^n

得到 a[n] = b[n]-n-3 = 3*2^n-n-3

a[n] 就是在之前时间为n-1 (因为之前等了一秒)时,当前2消掉的花费了。

再加上之前的花费n-1 + 1可以算出总的当前花费 3*2^n-3

那么由于每次都要对前面的结果取一次指数,就得用指数循环节了

1e9+7 开始打个表,20多次phi就能打到1了·剩下的就是维护指数,和结果了

倒存一下mod,正向一遍出结果。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;
char s[maxn];
stack <ll> mod;
ll qm(ll a, ll n, ll m)
{if(a >= m) a = a%m+m;ll ans = 1;while(n){if(n%2) {ans = ans*a;if(ans >= m) ans = ans%m+m;	}	a = a*a;if(a >= m) a= a%m+m;n/=2;}return ans;
}
map <int,ll> phi;
ll get_phi(ll n)
{ll ans = n;for(ll i = 2; i*i <= n; i++){if(n%i == 0) ans = ans-ans/i;while(n%i==0) n/=i;}if(n!=1) ans = ans-ans/n;return ans;
}int main()
{ll kk;phi[1] = 1;for(ll i = 1e9+7; i > 1; i=kk){kk = get_phi(i);phi[i] = kk;}int t;scanf("%d",&t);while(t--){scanf("%s",s);int len = strlen(s);while(mod.size()) mod.pop();ll md = 1e9+7;for(int i = len-1; i >= 0; i--){if(s[i] == '2') {mod.push(md);md = phi[md];}}ll ans = 0;ll tmp = 0;ll MOD = 1e9+7;if(mod.empty()) mod.push(MOD);for(int i = 0; s[i]; i++){if(s[i] == '0'){ans=(ans+1)%MOD;tmp=(tmp+1);if(tmp >= md) tmp = tmp%md+md;}if(s[i] == '1'){ans=(2LL*ans+2LL)%MOD;tmp=(2LL*tmp+2LL);if(tmp >= md) tmp = tmp%md+md;}if(s[i] == '2') {md = mod.top();mod.pop();tmp = 3LL*qm(2,tmp+1,md);ans = (tmp-3+MOD)%MOD;tmp = (tmp-3+md*MOD);if(tmp >= md) tmp = tmp%md+md;}}printf("%lld\n",ans);}return 0;
}

 

这篇关于牛客多校 Ternary String (数论)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/720203

相关文章

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

java String.join()的使用小结

《javaString.join()的使用小结》String.join()是Java8引入的一个实用方法,用于将多个字符串按照指定分隔符连接成一个字符串,本文主要介绍了javaString.join... 目录1. 方法定义2. 基本用法2.1 拼接多个字符串2.2 拼接集合中的字符串3. 使用场景和示例3

C# string转unicode字符的实现

《C#string转unicode字符的实现》本文主要介绍了C#string转unicode字符的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随... 目录1. 获取字符串中每个字符的 Unicode 值示例代码:输出:2. 将 Unicode 值格式化

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下:1. 字符串的不可变性:每次修改都创建新对象2. 使用 == 比较字符串,陷阱满

IDEA如何将String类型转json格式

《IDEA如何将String类型转json格式》在Java中,字符串字面量中的转义字符会被自动转换,但通过网络获取的字符串可能不会自动转换,为了解决IDEA无法识别JSON字符串的问题,可以在本地对字... 目录问题描述问题原因解决方案总结问题描述最近做项目需要使用Ai生成json,可生成String类型

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

数论ZOJ 2562

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。 分析:反素数定义:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7

POJ2247数论

p = 2^a*3^b*5^c*7^d 求形如上式的第n小的数。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.u