General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
130077910 Practice:
chasedeath
1540E - 34 C++17 (GCC 7-32) Accepted 2199 ms 9152 KB 2021-09-28 13:22:03 2021-09-28 13:22:03
→ Source
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

bool Mbe;
const int N=310,INF=1e9+10,P=1e9+7;

int n,m,q;
int a[N],A[N][N],V[N][N],SV[N][N],C[N][N];
int F[N];
ll qpow(ll x,ll k=P-2){
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int D[N];
bitset <N> B[N],All;
struct Tree{
	int s[N],t[N];
	void clr(){ memset(t,0,(m+1)<<2); }
	void Build(){ rep(i,1,m) t[i]+=t[i-1],Mod1(t[i]),s[i]=t[i]-t[i&(i-1)],Mod2(s[i]); }
	void Add(int p,int x) {
		t[m]+=x,Mod1(t[m]);
		p++;
		while(p<=m) s[p]+=x,Mod1(s[p]),p+=p&-p;
	}
	int Que(int p) {
		int r=0;
		cmin(++p,m);
		if(p==m) return t[p];
		while(p) r+=s[p],Mod1(r),p-=p&-p;
		return r;
	}
} T[N];
int W[N][N],Inv[N][N],Pow1[N][1010],Pow2[N][1<<10];

void Make(){
	All.reset();
	rep(i,1,n) if(a[i]>0) D[i]=0,All[i]=1,All|=B[i];
	else D[i]=INF;
	m=0;
	rep(i,1,n) rep(j,1,n) if(D[j]==INF && All[j]) D[j]=i,All|=B[j];
	rep(i,1,n) if(D[i]<INF) cmax(m,D[i]);
	m++;
	rep(i,1,n) T[i].clr();
	rep(i,1,n) if(D[i]<INF) rep(j,1,n) W[i][j]=1ll*C[i][j]*Inv[j][D[i]]%P,T[j].t[D[i]+1]=(T[j].t[D[i]+1]+1ll*W[i][j]*(P+a[i]))%P;
	rep(i,1,n) T[i].Build();
}

bool Med;
int main() {
	n=rd();
	rep(i,1,n) {
		Inv[i][0]=1,Inv[i][1]=qpow(i);
		rep(j,2,n) Inv[i][j]=1ll*Inv[i][j-1]*Inv[i][1]%P;
	}
	rep(i,1,n) 	rep(j,*Pow1[i]=1,1000) Pow1[i][j]=1ll*Pow1[i][j-1]*i%P;
	rep(i,1,n) a[i]=rd();
	rep(i,1,n) rep(j,A[i][i]=1,rd()) A[i][rd()]=1;
	rep(i,1,n) rep(j,i+1,n) if(A[i][j]) B[j][i]=1;
	rep(i,1,n) rep(j,1,n) A[i][j]*=j;
	rep(i,1,n) drep(j,i-1,V[i][i]=1) {
		rep(k,j+1,i) V[i][j]=(V[i][j]+1ll*A[j][k]*V[i][k])%P;
		V[i][j]=V[i][j]*qpow(i-j)%P;
	}
	rep(i,1,n) rep(j,1,n) SV[i][j]=SV[i][j-1]+V[i][j],Mod1(SV[i][j]);
	rep(i,1,n) C[i][i]=1;
	rep(i,1,n) rep(j,1,i-1) rep(k,1,n) C[i][k]=(C[i][k]+1ll*(P-V[i][j])*C[j][k])%P;
	Make();
	rep(_,1,rd()) {
		int opt=rd();
		if(opt==2){
			int i=rd(),x=rd(); a[i]+=x;
			if(a[i]-x<=0 && a[i]>0) Make();
			else if(D[i]<INF && x) rep(j,1,n) T[j].Add(D[i],1ll*W[i][j]*x%P);
		} else {
			int k=rd(),l=rd(),r=rd();
			int ans=0;
			rep(j,1,n) ans=(ans+1ll*(SV[j][r]-SV[j][l-1]+P)*T[j].Que(k)%P*Pow1[j][k])%P;
				//rep(i,1,n) if(D[i]<=k) ans=(ans+1ll*w*C[i][j]%P*qpow(j,k-D[i])%P*(P+a[i]))%P;
			rep(i,l,r) if(D[i]>k) ans+=a[i],Mod2(ans);
			printf("%d\n",ans);
		}
	}
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details