Submission #39428

#	Time	Username	Problem	Language	Result	Execution time	Memory
39428		adamczh1	Relativnost (COCI15_relativnost)	C++14	140 / 140	2763 ms	18460 KiB

relativnost

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define SIZE(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define ff first
#define ss second

inline ll readi(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=1e5+5;
const int MOD=10007;

int N,C,Q;
int inv[MOD];
int a[MAXN];
int b[MAXN];
int tree[20][2*MAXN];
inline void pull(int x){
	for(int i=0;i<C;i++){
		tree[i][x]=0;
		for(int j=0;j<=i;j++)
			tree[i][x]=(tree[i][x]+tree[j][x<<1]*tree[i-j][x<<1|1])%MOD;
	}
}
inline void update(int p){
	int x=p+MAXN;
	tree[0][x]=b[p]%MOD;
	tree[1][x]=a[p]%MOD;
	for(x>>=1;x>0;x>>=1) pull(x);
}

int main(){
	inv[1]=1;
	for(int i=2;i<MOD;i++) inv[i]=(MOD-(MOD/i)*inv[MOD%i]%MOD)%MOD;
	N=readi(),C=readi();
	int tot=1;
	for(int i=1;i<=N;i++) a[i]=readi();
	for(int i=1;i<=N;i++) b[i]=readi(), tot=tot*((a[i]+b[i])%MOD)%MOD;
	for(int i=1;i<2*MAXN;i++)tree[0][i]=1;
	for(int i=1;i<=N;i++) update(i);
	Q=readi();
	while(Q--){
		int P=readi();
		tot=tot*inv[(a[P]+b[P])%MOD]%MOD;
		a[P]=readi(),b[P]=readi();
		tot=tot*((a[P]+b[P])%MOD)%MOD;
		update(P);
		int res=tot;
		for(int i=0;i<C;i++)res=(res-tree[i][1])%MOD;
		res=(res+MOD)%MOD;
		printf("%d\n",res);
	}
	return 0;
}

• Subtask 1: 140 / 140