結果

問題 No.528 10^9と10^9+7と回文
ユーザー 14番
提出日時 2017-06-10 00:16:09
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 3,847 bytes
コンパイル時間 2,201 ms
コンパイル使用メモリ 109,196 KB
実行使用メモリ 210,520 KB
最終ジャッジ日時 2024-09-22 20:51:24
合計ジャッジ時間 4,136 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;

public class Program
{

    public void Proc()
    {
        this.Target = Reader.ReadLine();
        long[] ans = new long[2];
        for (int i = 1; i <= this.Target.Length; i++) {
            long[] tmp = GetAns(i, true);
            ans[0] += tmp[0];
            ans[1] += tmp[1];
            ans[0] = ans[0] % ModZero;
            ans[1] = ans[1] % Mod;
        }
        Console.WriteLine(ans[0]);
		Console.WriteLine(ans[1]);

	}

    private Dictionary<int, Dictionary<bool, long[]>> dic = new Dictionary<int, Dictionary<bool, long[]>>();


    private string Target;

    private bool IsBigger(string num) {
        if(num.Length > Target.Length) {
            return true;
        }
        if(num.Length < Target.Length) {
            return false;
        }
        for (int i = 0; i < num.Length; i++) {
            if(num[0]>Target[0]) {
                return true;
            }
            if(num[0]<Target[0]) {
                return false;
            }
        }
        return false;
    }

    private long[] GetAns(int keta, bool rmZero) {
        if(!dic.ContainsKey(keta)) {
            dic.Add(keta, new Dictionary<bool, long[]>());
        }
        if(dic[keta].ContainsKey(rmZero)) {
            return dic[keta][rmZero];
        }

        if(keta == 1) {
            if(Target.Length == 1) {
                int tmp = int.Parse(Target);
                return new long[] { tmp, tmp };
            }
            if(rmZero) {
                return new long[] { 9, 9 };
            }
            return new long[] { 10, 10 };
        }
        if(keta == 2) {
            if(Target.Length == 2) {
                int tmp = int.Parse(Target);
                int cnt = 0;
                for (int i = 1; i * 11 <= tmp; i++) {
                    cnt++;
                }
                return new long[] { cnt, cnt };
            }
            if(rmZero) {
                return new long[] { 9, 9 };
            }
            return new long[] { 10, 10 };
        }
        long[] baseNum = GetAns(keta - 2, false).ToArray();
        long[] ans = new long[2];
        if(keta < this.Target.Length) {
            if(rmZero) {
                ans[0] = baseNum[0] * 9;
                ans[1] = baseNum[1] * 9;
            } else {
				ans[0] = baseNum[0] * 10;
				ans[1] = baseNum[1] * 10;
			}
        } else {
            ans = GetTargetSmallerNum(0);
        }
        ans[0] = ans[0] % ModZero;
        ans[1] = ans[1] % Mod;
        dic[keta][rmZero] = ans;
        return ans;
    }

    private long[] GetTargetSmallerNum(int idx) {
        if (idx >= Target.Length) {
            return new long[] { 0, 0 };
        }
        int num = int.Parse(Target[idx].ToString());

        int keta = Target.Length - idx - 1;

        long[] tmp = new long[2];
        if(num>=1) {
            tmp = GetAns(keta, false).ToArray();
			tmp[0] *= (num - 1);
			tmp[1] *= (num - 1);
		}
        long[] tmp2 = GetTargetSmallerNum(idx + 1).ToArray();
        long[] ans = new long[] { tmp[0] + tmp2[0], tmp[1] + tmp2[1] };
        ans[0] = ans[0] % ModZero;
        ans[1] = ans[1] % Mod;
        return ans;
    }

    private long ModZero = 1000000000;
    private long Mod = 1000000000 + 7;

    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"




1000000000000000000000000000000








";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}
0