d88888888

news/2024/7/7 20:55:56 标签: 算法, c++, 数据结构, c语言, 快速幂

分析:v9=999999999

vn=输出n个n

先算出n的位数p

所以答案是n+n*10的p次方+n*10的2p次方+.....+n*10的(n-1)p次方

化简n*(10的0次方+10的p次方+10的2p次方+.....+10的(n-1)p次方)

后面为等比数列求和 公比为10的p次方 首相是1

节省点写法把10的p次方为p

答案是n*(p的n次方-1)/(p-1)

快速幂的板子

ll qpow2(ll a,ll b,ll p){//a的b次方%mod
    ll base=a;
    ll res=1;
    while(b){
            if(b&1)res=(res*base)%p;
            base=(base*base)%p;
            b>>=1;
    }
    return res%p;
}

有除法 就用逆元

逆元的板子

ll inv(ll a,ll b)//a/b%mod
{
    return (a*qpow2(b,mod-2,mod))%mod;
}

一整合

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;

ll qpow2(ll a,ll b,ll p){
    ll base=a;
    ll res=1;
    while(b){
            if(b&1)res=(res*base)%p;
            base=(base*base)%p;
            b>>=1;
    }
    return res%p;
}


//逆元函数 公式为 (a/b)%mod=(a*b^(mod-2))%mod
//逆元
ll inv(ll a,ll b)
{
    return (a*qpow2(b,mod-2,mod))%mod;
}

int main(){
    ll n;cin>>n;
    ll p=1,x=n;
    while(x>0){
        x/=10;
        p*=10;
        p%=mod;
    }
    ll ans=n%mod;
    ans=(ans*(qpow2(p,n,mod)-1))%mod;
    ans=inv(ans,p-1)%mod;
    cout<<ans<<endl;
    return 0;
}


http://www.niftyadmin.cn/n/5535224.html

相关文章

前端三件套开发模版——产品介绍页面

今天有空&#xff0c;使用前端三件套html、css、js制作了一个非常简单的产品制作页面&#xff0c;与大家分享&#xff0c;希望可以满足大家应急的需求。本页面可以对产品进行“抢购”、对产品进行介绍&#xff0c;同时可以安排一张产品的高清大图&#xff0c;我也加入了页面的背…

数据结构底层之HashMap(面经篇1)

1 . 讲一下hashmap的数据结构 HashMap是一种基于哈希表实现的数据结构&#xff0c;通常用于关联键值对&#xff0c;其中键是唯一的&#xff0c;而值可以重复。在Java中&#xff0c;HashMap是java.util.Map接口的一个实现&#xff0c;它提供了快速的查找、插入和删除操作。 数据…

Ueditor中集成135编辑器

一、背景 在资讯项目平台运营过程中&#xff0c;资讯需要排版&#xff0c;一般都是在135编辑器排好以后&#xff0c;复制到平台中UEditor编辑器中&#xff0c;所以&#xff0c;他们建议集成一下135哈 二、了解135编辑器 开始调研了解135编辑器&#xff0c;发现人家就支持集成…

HarmonyOS ArkUi Tabs+TabContent+List实现tab吸顶功能

Demo效果 Entry Component struct StickyNestedScroll {State message: string Hello WorldState arr: number[] []scroller new Scroller()StyleslistCard() {.backgroundColor(Color.White).height(72).width("100%").borderRadius(12)}build() {Scroll(this.sc…

记录通过Cloudflare部署属于自己的docker镜像源

引言 由于最近国内无法正常拉取docker镜像&#xff0c;然而找了几个能用的docker镜像源发现拉取回来的docker镜像不是最新的版本&#xff0c;部署到Cloudflare里Workers 和 Pages&#xff0c;拉取docker 镜像成功&#xff0c;故记录部署过程。 部署服务 登录Cloudflare后&…

深入学习索引

1.索引的底层数据结构是什么&#xff1f;索引是如何实现的&#xff1f; 索引的底层数据结构是Btree(多路树) 当设置了字段为索引以后&#xff0c;底层会将字段上的数据使用BTree的数据结构存储在索引文件里 2.索引的优缺点 优点&#xff1a;索引字段作为条件查询更快 缺点&…

【字符串处理】【双指针】个人练习-Leetcode-777. Swap Adjacent in LR String

题目链接&#xff1a;https://leetcode.cn/problems/swap-adjacent-in-lr-string/description/ 题目大意&#xff1a;给两个字符串start, end&#xff0c;只包含XLR三种字符。可以进行一次操作将XL转换成LX或者将RX转换为XR&#xff0c;返回是否存在方法使得start能转换成end …

HX4004A-MFC 低噪声、稳压电荷泵DC/DC转换器芯片IC

一般描述 该HX4004A是一个低噪声开关电容电压倍。它产生一个调节输出电压从2.7V到4.5V的输入。低的外部零件数量(VIN和VOUT处一个飞行电容和两个小型旁路电容)使HX4004A非常适合小型电池供电应用。 该HX4004A具有热关断能力&#xff0c;可以生存从VOUT到GND的连续…