Submission #12719

#TimeUsernameProblemLanguageResultExecution timeMemory
12719ainu7The last wizard (kriii2_T)C++98
1 / 4
624 ms1676 KiB
#include <math.h> #include <stdio.h> #include <string.h> #include <vector> #include <string> #include <queue> #include <map> #include <algorithm> #include <cmath> #include <iostream> #include <sstream> #include <set> using namespace std; const int mmod = 1000000007; int pw(int a, long long b) { if (b == 0) return 1; int c = pw(a, b/2); c = (1LL * c * c) % mmod; if (b%2) c = (1LL * c * a) % mmod; return c; } int inv_mod(int a, int b) { if (a == 1) return b; int div = mmod / a + 1; return inv_mod((a * (long long)div) % mmod, (b * (long long)div) % mmod); } int combi(long long a, int b) { for (int i=0; i<b; i++) if ((a-i)%mmod == 0) return 0; int ret = 1; for (int i=0; i<b; i++) { ret = (1LL * ret * (a-i)) % mmod; ret = (1LL * ret * inv_mod(i+1, 1)) % mmod; } return ret; } int main() { long long T; int N, A; cin >> T >> N >> A; int remain = A; int sum[1024] = {0}; for (int i=0; i<N; i++) { int P; cin >> P; int Q[10]; remain -= P; for (int j=0; j<10; j++) cin >> Q[j]; for (int j=0; j<(1<<10); j++) { int now = P; for (int k=0; k<10; k++) if (j&(1<<k)) now = (1LL * now * Q[k]) % mmod; sum[j] = (sum[j] + now) % mmod; } } if (remain) { sum[0] = (sum[0] + remain) % mmod; } int res = pw(A, T); int prv[1<<10] = {0}; prv[0] = 1; for (int i=1; i<=min(10LL, T); i++) { int nxt[1<<10] = {0}; int com = combi(T, i); for (int j=0; j<(1<<10); j++) { nxt[j] = 0; for (int k=0; k<j; k++) if ((j&k) == k) nxt[j] = (nxt[j] + 1LL * prv[k] * sum[j-k]) % mmod; } for (int j=0; j<(1<<10); j++) { prv[j] = nxt[j]; res = (res + ((1LL * prv[j] * com) % mmod) * pw(A, T-i)) % mmod; } } cout << res << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...