This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)) % 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |