結果

問題 No.492 IOI数列
コンテスト
ユーザー fiord
提出日時 2017-03-11 01:03:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,056 bytes
コンパイル時間 636 ms
コンパイル使用メモリ 69,924 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-24 09:25:01
合計ジャッジ時間 1,321 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/*
	ai=100a(i-1)+1	->	ai+(1/99)=100(a(i-1)+1/99)
	ai=-1/99+100/99*(100)^(i-1)
	  ={(100)^i-1}/99

	1e9+7は(100)^n(mod m)を算出して1を引き、99の逆元をかければOK
	a11は	n(mod 11)		an(mod a11)
			0				0
			1				1
			2				101
			3				10101
			4				1010101
			5				101010101
			6				10101010101
			7				1010101010101
			8				101010101010101
			9				10101010101010101
			10				1010101010101010101
*/
typedef long long ll;
ll mod = 1000000007;
ll solve1(ll n) {
	//(100)^n(mod m)
	ll ret = 1;
	ll multi = 100;
	while (n) {
		if (n & 1)	ret = (ret*multi) % mod;
		n >>= 1;
		multi = (multi*multi) % mod;
	}
	//-1
	ret = (ret + mod - 1) % mod;
	//99の逆元=99^(mod-2)
	multi = 99;
	n = mod - 2;
	while (n) {
		if (n & 1)	ret = (ret*multi) % mod;
		n >>= 1;
		multi = (multi*multi) % mod;
	}
	return ret;
}

int main() {
	ll n;	cin >> n;
	cout << solve1(n) << endl;
	n %= 11;
	ll a = 0;
	for (int i = 0; i < n; i++)	a = a * 100 + 1;
	cout << a << endl;
	return 0;
}
0