結果

問題 No.528 10^9と10^9+7と回文
ユーザー IL_msta
提出日時 2017-06-09 23:52:48
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,719 bytes
コンパイル時間 918 ms
コンパイル使用メモリ 106,700 KB
実行使用メモリ 8,964 KB
最終ジャッジ日時 2024-09-22 20:20:26
合計ジャッジ時間 1,890 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 19
権限があれば一括ダウンロードができます

ソースコード

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;

void solve(){
	LL mod1 = 1000000000;
			///123456789
	LL mod2 = MOD;
	string str;
	cin >> str;
	const int size = str.size();
	
	//全ての数字を使えるとき,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);
	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( MIN < L ){
			dp1[0][i] = 0;dp2[0][i] = 0;
		}else{
			dp1[0][i] = 1;dp2[0][i] = 1;
		}
		if(i==0){
			dp1[1][i] = L-1;dp2[1][i] = L-1;
		}else{
			dp1[1][i] = dp1[1][i-1]*10 + L*dp1[0][i-1];
			dp1[1][i] %= mod1;
			
			dp2[1][i] = dp2[1][i-1]*10 + L*dp2[0][i-1];
			dp2[1][i] %= mod2;
		}
	}
	int flag1 = 1;
	int flag2 = 1;
	for(int i=0;i<mid;++i){
		if( str[i] > str[size-1-i] ){
			flag1 = 0;
			flag2 = 0;
			break;
		}
	}
	res1 = (flag1 + dp1[1][mid-1]);
	ans1 = (ans1 + res1) % mod1;
	res2 = (flag2 + dp2[1][mid-1]);
	ans2 = (ans2 + res1) % 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