QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#459888 | #8717. 骰子 | JEdward | WA | 1ms | 9880kb | C++17 | 2.5kb | 2024-06-30 16:18:03 | 2024-06-30 16:18:03 |
Judging History
answer
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define int long long
#define endl '\n'
#define lowbit(x) (x)&(-x)
#define pii pair<int,int>
#define all(s) s.begin(), s.end()
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define here system("pause")
using namespace std;
template <class T> inline void read(T& x) { x = 0; char c = getchar(); bool f = 0; for (; !isdigit(c); c = getchar()) f ^= (c == '-'); for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48); x = f ? -x : x; }
template <class T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x < 10) putchar(x + 48); else write(x / 10), putchar(x % 10 + 48); }
const int N = 1505;
const int mod = 1e9+7;
const int INF = 1e15+7;
const double eps = 1e-6;
inline int pow(int a, int b, int p){ int res = 1%p; while(b){ if(b&1) res=res*a%p; a=a*a%p, b>>=1;} return res;}
inline int inv(int a, int p){ return pow(a,p-2,p)%p;}
int n, m, q;
int b[205], p[N][205], zero[N];
int pre[N][205], ipre[N][205], pre2[N][205];
vector<int> inv(vector<int> &a, int deg) {
assert(a[0]);
vector<int> res(deg + 1);
res[0] = inv(a[0], mod);
for (int i = 1; i <= deg; ++i) {
int val = 0;
for (int j = 0; j < i; ++j) {
if (i - j >= 0 && i - j < a.size())
val = (val - res[j] * a[i - j] % mod);
}
val = (val % mod + mod) % mod;
val = val * res[0] % mod;
res[i] = val;
}
return res;
}
inline void mul(int *a, int *b, int *c){
for(int i=0;i<=m;i++){
c[i] = 0;
for(int j=0;j<=i;j++){
c[i] += (c[i] + b[j]*a[i-j]) % mod;
}
}
}
inline void inv(int *a, int *b){
assert(a[0]);
b[0] = inv(a[0], mod);
for(int i=1;i<=m;i++){
b[i] = 0;
for(int j=0;j<i;j++){
b[i] = (b[i] + a[i-j]*b[j]) % mod;
}
b[i] = (b[i] + mod) % mod;
b[i] = b[i] * b[0] % mod;
}
}
inline void sol(){
cin >> n >> m >> q;
for(int i=m;i>=0;i--){
cin >> b[i];
}
for(int i=1;i<=n;i++){
bool flag = 0;
for(int j=0;j<=m;j++){
int x;
cin >> x;
x%=mod;
if(x) flag = 1;
if(flag) p[i][j-zero[i]] = x;
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 = (ans + pre2[r][i] * ipre[l-1][m-zero[r]+zero[l-1]-i]) % mod;
}
cout << ans << endl;
}
}
signed main(){
IOS;
int tc = 1;
while(tc--){
sol();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 9880kb
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: 9808kb
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: 7792kb
input:
1 1 1 604063100 57375033 742299910 257700098 1 1
output:
672257880
result:
wrong answer 1st numbers differ - expected: '148903503', found: '672257880'