#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e4+7;
const int MAXN = (int) 3e5+5;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, c, q;
ll a[MAXN], b[MAXN];
ll dp[MAXN][25];
const int bs = 400;
ll bld[bs + 5][25];
ll bd[bs + 5][25];
ll bp(ll a, ll b){
ll res = 1;
while(b){
if(b % 2) res = (res * a)%mod;
a = (a * a) %mod;
b = b / 2;
}
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
#ifdef Local
freopen("../IO/int.txt","r",stdin);
freopen("../IO/out.txt","w",stdout);
#endif
cin>>n>>c;
for(int i = 1; i <= n; i++){
cin>>a[i];
}
ll cur = 1;
for(int i = 1; i <= n; i++){
cin>>b[i];
cur *= a[i] + b[i];
cur %= mod;
}
int blkC = (n + bs - 1)/bs;
for(int i = 0; i < blkC; i++){
dp[0][0] = 1;
ll numIt = min(bs*(i + 1), n) - bs*i;
for(int j = 1; j <= numIt; j++){
int curA = a[bs*i + j];
int curB = b[bs*i + j];
dp[j][0] = dp[j - 1][0]*curB%mod;
dp[j][0] %= mod;
for(int k = 1; k < c; k++){
dp[j][k] = dp[j - 1][k - 1]*curA% mod;
dp[j][k] += dp[j - 1][k]*curB%mod;
dp[j][k] %= mod;
}
}
for(int j = 0; j < c; j++){
bd[i][j] = dp[numIt][j];
if(i == 0) bld[i][j] = bd[i][j];
}
if(i != 0)
for(int k = 0; k < c; k++){
bld[i][k] = 0;
for(int l = 0; l <= k; l++){
bld[i][k] += bld[i - 1][l]*bd[i][k - l];
bld[i][k] %= mod;
}
}
}
cin>>q;
while(q--){
int kis, an, bn;
cin>>kis>>an>>bn;
cur = cur * bp(a[kis] + b[kis], mod - 2);
cur %= mod;
a[kis] = an;
b[kis] = bn;
cur *= an + bn;
cur %= mod;
int dis = (kis - 1)/bs;
dp[0][0] = 1;
for(int j = 1; j < c; j++){
dp[0][j] = 0;
}
int numIt = min(bs*(dis + 1), n) - bs*dis;
for(int i = 1; i <= numIt; i++){
int curA = a[bs*dis + i];
int curB = b[bs*dis + i];
dp[i][0] = dp[i - 1][0]*curB%mod;
dp[i][0] %= mod;
if(i == numIt){
bd[dis][0] = dp[i][0];
bld[dis][0] = dp[i][0];
}
for(int k = 1; k < c; k++){
dp[i][k] = dp[i - 1][k - 1]*curA% mod;
dp[i][k] += dp[i - 1][k]*curB%mod;
dp[i][k] %= mod;
if(i == numIt){
bd[dis][k] = dp[i][k];
bld[dis][k] = bd[dis][k];
}
}
}
for(int i = max(1, dis); i < blkC; i++){
for(int k = 0; k < c; k++){
bld[i][k] = 0;
for(int l = 0; l <= k / 2; l++){
bld[i][k] += bld[i - 1][l]*bd[i][k - l];
if(l != k / 2)
bld[i][k] += bld[i - 1][k - l]*bd[i][l];
bld[i][k] %= mod;
}
}
}
int cik = 0;
for(int i = 0; i < c; i++){
cik += bld[blkC - 1][i];
cik %= mod;
}
cout<<(cur - cik + mod)%mod<<endl;
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
504 KB |
Output isn't correct |
| 2 |
Incorrect |
38 ms |
504 KB |
Output isn't correct |
| 3 |
Incorrect |
46 ms |
504 KB |
Output isn't correct |
| 4 |
Incorrect |
1294 ms |
4416 KB |
Output isn't correct |
| 5 |
Incorrect |
3811 ms |
6072 KB |
Output isn't correct |
| 6 |
Execution timed out |
4022 ms |
5720 KB |
Time limit exceeded |
| 7 |
Incorrect |
2364 ms |
4648 KB |
Output isn't correct |
| 8 |
Incorrect |
1431 ms |
5508 KB |
Output isn't correct |
| 9 |
Incorrect |
2739 ms |
6132 KB |
Output isn't correct |
| 10 |
Execution timed out |
4065 ms |
4920 KB |
Time limit exceeded |
