結果

問題 No.528 10^9と10^9+7と回文
ユーザー IL_mstaIL_msta
提出日時 2017-06-10 01:39:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 8 ms / 1,000 ms
コード長 2,890 bytes
コンパイル時間 1,014 ms
コンパイル使用メモリ 106,168 KB
実行使用メモリ 8,828 KB
最終ジャッジ日時 2024-07-23 18:31:32
合計ジャッジ時間 2,007 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 8 ms
8,708 KB
testcase_11 AC 7 ms
8,708 KB
testcase_12 AC 7 ms
8,708 KB
testcase_13 AC 8 ms
8,700 KB
testcase_14 AC 5 ms
6,944 KB
testcase_15 AC 5 ms
6,940 KB
testcase_16 AC 5 ms
6,944 KB
testcase_17 AC 4 ms
6,944 KB
testcase_18 AC 7 ms
8,540 KB
testcase_19 AC 3 ms
6,948 KB
testcase_20 AC 6 ms
6,948 KB
testcase_21 AC 4 ms
6,940 KB
testcase_22 AC 1 ms
6,944 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 8 ms
8,828 KB
testcase_27 AC 7 ms
8,708 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18;
const double PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

//string str;
char str[100010];
void solve(){
	LL mod1 = 1000000000;
			///123456789
	LL mod2 = MOD;
	
	cin >> str;
	//const int size = str.size();
	const int size = strlen(str);
	
	//全ての数字を使えるとき,dp[i]:=i桁の回文の個数
	vector< LL > dpALL1(size+1,0);
	vector< LL > dpALL2(size+1,0);
	dpALL1[1] = 9;
	dpALL2[1] = 9;
	for(int i=2;i<=size;++i){
		LL res1 = dpALL1[i-1];
		LL res2 = dpALL2[i-1];
		if( i&1 ){//中央に数字を加える。
			res1 *= 10;
			res2 *= 10;
		}/*else{//中央の数字をコピーする
		}*/
		dpALL1[i] = res1 % mod1;
		dpALL2[i] = res2 % mod2;
	}
	
	//1桁少ない場合
	LL ans1 = 0;
	LL ans2 = 0;
	for(int i=1;i<size;++i){
		ans1 = (ans1 + dpALL1[i]) % mod1;
		ans2 = (ans2 + dpALL2[i]) % mod2;
	}

	//size桁全て使う場合
	vector< vector< LL > > dp1(2,vector<LL>(size,0));
	vector< vector< LL > > dp2(2,vector<LL>(size,0));
	LL res1,res2;
	
	const int mid = size/2 + (size&1);
	//size桁の小さい値だけカウント
	for(int i=0;i<mid;++i){
		int L = str[i]-'0';
		int R = str[size-1-i]-'0';
		int MIN = min(L,R);
		
		if(i==0){
			dp1[1][i] = L-1;
			dp2[1][i] = L-1;
		}else{
			dp1[1][i] = dp1[1][i-1]*10 + L;
			dp1[1][i] %= mod1;
			
			dp2[1][i] = dp2[1][i-1]*10 + L;
			dp2[1][i] %= mod2;
		}
	}
	//最大値が回文
	LL flag1 = 1;
	LL flag2 = 1;
	int L,R;
	if( size&1 ){//奇数文字
		L = size/2;
		R = L;
	}else{//偶数文字
		L = size/2 -1;
		R = L+1;
	}
	for(int i=0;i<=size/2; ++i,--L,++R){
		if( str[L] > str[R] ){
			flag1 = 0;
			flag2 = 0;
			break;
		}else if( str[L] < str[R] ){
			break;
		}
	}
	res1 = (dp1[1][mid-1] + flag1);
	ans1 = (ans1 + res1) % mod1;
	
	res2 = (dp2[1][mid-1] + flag2);
	ans2 = (ans2 + res2) % mod2;

	cout << ans1 << endl;
	cout << ans2 << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	
	
	solve();
}
#pragma endregion //main()
0