吉哥系列故事——恨7不成妻 数位dp

2023-11-07 00:20
文章标签 dp 系列 故事 数位 吉哥

本文主要是介绍吉哥系列故事——恨7不成妻 数位dp,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  单身!
  依然单身!
  吉哥依然单身!
  DS级码农吉哥依然单身!
  所以,他生平最恨情人节,不管是214还是77,他都讨厌!
  
  吉哥观察了214和77这两个数,发现:
  2+1+4=7
  7+7=7*2
  77=7*11
  最终,他发现原来这一切归根到底都是因为和7有关!所以,他现在甚至讨厌一切和7有关的数!

  什么样的数和7有关呢?

  如果一个整数符合下面3个条件之一,那么我们就说这个整数和7有关——
  1、整数中某一位是7;
  2、整数的每一位加起来的和是7的整数倍;
  3、这个整数是7的整数倍;

  现在问题来了:吉哥想知道在一定区间内和7无关的数字的平方和。

 

Input
输入数据的第一行是case数T(1 <= T <= 50),然后接下来的T行表示T个case;每个case在一行内包含两个正整数L, R(1 <= L <= R <= 10^18)。

 

Output
请计算[L,R]中和7无关的数字的平方和,并将结果对10^9 + 7 求模后输出。

 

Sample Input
3 1 9 10 11 17 17

 

Sample Output
236 221 0
我连怎么求和都没想出来   
参考了kuangbin大佬的题解
如果要维护和的话:
当前个数乘其 10^pos 即可
维护和的话用平方和公式

(pre*10^pos + next)^2= (pre*10^pos)^2+2*pre*10^pos*next +next^2

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
//
const long long MOD=1000000007LL;
struct Node
{long long cnt;//与7无关的数的个数long long sum;//与7无关的数的和long long sqsum;//平方和
}dp[20][10][10];//分别是处理的数位、数字和%7,数%7
int bit[20];
long long p[20];//p[i]=10^i

Node dfs(int pos,int pre1,int pre2,bool flag)
{if(pos==-1){Node tmp;tmp.cnt=(pre1!=0 && pre2!=0);tmp.sum=tmp.sqsum=0;return tmp;}if(!flag && dp[pos][pre1][pre2].cnt!=-1)return dp[pos][pre1][pre2];int end=flag?bit[pos]:9;Node ans;Node tmp;ans.cnt=ans.sqsum=ans.sum=0;for(int i=0;i<=end;i++){if(i==7)continue;tmp=dfs(pos-1,(pre1+i)%7,(pre2*10+i)%7,flag&&i==end);ans.cnt+=tmp.cnt;ans.cnt%=MOD;ans.sum+=(tmp.sum+ ((p[pos]*i)%MOD)*tmp.cnt%MOD )%MOD;ans.sum%=MOD;ans.sqsum+=(tmp.sqsum + ( (2*p[pos]*i)%MOD )*tmp.sum)%MOD;ans.sqsum%=MOD;ans.sqsum+=( (tmp.cnt*p[pos])%MOD*p[pos]%MOD*i*i%MOD );ans.sqsum%=MOD;}if(!flag)dp[pos][pre1][pre2]=ans;return ans;
}
long long calc(long long n)
{int pos=0;while(n){bit[pos++]=n%10;n/=10;}return dfs(pos-1,0,0,1).sqsum;
}
int main()
{int T;long long l,r;p[0]=1;for(int i=1;i<20;i++)p[i]=(p[i-1]*10)%MOD;for(int i=0;i<20;i++)for(int j=0;j<10;j++)for(int k=0;k<10;k++)dp[i][j][k].cnt=-1;scanf("%d",&T);while(T--){scanf("%I64d%I64d",&l,&r);long long ans=calc(r);ans-=calc(l-1);ans=(ans%MOD+MOD)%MOD;printf("%I64d\n",ans);}return 0;
}
View Code

 

转载于:https://www.cnblogs.com/bxd123/p/10974247.html

这篇关于吉哥系列故事——恨7不成妻 数位dp的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]

uva 10118 dP

题意: 给4列篮子,每次从某一列开始无放回拿蜡烛放入篮子里,并且篮子最多只能放5支蜡烛,数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时,猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs

uva 10069 DP + 大数加法

代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl