結果

問題 No.435 占い(Extra)
コンテスト
ユーザー koyumeishi
提出日時 2016-04-19 06:12:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,284 bytes
コンパイル時間 1,602 ms
コンパイル使用メモリ 115,932 KB
実行使用メモリ 22,656 KB
最終ジャッジ日時 2024-10-08 11:17:56
合計ジャッジ時間 7,596 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other WA * 13 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
using namespace std;

namespace {
	using Integer = long long; //__int128;
	template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
	template<class T> istream& operator ,  (istream& is, T& val){ return is >> val;}
	template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
	template<class T> ostream& operator ,  (ostream& os, const T& val){ return os << " " << val;}

	template<class H> void print(const H& head){ cout << head; }
	template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
	template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }

	template<class H> void eprint(const H& head){ cerr << head; }
	template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; print(tail...); }
	template<class ... T> void eprintln(const T& ... values){ print(values...); cerr << endl; }

	string operator "" _s (const char* str, size_t size){ return move(string(str)); }
	constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
	constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
	constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }

	inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed

	mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());

	template<class T> string join(const vector<T>& v, const string& sep){
		stringstream ss; for(int i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str();
	}
}

constexpr long long mod = 9_ten + 7;

// nCk mod p, O(1)
// precomputation O(size)
class combination_mod{
	const long long mod;
	const long long size;
	
	vector<long long> fact;	//n!
	vector<long long> fact_inv;	// (n!)^-1

	void make_fact(){
		fact[0] = 1;
		for(long long i=1; i<size; i++){
			fact[i] = fact[i-1]*i % mod;
		}
	}

	void make_fact_inv(){
		fact_inv[0] = fact_inv[1] = 1;
		for(long long i=2; i<size; i++){
			fact_inv[i] = fact_inv[mod%i] * (mod - mod/i) % mod;	// x ^ -1
		}
		for(int i=2; i<size; i++){
			fact_inv[i] = fact_inv[i-1] * fact_inv[i] % mod;	// x! ^ -1
		}
	}

public:
	combination_mod(long long mod_, long long size_ = 2000000) : mod(mod_), size(size_+1){
		fact.resize(size);
		fact_inv.resize(size);
		make_fact();
		make_fact_inv();
	}

	//nCk mod p O(1)
	long long comb(long long n, long long k){
		if(k==0 || n==k) return 1;
		long long ret = fact[n] * fact_inv[k] % mod * fact_inv[n-k] % mod;
		return ret;
	}
};

long long gcd(long long a, long long b){ return (b==0)?a:gcd(b,a%b); }
template<class ... T> long long gcd(long long a, long long b, T ... c){ return gcd(gcd(a,b), c...);}
long long lcm(long long a, long long b){ if(a<b) swap(a,b); return (b==1)?a:a*(b/gcd(a,b)); }
template<class ... T> long long lcm(long long a, long long b, T ... c){ return lcm(lcm(a,b), c...);}

long long extgcd(long long a, long long b, long long &x, long long &y){
	long long d=a;
	if(b!=0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

long long mod_inverse(long long a, long long m){
	long long x,y;
	extgcd(a,m,x,y);
	return (m+x%m)%m;
}

// Z % Yi = Xi であるようなZを求める。Garnerのアルゴリズム O(N^2)
// 参考 http://techtipshoge.blogspot.jp/2015/02/blog-post_15.html
// http://yukicoder.me/problems/448
long long Chinese_Remainder_Theorem_Garner(vector<long long> x, vector<long long> y, long long MOD){
	int N = x.size();
	bool valid = true;
	//前処理
	//gcd(Yi,Yj) == 1 (i!=j) でなくてはならないので、
	//共通の因数 g = gcd(Yi,Yj) を見つけたら片側に寄せてしまう
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			if(i == j) continue;
			long long g = gcd(y[i], y[j]);

			if( x[i]%g != x[j]%g ) valid = false;	//解が存在しない

			if(g != 1){
				y[i] /= g; y[j] /= g;
				long long g_ = gcd(y[i], g);
				while(g_ != 1){
					y[i] *= g_;
					g /= g_;
					g_ = gcd(y[i], g);
				}
				y[j] *= g;

				x[i] %= y[i];
				x[j] %= y[j];
			}
		}
	}

	if(!valid){
		cerr << -1 << endl;
		return 0;
	}

	//Garner's algorithm
	vector<long long> z(N);
	for(int i=0; i<N; i++){
		z[i] = x[i];
		for(int j=0; j<i; j++){
			z[i] = mod_inverse(y[j], y[i]) % y[i] * (z[i] - z[j]) % y[i];

			z[i] = (z[i]+y[i])%y[i];
		}
	}

	long long ans = 0;
	long long tmp = 1;
	for(int i=0; i<N; i++){
		ans = (ans + z[i] * tmp)%MOD;
		tmp = (tmp * y[i])%MOD;
	}

	return ans;
}

int main(){
	int t;
	cin >> t;

	vector<combination_mod> c;
	c.emplace_back(9_ten+7, 5_ten+10);
	c.emplace_back(9_ten+9, 5_ten+10);
	c.emplace_back(9_ten+21, 5_ten+10);
	c.emplace_back(9_ten+33, 5_ten+10);
	c.emplace_back(9_ten+87, 5_ten+10);
	c.emplace_back(999999893, 5_ten+10);
	c.emplace_back(999999797, 5_ten+10);
	c.emplace_back(999999599, 5_ten+10);
	c.emplace_back(999999503, 5_ten+10);

	vector<long long> y ={
		9_ten+7,
		9_ten+9,
		9_ten+21, 
		9_ten+33, 
		9_ten+87, 
		999999893,
		999999797,
		999999599,
		999999503,
	};

	while(t--){
		string s;
		cin >> s;

		bool zero = true;
		for(int i=0; i<s.size(); i++){
			if(s[i] != '0'){
				zero = false;
				break;
			}
		}
		if(zero){
			println(0);
			continue;
		}

		vector<int> v(s.size());
		for(int i=0; i<s.size(); i++){
			v[i] = s[i] - '0';
			if(v[i] == 0) v[i] = 9;
		}

		long long ans = 0;
		int n = s.size();
		for(int i=0; i<n; i++){
			vector<long long> x;
			for(int j=0; j<c.size(); j++){
				x.push_back(c[j].comb(n-1,i));
			}
			long long k = Chinese_Remainder_Theorem_Garner(x,y,9);
			ans += (k * v[i]);
			ans %= 9;
		}

		if(ans == 0) ans = 9;

		println(ans);
	}
	return 0;
}
0