当前位置:网站首页>洛谷P4127 [AHOI2009]同类分布 题解
洛谷P4127 [AHOI2009]同类分布 题解
2022-07-06 07:23:00 【q779】
洛谷P4127 [AHOI2009]同类分布 题解
题目链接:P4127 [AHOI2009]同类分布
题意:
给出两个数 a , b a,b a,b ,求出 [ a , b ] [a,b] [a,b] 中各位数字之和能整除原数的数的个数。
对于所有的数据, 1 ≤ a ≤ b ≤ 1 0 18 1 ≤ a ≤ b ≤ 10^{18} 1≤a≤b≤1018。
明天就期末考了非但不复习还在刷题 qwqqwqwq
因为我们不能确切知道每个数的数位和
但是我们知道它们一定在 [ 1 , 9 × l ] [1,9 \times l] [1,9×l] 的范围内( l l l 为最长的位数)
我们枚举所有的数位和并计算每个数位和对应的答案
把这些答案加起来就是 [ 0 , x ] [0,x] [0,x] 的答案
[ a , b ] [a,b] [a,b] 的答案可以拆分为两个询问 [ 0 , b ] [0,b] [0,b] 和 [ 0 , a − 1 ] [0,a-1] [0,a−1]
而这里 a , b ≤ 1 0 18 a,b \le 10^{18} a,b≤1018 ,直接压入状态显然不可接受
于是我们可以考虑记录模当前枚举的数位和意义下的数
方便起见,我们称当前枚举的数位和为 m m m
设 f i , j , k f_{i,j,k} fi,j,k 表示只考虑前 i i i 位数(包括前导零),前 i i i 位的数位和为 j j j ,当前数模 m m m 为 k k k 时的答案
不难发现
f i , j , k = ∑ 0 ≤ d ≤ t f i + 1 , j + d , ( k × 10 + d m o d m ) f_{i,j,k} = \sum_{0 \le d \le t} f_{i+1,j+d,\left(k\times 10 + d \, \bmod \, m\right)} fi,j,k=0≤d≤t∑fi+1,j+d,(k×10+dmodm)
其中 t t t 为第 i + 1 i+1 i+1 位的高位限制
用记搜写法能简洁不少
时间复杂度 O ( 9 3 × l 4 ) O(9^3\times l^4) O(93×l4)
代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()
int len,num[25],f[25][205][205];
int dfs(int u,int sum,int st,int limit,int p)
{
if(u>len)
{
if(!sum)return 0;
return st==0&&sum==p;
}
if(!limit&&f[u][sum][st]!=INF)
return f[u][sum][st];
int up=limit?num[len-u+1]:9;
int res=0;
for(int i=0; i<=up; i++)
res+=dfs(u+1,sum+i,(10*st+i)%p,limit&&i==up,p);
return limit?res:f[u][sum][st]=res;
}
int solve(int x)
{
int res=0; len=0;
while(x) num[++len]=x%10,x/=10;
for(int m=1; m<=9*len; m++)
{
memset(f,0x3f,sizeof(f));
res+=dfs(1,0,0,1,m);
}
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int l,r; cin >> l >> r;
cout << solve(r)-solve(l-1) << '\n';
return 0;
}
没事反正whk暂时开摆了
转载请说明出处
边栏推荐
- Fundamentals of C language 9: Functions
- Twelve rules for naming variables
- How to configure GUI guide development environment
- 位运算异或
- Supervisor usage document
- Jerry's general penetration test - do data transmission with app Communication [article]
- Ble of Jerry [chapter]
- Emo diary 1
- leetcode704. Binary search (find an element, simple, different writing)
- Mise en œuvre du langage leecode - C - 15. Somme des trois chiffres - - - - - idées à améliorer
猜你喜欢
Twelve rules for naming variables
Babbitt | metauniverse daily must read: the group image of Chinese Internet enterprises pouring into metauniverse: "there are only various survival desires, and there is no ambition for forward-lookin
杰理之AD 系列 MIDI 功能说明【篇】
Ble of Jerry [chapter]
Cookie技术&Session技术&ServletContext对象
Go learning -- implementing generics based on reflection and empty interfaces
The author is dead? AI is conquering mankind with art
MVVM of WPF
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Lesson 12 study notes 2022.02.11
随机推荐
[dictionary tree] [trie] p3879 [tjoi2010] reading comprehension
Multithreading and concurrent programming (2)
Mise en œuvre du langage leecode - C - 15. Somme des trois chiffres - - - - - idées à améliorer
On the world of NDK (2)
Fundamentals of C language 9: Functions
CF1036C Classy Numbers 题解
#systemverilog# 可綜合模型的結構總結
多线程和并发编程(二)
C - Inheritance - hidden method
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Ble of Jerry [chapter]
Internal and external troubles of "boring ape" bayc
Redis builds clusters
杰理之开发板上电开机,就可以手机打开 NRF 的 APP【篇】
The first Baidu push plug-in of dream weaving fully automatic collection Optimization SEO collection module
(4) Web security | penetration testing | network security web site source code and related analysis
mysql如何合并数据
Go learning --- use reflection to judge whether the value is valid
[online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code
Related operations of Excel