首页 > 其他分享 >CF327C Magic Five 题解

CF327C Magic Five 题解

时间:2024-01-23 15:24:13浏览次数:37  
标签:qpow CF327C 题解 ll pos len Five ans mod

CF327C Magic Five

搬运工
单调队列优化DP加等比数列求和
首先 \(5\) 的倍数要求末尾是 \(0\) 或 \(5\) 所以我们只用看给定字符串的 \(0\) 和 \(5\) 就好,我们钦定他是最终的数的末尾。
在他之前的选择删掉,在他之后的全部删掉,方案数就是 \(2^{pow-1}\),答案累加就可以了。
容易想到一个朴素的,每次找到后,循环 \(n\) 遍,\(ans=\sum^{len}_{pos}{\sum_{k=0}^{n-1} {2^{pos+k\cdot len-1}}}\),这样复杂度 \(O(nm)\),肯定不行。
不难看出上面的式子是一个等比数列,直接求和就行,最终式子是

\[ans=\sum^{len}_{pos}k\cdot 2^{pos-1} \]

k是系数,提前处理出来就好,\(k=\dfrac{2^{len\cdot n}-1}{2^{len}-1}\) 然后就做完了。

#include<bits/stdc++.h>
#define ll long long
const ll mod=1e9+7,N=1e5+5;
char s[N];
ll ans,len,ny,n,xs;
inline ll qpow(ll a,ll b){
    ll ans=1;
    for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
    return ans;
}
int main(){
    // freopen("in.in","r",stdin),freopen("out.out","w",stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),std::cout.tie(0);
    std::cin>>s+1>>n;
    len=strlen(s+1);
    ll k=qpow(2,len);
    ny=qpow(k-1,mod-2);
    xs=(qpow(k,n)-1)*ny%mod;
    for(int i=1;i<=len;++i)
        if(s[i]=='0'||s[i]=='5')
            ans=(ans+xs*qpow(2,i-1)%mod)%mod;
    std::cout<<ans<<'\n';
}

取模放括号里死活没看出来。

标签:qpow,CF327C,题解,ll,pos,len,Five,ans,mod
From: https://www.cnblogs.com/Ishar-zdl/p/17982557

相关文章

  • P2254 [NOI2005] 瑰丽华尔兹 题解
    P2254[NOI2005]瑰丽华尔兹搬运工单调队列优化DP还是先朴素,设\(f_{t\i\j\d}\)表示在第\(t\)个时刻,在\(i,j\)位置上,上一步是停留还是滑动的最大步数。这个就是四个方向随便转移。\(T_{max}=4*10^4\)这么做肯定不行。发现\(k\)很小,只有\(200\),所以不妨让\(k\)......
  • P2569 [SCOI2010] 股票交易 题解
    P2569[SCOI2010]股票交易搬运工稍微复杂一点的单调队列优化DP直接设\(f_{i\j}\)表示在第\(i\)天,手上还剩\(j\)个股票时的最大收入。容易写出状态转移方程:\(f_{i\j}=max\{f_{k\t}+(t-j)\cdotw\}\),这样不好看,我们可以拆成这样的形式:\[f_{i\j}=max\{f_{k\t}+t\cdo......
  • P4899 [IOI2018] werewolf 狼人 题解
    因为我记忆力不好,经常遇到之前做过的题一下子想不起来,所以打算基本上给每个比较有意思的题写题解,同时造福后代。这是werewolf,它是furry,很可爱题意:一张无向图,点有点权,每次询问从\(u\)到\(v\)的路径中,是否存在一条先走点权大于等于\(L\),再走点权小于等于\(R\)的路径。思路......
  • dbt-language-server fivetran 提供的dbt 语言工具
    dbt-language-serverfivetran提供的dbt语言工具包含的特性查询预览sqltoref的转换异常高光自动完成函数签名帮助跳转定义dbt状态创建dbt项目安装dbt包说明对于基于dbt进行是数据建模的,dbt-language-server是一个很值得尝试的工具参考资料https://github......
  • hugeの张江蔡唐氏模拟赛题解
    晚三huge不让去一机房,说便于管理,我的评价是:唐氏况且二机房没有luogu,改完题后没事干(指写不了狼人),遂写个没人看的题解。T1纯哈希,不写。T2纯tarjan,一直没学,不写。T3比较套路的双指针,赛时降智题意:给定由\(B\)和\(R\)组成的字符串,环形结构,每次可以交换相邻,问最少多少次可以......
  • 01.22 ARC170 题解慢报
    补完了,来发题解慢报。AB就不写了。CPrefixMexSequence考虑DP,\(f(i,j)\)表示前\(i\)个数,填了\(j\)个不同的数。如果\(s_{i+1}=1\)那么这位唯一确定,只需要保证\(j<m\)即可转移到\(f(i+1,j+1)\);如果\(s_{i+1}=0\)那么可以选旧的数也可以选新的数,分别转移即可。D......
  • 「Daily OI Round 1」block 题解
    设\(c_u\)表示节点\(u\)的颜色,\(f_u\)表示只考虑原树中\(u\)的子树中的点、选择点\(u\)的方案数。对于儿子\(v\),可以选择同色儿子节点,也可以跳过这个儿子节点,选择\(v\)的与\(u\)同色的儿子节点\(w\),故状态转移方程为:\[f_u=\prod[c_u=c_v]f_v+\left(\prod[c_u=c_w]......
  • CF1424M Ancient Language 题解
    1.题意描述一本字典中有\(r\)\((1\leqr\leq10^6)\)个单词,单词长度不超过$10^3$,所有字母都是小写英文字母,但字母排序不是按英文字母排序,求所有出现字母的一种排序,如果不存在,输出"IMPOSSIBLE"。2.题目分析由排序规则可知,对于字符串\(s\)和\(t\),\(s\)排在\(t\)......
  • CF618C Constellation 题解
    题意描述给定\(n\)个点(\(n\leq10^5\)),找到三个点满足这三个点不在同一直线上且三个点构成的三角形中不包含其他点,保证所有点不会在同一直线上。题目分析首先必然每一个点都可以作为一组解中的点。不妨其中一个点编号为\(1\)。找一个点作为第二个点,为了使没有点在这条边上,这......
  • CF1036F Relatively Prime Powers 题解
    题目分析对于一个不合法的数\(x(x\ge2)\),设\(x=\prodp_i^{r_i}\),令\(g=\gcd(r_1,r_2,\ldots,r_k)\),则\(x=\left(\prodp_i^{r_i/g}\right)^g\),所以\(x\)是一个正整数的\(g\)次方。所以可以枚举上文的\(g\),把每一类不合法方案排除掉,就是答案。设\(f(i)\)表示\(2\)......