Hướng dẫn cho Tích phần tử thiếu
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Tóm tắt đề bài
- Cho mảng \(a_1,a_2,...,a_n\), số nguyên dương: \(n, m, q\).
- Mỗi \(q\) truy vấn tính \(p_1\ * \ p_2 \ * \ ... \ * \ p_i\) với điều kiện:
\[~1 \le p_i \le m~ \]
\[~p_i \notin a_{l...r}~ \]
- Kết quả chia lấy dư với \(10^9+7\).
Subtask \(1\)
- Với mỗi truy vấn, ta \(for\) từ \(a_l,a_{l+1},...,a_r\) lưu vào mảng đếm \(cnt[]\).
- Sau đó ta \(for \ i\) từ \(1...m\). Nếu \(i\) chưa tồn tại trong \(cnt\) thì \(ans = ans * i\).
\(ans\) là biến kết quả.
Subtask \(2\)
- Dễ dàng nhận thấy \(p_1\ * \ p_2 \ * \ ... \ * \ p_i\) với điều kiện:
\[~1 \le p_i \le m~ \]
\[~p_i \notin a_{l...r}~ \]
chính là:
\[ ~\frac{m!}{a_l*a_{l+1}*...*a_r}~\]
- Ta tính trước \(m!\).
- Tạo mảng tiền tố \(pre[i]\) là tích của \(a_{1...i}\).
- Mỗi truy vấn ta tính \(\frac{m!}{pre[r]/pre[l-1]}\).
- Để tránh tràn số, ta áp dụng Định lí Fermat nhỏ(Fermat's little theorem).
Code
C++
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9+7;
const int nmax = 1e5+10;
ll a[nmax];
ll n,m;
ll factorial(ll n){
ll ans=1;
for(int i=2;i<=n;++i) ans = ans*i%mod;
return ans;
}
ll powmod(ll a,ll b){
ll ans = 1;
while(b){
if(b%2) ans=(ans*a)%mod;
a=(a*a)%mod;
b/=2;
}
return ans;
}
void solve(int l,int r){
ll ans = m*powmod(a[r]*powmod(a[l-1],mod-2)%mod,mod-2)%mod;
cout << ans << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
a[0]=1;
for(int i=1;i<=n;i++){
cin >> a[i];
a[i]=a[i-1]*a[i]%mod;
}
m = factorial(m);
int q; cin >> q;
while(q--){
int l, r; cin >> l >> r;
solve(l,r);
}
}
Python
Python
mod = 10**9 + 7
def factorial(m):
ans = 1
for i in range(2, m+1):
ans = ans * i % mod
return ans
def solve():
n, m = map(int, input().split())
a = list(map(int, input().split()))
pref = [1]*(n+1)
for i in range(1, n+1):
pref[i] = pref[i-1] * a[i-1] % mod
mf = factorial(m)
q = int(input())
for _ in range(q):
l, r = map(int, input().split())
prod = pref[r] * pow(pref[l-1], mod-2, mod) % mod
ans = mf * pow(prod, mod-2, mod) % mod
print(ans)
if __name__ == "__main__":
solve()
Bình luận