QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#459888#8717. 骰子JEdwardWA 1ms9880kbC++172.5kb2024-06-30 16:18:032024-06-30 16:18:03

Judging History

你现在查看的是最新测评结果

  • [2024-06-30 16:18:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9880kb
  • [2024-06-30 16:18:03]
  • 提交

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'