QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#459893 | #8717. 骰子 | JEdward | WA | 832ms | 13316kb | C++17 | 2.5kb | 2024-06-30 16:26:23 | 2024-06-30 16:26:23 |
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: 1ms
memory: 9752kb
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: 9760kb
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: 0
Accepted
time: 1ms
memory: 7776kb
input:
1 1 1 604063100 57375033 742299910 257700098 1 1
output:
148903503
result:
ok 1 number(s): "148903503"
Test #4:
score: -100
Wrong Answer
time: 832ms
memory: 13316kb
input:
1500 200 600000 253665324 876103781 804024983 929290295 908790466 176299158 528078340 696679927 416465140 509641654 705083449 361711737 250659645 735832780 35321360 383752049 203979021 178832532 785212637 514502839 169840231 65809146 504755349 516829442 382478309 901925498 142312128 782336477 741339...
output:
92863704 836701132 242465252 928706068 218427777 520253356 885164944 193662453 584364851 351158898 779271439 429532075 843224465 597469676 23747875 403646943 255796554 402902742 302776041 147499118 992782015 972761093 544386922 574257914 645532630 689034391 662015873 898264863 456279024 442124215 63...
result:
wrong answer 1st numbers differ - expected: '66394849', found: '92863704'