QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#449778 | #8717. 骰子 | Andyqian7 | WA | 1ms | 7672kb | C++14 | 2.0kb | 2024-06-21 17:05:24 | 2024-06-21 17:05:24 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
using namespace std;
int n, m, q, b[300], p[2000][300], zero[300], pre[300][300], ipre[300][300], pre2[300][300];
int fp(int x, int k)
{
if (!k)
return 1;
if (k & 1)
return fp(x, k - 1) * x % mod;
int tmp = fp(x, k >> 1);
return tmp * tmp % mod;
}
int inv(int x)
{
return fp(x, mod - 2);
}
void mul(int *a, int *b, int *c)
{
for (int i = 0; i <= m; i++)
{
c[i] = 0;
for (int j = 0; j <= m; j++)
{
c[i] += b[i] * a[i - j];
c[i] %= mod;
}
}
}
void inv(int *a, int *b)
{
b[0] = inv(a[0]);
for (int i = 1; i <= m; i++)
{
b[i] = 0;
for (int j = 0; j < i; j++)
{
b[i] += a[i - j] * b[j];
b[i] %= mod;
}
b[i] = (mod - b[i]) * b[0] % mod;
}
}
signed main()
{
cin >> n >> m >> q;
for (int i = 0; i <= m; i++)
{
cin >> b[m - i];
}
for (int i = 1; i <= n; i++)
{
bool sign = false;
for (int j = 0; j <= m; j++)
{
int tmp;
cin >> tmp;
tmp %= mod;
if (tmp)
sign = true;
if (sign)
{
p[i][j - zero[i]] = tmp;
}
else
{
zero[i]++;
}
}
zero[i] += zero[i - 1];
}
ipre[0][0] = pre[0][0] = 1;
for (int i = 1; i <= n; i++)
{
mul(pre[i - 1], p[i], pre[i]);
inv(pre[i], ipre[i]);
mul(pre[i], b, pre2[i]);
}
while (q--)
{
int l, r;
cin >> l >> r;
int ans = 0;
for (int i = 0; i <= m - zero[r] + zero[l - 1]; i++)
{
ans += pre2[r][i] * ipre[l - 1][m - zero[r] + zero[l - 1] - i];
ans %= mod;
}
cout << ans << endl;
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5768kb
input:
3 3 3 4 3 2 1 0 1 0 1000000007 0 500000004 0 500000004 0 0 500000004 500000004 1 1 1 2 1 3
output:
3 1 0
result:
ok 3 number(s): "3 1 0"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7672kb
input:
3 3 6 4 3 2 1 1000000007 0 1 0 1000000007 1 0 0 1000000007 0 1 0 1 1 1 2 1 3 2 2 2 3 3 3
output:
2 1 0 3 1 2
result:
ok 6 numbers
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3716kb
input:
1 1 1 604063100 57375033 742299910 257700098 1 1
output:
604063100
result:
wrong answer 1st numbers differ - expected: '148903503', found: '604063100'