結果
| 問題 | No.435 占い(Extra) |
| コンテスト | |
| ユーザー |
 koyumeishi
|
| 提出日時 | 2016-04-19 04:49:12 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,640 bytes |
| 記録 | |
| コンパイル時間 | 1,439 ms |
| コンパイル使用メモリ | 118,880 KB |
| 実行使用メモリ | 42,880 KB |
| 最終ジャッジ日時 | 2024-10-08 11:17:08 |
| 合計ジャッジ時間 | 4,745 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 4 |
| other | WA * 32 |
ソースコード
#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;
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;
}
long long mod_pow(long long x, long long y, long long MOD){
if(x==0) return 0;
long long ret=1LL;
while(y>0LL){
if(y&1LL) ret = (ret * x) % MOD;
x = (x*x) % MOD;
y >>= 1LL;
}
return ret;
}
/*
FFTで使う回転子をあるMOD上の原始根にすることで、整数での畳み込みを可能にする O(N log N)
まちがい)高速に畳み込むには 原始根^2の冪 = 1 (MOD P) とする必要がある
せいかい)高速に畳み込むには、回転子を MOD P 上で位数が 2の冪 となるような x とする必要がある。また、この位数はNTTする列より長くなくてはならない
実用的には 10^5 <= 2^k <= 10^6 となる 17 <= k <= 21 (131072 ~ 2097152) 辺りか
逆変換のときには 原始根^-1 (MOD P) を原始根として使えば良い
これを複数の MOD P_k について行い、畳み込んだ後に中国剰余定理を使えば lcm( mod P_k ) 未満の数を復元することができる
NTT( f[x] (mod P_k) ) -> F[x]
NTT( g[x] (mod P_k) ) -> G[x]
Inverse_NTT( F[x]*G[x] (mod P_k) ) -> f*g (mod P_k)
[k = 18] (2^18 = 262144 = O(2*10^5))
5 786433
79 7340033
127 5767169
593 8650753
*/
template<typename T = long long>
class Number_Theoretic_Transform {
// return the vector of F[t] or f[x] where
// F[t] = sum of { f[x] * exp(-j * theta * t * x) } in x = 0 .. N-1 (FFT)
// f(x) = 1/N * sum of { F[t] * exp(j * theta * t * x) } in t = 0 .. N-1 (inverse FFT)
// where theta = 2*PI / N
// N == 2^k
// use the rotater as (primitive-root of mod) ^ t in NTT, which is used as exp(j*theta)^t in FFT
//事前に計算した 単位回転子 rotater (MOD mod 上での位数が2^kとなる数) を 引数に与える。
//逆変換のときには rotater^-1 (MOD mod) を rotaterに与える
vector< T > do_NTT(vector< T > A, bool inverse){
int N = A.size();
//bit reverse
for(int bit=0; bit<N; bit++){
int rbit = 0;
for(int i=0, tmp_bit = bit; i<k-1; i++, rbit <<= 1, tmp_bit >>= 1){
rbit |= tmp_bit & 1;
}
rbit >>= 1;
if(bit < rbit){
swap(A[bit], A[rbit]);
}
}
int dist = 1;
vector<T>& theta = (inverse?inv_theta_v:theta_v);
T t = k-1;
T half = theta[k-1]; //半回転
for(int level = 1; level<k; level++){
T W_n = theta[t]; //rotater ^ theta (MOD mod)
T W = 1; //rotater
for(int x=0; x < (1<<(level-1)); x++){
for(int y=x; y+dist < N; y += (dist<<1)){
T tmp = A[y+dist]*W;
if(tmp >= mod) tmp %= mod;
A[y+dist] = A[y] + (tmp*half) % mod;
if(A[y+dist] >= mod) A[y+dist] %= mod;
A[y] = A[y] + tmp;
if(A[y] + tmp >= mod) A[y] %= mod;
}
W = W*W_n;
if(W>=mod) W%=mod;
}
dist <<= 1;
t -= 1;
}
if(inverse){
for(int i=0; i<N; i++){
A[i] = z * A[i];
if(A[i] >= mod) A[i] %= mod;
}
}
return A;
}
public:
const T mod;
const T rotater;
const T inv_rotater;
const T k;
vector<T> theta_v;
vector<T> inv_theta_v;
const T z;
Number_Theoretic_Transform(T mod_, T rotater_, T k_) :
mod(mod_),
rotater(rotater_),
k(k_),
inv_rotater(mod_inverse(rotater_, mod)),
z(mod_inverse(1<<(k-1), mod)) // 1/Nを掛けるところなので N^-1 MOD modを掛けたいところだけど何故か (N/2)^-1 で上手く行く……
{
theta_v = vector<T>(k+1,1);
theta_v[0] = rotater;
for(int i=1; i<=k; i++){
theta_v[i] = theta_v[i-1] * theta_v[i-1];
if(theta_v[i] >= mod) theta_v[i] %= mod;
}
inv_theta_v = vector<T>(k+1,1);
inv_theta_v[0] = inv_rotater;
for(int i=1; i<=k; i++){
inv_theta_v[i] = inv_theta_v[i-1] * inv_theta_v[i-1];
if(inv_theta_v[i] >= mod) inv_theta_v[i] %= mod;
}
};
vector< T > NTT(vector< T > A){
return do_NTT(A, false);
}
vector< T > INTT(vector< T > A){
return do_NTT(A, true);
}
// vector<double> C | C[i] = ΣA[i]B[size-1-j]
vector<T> convolution(vector<T> &A, vector<T> &B){
int n = A.size();
assert(A.size() == B.size());
assert( n == (1<<k) ); //Nは2^kである必要がある(事前にresize)
auto A_NTT = NTT(A);
auto B_NTT = NTT(B);
for(int i=0; i<n; i++){
A_NTT[i] *= B_NTT[i];
if(A_NTT[i] >= mod) A_NTT[i] %= mod;
}
return INTT(A_NTT);
}
};
long long gcd(long long a, long long b){
if(b==0) return a;
return gcd(b, a%b);
}
long long lcm(long long a, long long b){
if(a<b) swap(a,b);
if(b==1) return a;
return a * (b/gcd(a,b));
}
// 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;
const int sz = 3000;
vector<vector<int>> nCk(sz, vector<int>(sz, 0));
nCk[0][0] = 1;
for(int i=1; i<sz; i++){
for(int j=0; j<=i; j++){
nCk[i][j] = (nCk[i-1][j] + (j>0?nCk[i-1][j-1]:0)) % 9;
}
}
vector<long long> B(nCk[sz-1].begin(), nCk[sz-1].end());
B.resize(1<<18);
//reverse(B.begin(), B.end());
vector<long long> A(1<<18, 0);
Number_Theoretic_Transform<long long> ntt1(8650753,593,18);
Number_Theoretic_Transform<long long> ntt2(5767169,127,18);
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;
}
while(s.size() > sz){
fill(A.begin(), A.end(), 0);
for(int i=0; i<s.size(); i++){
A[i] = s[i] - '0';
}
auto res1 = ntt1.convolution(A,B);
auto res2 = ntt2.convolution(A,B);
string t;
for(int i=0; i<s.size()-sz+1; i++){
int val = Chinese_Remainder_Theorem_Garner({res1[i+sz-1],res2[i+sz-1]}, {8650753,5767169}, 9);
t += val + '0';
}
//cerr << t << endl;
swap(s,t);
}
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++){
long long k = nCk[n-1][i];
ans += (k * v[i]);
ans %= 9;
}
if(ans == 0) ans = 9;
println(ans);
}
return 0;
}