結果
問題 | No.434 占い |
ユーザー |
![]() |
提出日時 | 2016-10-14 22:47:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 2,677 bytes |
コンパイル時間 | 1,592 ms |
コンパイル使用メモリ | 170,948 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-22 08:11:03 |
合計ジャッジ時間 | 3,480 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }struct BinCoeffPrimePower {vector<int> fact; //(x!)_pvector<int> factinv; //fact[x]^{-1} mod Pvoid init(int maxN_, int p_, int q_) {assert(1 < p_ && 1 <= q_);p = p_, q = q_;P = p; for(int k = 1; k < q; ++ k) P *= p;int maxN = min(max(0, maxN_), P - 1);fact.resize(maxN + 1);fact[0] = 1;for(int x = 1; x <= maxN; ++ x) {fact[x] = x % p == 0 ? fact[x - 1] : mul(fact[x - 1], x);}factinv.resize(maxN + 1);factinv[maxN] = inverse(fact[maxN]);for(int x = maxN; x >= 1; -- x) {factinv[x - 1] = x % p == 0 ? factinv[x] : mul(factinv[x], x);}}int getP() const { return P; }int nCr(int n, int r) const {if(r > n) return 0;assert(0 <= n && (n >= getP() || n < (int)fact.size()) && 0 <= r);int z = n - r;int e0 = 0;for(int u = n / p; u > 0; u /= p) e0 += u;for(int u = r / p; u > 0; u /= p) e0 -= u;for(int u = z / p; u > 0; u /= p) e0 -= u;int em = 0;for(int u = n / P; u > 0; u /= p) em += u;for(int u = r / P; u > 0; u /= p) em -= u;for(int u = z / P; u > 0; u /= p) em -= u;int prod = 1;while(n > 0) {prod = mul(prod, fact[n % P]);prod = mul(prod, factinv[r % P]);prod = mul(prod, factinv[z % P]);n /= p, r /= p, z /= p;}if(!(p == 2 && q >= 3) && em % 2 != 0)prod = P - prod;for(int i = 0; i < e0 && i < q; ++ i)prod = mul(prod, p);return prod;}private:int mul(int x, int y) const { return (long long)x * y % P; }int inverse(signed a) const {a %= P;if(a < 0) a += P;signed b = P, u = 1, v = 0;while(b) {signed t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}if(u < 0) u += P;return u;}int p, q, P;};int main() {BinCoeffPrimePower bc;bc.init(100000, 3, 2);int T;scanf("%d", &T);for(int ii = 0; ii < T; ++ ii) {char S[100001];scanf("%s", S);int n = (int)strlen(S);int ans;if(count(S, S + n, '0') == n) {ans = 0;} else {ans = 0;rep(i, n)ans += bc.nCr(n - 1, i) * (S[i] - '0');ans %= 9;if(ans == 0) ans = 9;}printf("%d\n", ans);}return 0;}