[hdu 4933]Miaomiao's Function 数位DP+大数
发布时间：2020-12-14 03:05:21 所属栏目：大数据 来源：网络整理
导读：Miaomiao's Function Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 79????Accepted Submission(s): 18 Problem Description Firstly,Miaomiao define two functions f(x),g(x): (K is the sm
Miaomiao's FunctionTime Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 79????Accepted Submission(s): 18
Problem Description
Firstly,Miaomiao define two functions f(x),g(x):
(K is the smallest integer which satisfied x + 9 * K > 0) if?
For example f(20140810) = f(2 + 0 + 1 + 4 + 0 + 8 + 1 + 0) = f(16) = f(1 + 6) = f(7) = 7 Then,you are given two integers L,R( L <= R) .? Answer is defined as?
Please caculate (Answer Mod f(Answer) + f(Answer)) Mod f(Answer). Pay attantion ! If f(Answer) = 0,please output "Error!"
?
Input
There are many test cases. In the first line there is a number T ( T <= 50 ) shows the number of test cases.
For each test cases there are two numbers L,R ( 0 <= L,R <= 10^100 ). For your Information,L,R don't have leading zeros.
?
Output
For each opeartion,output the result.
?
Sample Input
?
Sample Output
?
题源为 bestcoder #4 C题 题目大意? 给出L,R，询问[L,R]之中所有数的交错和之和，交错和的定义为?
给定一个数?x，设它十进制展从高位到低位上的数位依次是?a0,?a1,?...,?an?-?1，定义交错和函数： f(x)?=?a0?-?a1?+?a2?-?...?+?(?-?1)n?-?1an?-?1 其实就是hihocoder 1033的题目并将ans做一个模处理 解题思路 这一题的方法和hihocoder 1033完全一致，推不出公式就写了记忆化dfs+java大数…… 注意最后的结果可能有0和9两种 所以直接对九取模就会造成答案模数的Error变为0 特判即可 code:
import java.util.*;
import java.math.*;
public class Main
{
static class node
{
public BigInteger s=BigInteger.ZERO,n=BigInteger.ZERO;
}
public static int top=0,bn=0;
public static node[] dp=new node[105];
public static int[] bt=new int[105];
public static node dfs(int pos,int limit)
{
node tmp = new node();
tmp.s=BigInteger.ZERO;
tmp.n=BigInteger.ZERO;
if (pos==0) {
tmp.s=BigInteger.ZERO;
tmp.n=BigInteger.ONE;
return tmp;
}
if (limit==0&&(!dp[pos].n.equals(BigInteger.ZERO))) return dp[pos];
int head=(pos==top)?1:0;
int tail=(limit==1)?bt[pos]:9;
for (int i=head;i<=tail;i++)
{
node s= dfs(pos-1,(limit==1&&bt[pos]==i)?1:0);
tmp.n=tmp.n.add(s.n);
tmp.s=tmp.s.add(s.s);
if ((top-pos)%2==0)
tmp.s=tmp.s.add((s.n).multiply(BigInteger.valueOf(i)));
else
tmp.s=tmp.s.add((s.n).multiply(BigInteger.valueOf(-i)));
}
if (limit==0) dp[pos]=tmp;
return tmp;
}
public static BigInteger f(BigInteger x)
{
BigInteger ans=BigInteger.ZERO;
if (x.equals(BigInteger.ZERO)) return ans;
if (x.equals(BigInteger.valueOf(-1))) return ans;
bn=0;
while (!x.equals(BigInteger.ZERO))
{
bn++;
bt[bn]=x.mod(BigInteger.valueOf(10)).intValue();
x=x.divide(BigInteger.valueOf(10));
}
for (top=1;top<=bn;top++)
{
for (int i=1;i<=104;i++){
dp[i]=new node();
dp[i].s=BigInteger.ZERO;
dp[i].n=BigInteger.ZERO;
}
ans=ans.add(dfs(top,(top==bn)?1:0).s);
}
return ans;
}
public static BigInteger g(BigInteger x)
{
BigInteger t=BigInteger.ZERO;
BigInteger p=x;
if (x.equals(BigInteger.ZERO)) return x;
if (x.compareTo(BigInteger.valueOf(0))<0)
if (x.mod(BigInteger.valueOf(9)).equals((BigInteger.valueOf(0))))
return(BigInteger.valueOf(9));
else return (g(x.multiply(BigInteger.valueOf(-8))));
if (x.mod(BigInteger.valueOf(9)).equals(BigInteger.ZERO))
return BigInteger.valueOf(9);
else return x.mod(BigInteger.valueOf(9));
}
public static void main(String [] args)
{
Scanner in=new Scanner(System.in);
int T=in.nextInt();
while (T--!=0)
{
BigInteger L=in.nextBigInteger();
BigInteger R=in.nextBigInteger();
BigInteger ans=f(R).add(f(L.add((BigInteger.valueOf(-1)))).negate());
BigInteger t=g(ans);
if (t.equals(BigInteger.valueOf(0)))
System.out.println("Error!");
else System.out.println((ans.mod(t).add(t)).mod(t));
}
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
