結果

問題 No.434 占い
コンテスト
ユーザー chakku
提出日時 2016-10-15 17:34:31
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 169 ms / 2,000 ms
コード長 2,341 bytes
コンパイル時間 1,467 ms
コンパイル使用メモリ 167,152 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2024-11-22 11:47:26
合計ジャッジ時間 3,620 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
#define CININIT cin.tie(0),ios::sync_with_stdio(false)
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

constexpr ll mod = 1e9+7;

constexpr ll max_s = 100010;
vector<vector<int>> f;

int mod_pow(int x,int n,int m){
    int res=1;
    if(x==0) return 1;
    x%=m;
    while(n){
        if(n&1) res=(res*x)%m;
        x=(x*x)%m;
        n>>=1;
    }
    return res;
}

vector<vector<int>> init(){
    vi prime;
    vector<bool> u(max_s,true);
    u[0] = u[1] = false;
    //素数列挙
    for(int i=2;i<max_s;i++){
        if(!u[i]) continue;
        prime.push_back(i);
        for(int j=2;i*j<max_s;j++) u[i*j] = false;
    }

    //素因数分解
    vector<vector<int>> f(max_s,vector<int>(9,0));
    for(int p : prime){
        for(int num=p;num<max_s;num+=p){
            int tmp=num;
            int cnt=0;
            while(tmp%p==0){
                cnt++;
                tmp/=p;
            }
            f[num][p%9]+=cnt;
        }
    }
    return f;
}

void solve(){
    string s;cin>>s;
    int n=s.size();
    vector<int> v(n);
    rep(i,n) v[i]=s[i]-'0';

    if(*max_element(ALL(v))==0){
        cout << "0" << endl;
        return;
    }

    ll ans=0;
    vector<int> nCk(9,0);
    for(int i=0;i<n;i++){
        ll tmp=1;
        // tmp := n-1Ci = 0*nCk[0] * 1*nCk[1] * 2*nCk[2] ... * 8*nCk[8]
        rep(j,9){
            ll k = mod_pow(j,nCk[j],9);
            tmp = tmp * k %9;
        }
        tmp = tmp*v[i]%9;
        ans=(ans+tmp)%9;

        // calc n-1Ci+1 = n-1Ci * (n-(i+1)) / (i+1)
        rep(j,9) nCk[j] += f[n-i-1][j];
        rep(j,9) nCk[j] -= f[i+1][j];
    }
    if(ans==0) ans=9;
    cout << ans << endl;
}

int main(){
    int T;cin>>T;
    f = init();
    rep(i,T){
        solve();
    }
}
0