首页 / 更多教程 / 牛客网多校训练4 A Ternary String（高阶幂次取模）

牛客网多校训练4 A Ternary String（高阶幂次取模）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了牛客网多校训练4 A Ternary String（高阶幂次取模），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1396字，纯文字阅读大概需要2分钟。

内容图文

题意：每一次都在2后面插一个1，在1后面插一个0，然后删除第一个数，问你这个字符串什么时候消失

思路：这个题是假的-1，队友发现一个0的贡献是1s，一个1是2s，一个2是6*2^3+3,这样我们就可以算出整个串的值，但是这里还有一个取模的问题，其实就是扩展欧拉定理，你对一个数的幂数取模，要模上模数的欧拉函数值，所以这里需要一直迭代，其实1e9+7的欧拉拉函数迭代28次就变成1了，这里有个地方就是看了聚聚们的代码，发现有人是用递归写的，很方便，就抄袭了一份（QAQ），比赛的时候差一点点，提交一直wa，后来想到是因为需要一直求欧拉的欧拉，而且想到的时候也没时间改了，凉凉

代码：

#include <bits/stdc++.h>
usingnamespace std;
typedef longlong LL;
const LL MOD=1e9+7;
constint maxn=100100;
char s[maxn];
map<LL,LL>mp;
 
//直接求解欧拉函数
LL euler(LL n){ //返回e(n)
     LL res=n,a=n;
     for(LL i=2;i*i<=a;i++){
         if(a%i==0){
             res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出while(a%i==0) a/=i;
         }
     }
     if(a>1) res=res/a*(a-1);
     return res;
}
 
LL qmod(LL a,LL b,LL p)
{
    if (b == 0) return1;
    LL r = a % p;
    LL k = 1;
    while (b > 1){
        if ((b & 1)!=0)
            k = (k * r) % p;
        r = (r * r) % p;
        b >>= 1;
    }
    return (r * k) % p;
}
 
LL solve(int i,LL p){
//    printf("test %d %lld\n",i,p);if (i==-1) return0;
    if (p==1) return0;
    if (s[i]==‘2‘) return (3*qmod(2,solve(i-1,mp[p])+1,p)-3+p)%p;
    if (s[i]==‘1‘) return ((solve(i-1,p)+1)*2+p)%p;
    if (s[i]==‘0‘) return (solve(i-1,p)+1+p)%p;
    return0;
}
void init()
{
    LL asd=1e9+7;
    while(asd!=1){
        mp[asd]=euler(asd);
        asd=mp[asd];
    }
    mp[asd]=1;
}
int main()
{
    int T;
    init();
    scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        int len=strlen(s);
        printf("%lld\n",solve(len-1,MOD)%MOD);
    }
    return0;
}

 

原文：https://www.cnblogs.com/lalalatianlalu/p/9383081.html

内容总结

以上是互联网集市为您收集整理的牛客网多校训练4 A Ternary String（高阶幂次取模）全部内容，希望文章能够帮你解决牛客网多校训练4 A Ternary String（高阶幂次取模）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1299077.html

来源：【匿名】