QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#459893#8717. 骰子JEdwardWA 832ms13316kbC++172.5kb2024-06-30 16:26:232024-06-30 16:26:23

Judging History

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

  • [2024-06-30 16:26:23]
  • 评测
  • 测评结果:WA
  • 用时:832ms
  • 内存:13316kb
  • [2024-06-30 16:26:23]
  • 提交

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'