【HDU4507】【吉哥系列故事——恨7不成妻】【变形数位dp】

2024-08-31 16:58

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


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

Time Limit: 1000/500 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2260    Accepted Submission(s): 660


Problem Description
单身!
  依然单身!
  吉哥依然单身!
  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

Source
2013腾讯编程马拉松初赛第一场(3月21日)

Recommend
liuyiding

这题就难在sqsum的计算上,其实也很简单的啦。

sum{i*p[pos] + $} ^2  = sum{i^2 * p[pos] ^ 2} + sum{2 * i * p[pos] *$} + sum{$ ^ 2} = cnt * i ^ 2*p[pos] ^2 +  2*i * p[pos] * sum + sqsum


#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;int T;
const long long  MOD = 1e9 + 7LL;
typedef long long ll;
ll p[30];
int bits[20];
struct Node
{ll cnt,sum,sqsum;
}dp[20][10][10];Node dfs(int len,int pre1,int pre2,bool flag)/*pre1 是数本身的和pre2是位的和*/
{if(len <= 0){Node n;n.cnt = (pre1!=0 && pre2!=0);n.sum = n.sqsum = 0;return n;}	if(!flag && dp[len][pre1][pre2].cnt!=-1) return dp[len][pre1][pre2];int end = flag ? bits[len] : 9;Node ans;ans.cnt = ans.sum = ans.sqsum = 0;for(int i=0;i<=end;i++){if(i == 7) continue;Node n = dfs(len-1,(pre1*10+i)%7,(pre2+i)%7,flag&&i==end);ans.cnt += n.cnt;ans.cnt %= MOD;ans.sum += (n.sum + ((i * p[len-1]) % MOD * n.cnt) % MOD) % MOD;ans.sum %= MOD;ans.sqsum += n.sqsum + ((((2 * n.sum) %MOD * p[len-1]) % MOD) * i) % MOD;ans.sqsum %= MOD;ans.sqsum += ((((n.cnt * i) % MOD * i) %MOD * p[len-1]) % MOD * p[len-1])% MOD;ans.sqsum %= MOD;}return flag ? ans : dp[len][pre1][pre2] = ans;
}ll solve(ll x)
{int c = 0;ll tt = x;while(tt > 0){bits[++c] = tt % 10;tt /= 10;}return dfs(c,0,0,true).sqsum % MOD;
}int main()
{p[0] = 1;for(int i=1;i<=20;i++){p[i] = p[i-1] * 10 % MOD;} scanf("%d",&T);while(T --){ll l,r;scanf("%I64d%I64d",&l,&r);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;}}}printf("%I64d\n",(solve(r) - solve(l-1) + MOD) % MOD);}return 0;
}


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



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

相关文章

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

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

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

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

hdu3389(阶梯博弈变形)

题意:有n个盒子,编号1----n,每个盒子内有一些小球(可以为空),选择一个盒子A,将A中的若干个球移到B中,满足条件B  < A;(A+B)%2=1;(A+B)%3=0 这是阶梯博弈的变形。 先介绍下阶梯博弈: 在一个阶梯有若干层,每层上放着一些小球,两名选手轮流选择一层上的若干(不能为0)小球从上往下移动,最后一次移动的胜出(最终状态小球都在地面上) 如上图所示,小球数目依次为

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]