C++14(g++5.4) 解法, 执行用时: 2514ms, 内存消耗: 121080K, 提交时间: 2019-08-23 10:06:21
#include <bits/stdc++.h>
using namespace std;
const int MAXN=311, Md=998244353;
struct Matrix {
int v[MAXN][MAXN];
int n;
Matrix(int _n=0) {
n=_n;
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
v[i][j]=0;
}
}
}
int* operator [] (int k) {
return v[k];
}
void Print() {
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
printf("%d%c", v[i][j], " \n"[j==n]);
}
}
}
};
Matrix T[MAXN], R, G, F, H, tp;
int P[MAXN], ini[MAXN], tmp[MAXN], Hs[MAXN][MAXN], Q[MAXN][MAXN], ans[MAXN][MAXN];
int gw[MAXN], igw[MAXN], fac[MAXN], ifa[MAXN];
int n, m, k;
inline void read(int &x) {
x=0; char ch=getchar();
while(!isdigit(ch)) {if(ch==EOF) return; ch=getchar();}
while(isdigit(ch)) {x=x*10+(ch-'0'); ch=getchar();}
}
inline int Add(int x, int y) {x+=y; return x>=Md ? x-Md : x;}
inline int Sub(int x, int y) {x-=y; return x<0 ? x+Md : x;}
inline int Mul(int x, int y) {return 1ll*x*y%Md;}
inline int Powe(int x, int y) {
int res=1;
for(;y;y>>=1, x=Mul(x, x))
if(y&1) res=Mul(res, x);
return res;
}
void GetInverse() {
int inv1=Powe(n-1, Md-2);
for(int i=1;i<=n;++i) {
igw[i]=Powe(gw[i], Md-2);
for(int j=1;j<=n;++j) {
if(i!=j) {
H[j][i]=Mul(inv1, igw[i]);
} else {
H[j][i]=Mul(inv1, Mul(Sub(2, n), igw[i]));
}
}
}
for(int i=1;i<=n;++i) {
for(int j=n;j>0;--j) {
Hs[j][i]=Add(Hs[j+1][i], H[j][i]);
}
}
}
Matrix operator + (Matrix A, Matrix B) {
Matrix tmp=Matrix(A.n);
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
tmp[i][j]=Add(A[i][j], B[i][j]);
}
}
return tmp;
}
Matrix operator * (Matrix A, Matrix B) {
Matrix tmp=Matrix(A.n);
for(int k=1;k<=n;++k) {
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
tmp[i][j]=Add(tmp[i][j], Mul(A[i][k], B[k][j]));
}
}
}
return tmp;
}
Matrix operator * (Matrix A, int k) {
Matrix tmp=Matrix(A.n);
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
tmp[i][j]=Mul(A[i][j], k);
}
}
return tmp;
}
/*
void Check() {
Matrix tmp=G*H;
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
if(i==j) assert(tmp[i][j]==1);
else assert(tmp[i][j]==0);
}
}
}
*/
void Calc() {
Matrix tmp=Matrix(n);
for(int i=1;i<=n;++i) {
tmp[i][i]=1;
}
int now=1;
T[0]=tmp*Powe(now, Md-2);
fac[0]=ifa[0]=1;
for(int x=1;x<n;++x) {
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
tmp[i][j]=Sub(tmp[i][j], Mul(G[i][1], H[x][j]));
}
}
for(int i=x+1;i<=n;++i) {
for(int j=1;j<=n;++j) {
tmp[i-x+1][j]=Add(tmp[i-x+1][j], Mul(gw[i-x+1], H[i][j]));
}
for(int j=1;j<=n;++j) {
tmp[i-x][j]=Sub(tmp[i-x][j], Mul(gw[i-x], H[i][j]));
}
}
now=Mul(now, x);
fac[x]=now;
ifa[x]=Powe(now, Md-2);
T[x]=tmp*ifa[x];
}
}
void GetExp() {
P[0]=1;
int now=1, kp=k;
for(int i=1;i<=n;++i) {
now=Mul(now, i);
P[i]=Mul(kp, Powe(now, Md-2));
kp=Mul(kp, k);
}
}
void GetAns() {
memset(Q, 0, sizeof Q);
for(int i=1;i<=n;++i) {
for(int j=0;j<=n;++j) {
for(int k=1;k<=n;++k) {
Q[i][j]=Add(Q[i][j], Mul(ini[k], T[j][i][k]));
}
}
}
}
/*
void FFF() {
memset(ans, 0, sizeof ans);
for(int i=1;i<=n;++i) {
for(int j=0;j<=n;++j) {
for(int k=0;j+k<=n;++k) {
ans[i][j+k]=Add(ans[i][j+k], Mul(Q[i][j], P[k]));
}
}
}
}
void Check2(int x) {
int tmp[MAXN]; memset(tmp, 0, sizeof tmp);
for(int i=0;i<=n;++i) {
for(int j=1;j<=n;++j) {
tmp[i]=Add(tmp[i], Mul(R[x][j], ans[j][i]));
}
}
int tmp2[MAXN]; memset(tmp2, 0, sizeof tmp2);
for(int i=0;i<=n;++i) {
tmp2[i]=ans[x][i];
}
for(int i=0;i<n;++i) {
tmp2[i]=Mul(tmp2[i+1], i+1);
}
for(int i=0;i<n;++i) {
assert(tmp2[i]==tmp[i]);
}
}
*/
void PrintAnswer(int x) {
for(int i=0;i<=n;++i) {
tmp[i]=0;
}
for(int i=0;i<=n;++i) {
for(int j=0;i+j<=n;++j) {
tmp[i+j]=Add(tmp[i+j], Mul(Q[x][i], P[j]));
}
}
for(int i=0;i<=n;++i) {
printf("%d%c", tmp[i], " \n"[i==n]);
}
}
void ModifyG(int x, int y) {
for(int i=1;i<=n;++i) {
if(i==x) continue;
for(int j=0;j<=n;++j) {
Q[i][j]=Sub(Q[i][j], Mul(ini[x], T[j][i][x]));
}
}
int ngw=y, nigw=Powe(y, Md-2), now=1, invn=Powe(n-1, Md-2);
int dif1=Sub(y, gw[x]), dif2=Mul(invn, nigw), dif3=Mul(dif2, Sub(2, n));
for(int i=1;i<=n;++i) {
int inv=ifa[i];
int ddif1=Mul(dif1, inv), ddif2=Mul(dif2, inv), ddif3=Mul(dif3, inv);
for(int j=1;j<=n;++j) {
if(j!=x) {
T[i][x][j]=Add(T[i][x][j], Mul(ddif1, Sub(Hs[i+1][j], (i+x<=n ? H[i+x][j] : 0))));
}
}
for(int j=1;j<=n;++j) {
if(j!=x) {
int tmp=Mul(n-i, gw[j]), tmp2=0;
if(i+j<=n) tmp=Sub(tmp, gw[j]);
if(x>=i+1 && x<=n && i+j!=x) tmp=Sub(tmp, gw[j]), tmp2=gw[j];
T[i][j][x]=(1ll*tmp*ddif2+1ll*tmp2*ddif3)%Md;
} else {
int tmp=Mul(n-i, ngw), tmp2=0;
if(i+j<=n) tmp=Sub(tmp, ngw);
if(x>=i+1 && x<=n && i+j!=x) tmp=Sub(tmp, ngw), tmp2=ngw;
T[i][j][x]=(1ll*tmp*ddif2+1ll*tmp2*ddif3)%Md;
}
}
}
for(int i=1;i<=n;++i) {
if(i!=x) G[x][i]=y, H[i][x]=Mul(invn, nigw);
else G[x][i]=0, H[i][x]=Mul(Mul(invn, Sub(2, n)), nigw);
}
for(int i=n;i>0;--i) {
Hs[i][x]=Add(Hs[i+1][x], H[i][x]);
}
gw[x]=ngw;
igw[x]=nigw;
for(int i=0;i<=n;++i) {
Q[x][i]=0;
for(int j=1;j<=n;++j) {
Q[x][i]=Add(Q[x][i], Mul(ini[j], T[i][x][j]));
}
}
for(int i=1;i<=n;++i) {
if(i==x) continue;
for(int j=0;j<=n;++j) {
Q[i][j]=Add(Q[i][j], Mul(ini[x], T[j][i][x]));
}
}
}
void ModifyIni(int x, int y) {
int dif=Sub(y, ini[x]);
for(int i=0;i<=n;++i) {
for(int j=1;j<=n;++j) {
Q[j][i]=Add(Q[j][i], Mul(dif, T[i][j][x]));
}
}
ini[x]=y;
}
int main() {
read(n);
assert(3<=n && n<=300);
G.n=H.n=T[0].n=n;
for(int i=1, x;i<=n;++i) {
T[i].n=n;
read(x); gw[i]=x;
assert(1<=x && x<=100000000);
for(int j=1;j<=n;++j) {
if(i!=j) G[i][j]=x;
}
}
GetInverse();
read(k);
assert(0<=k && k<=100000000);
for(int i=1;i<=n;++i) {
if(i>1) F[i-1][i]=1;
F[i][i]=k;
}
R=(G*F)*H;
Calc();
GetExp();
for(int i=1;i<=n;++i) {
read(ini[i]);
assert(0<=ini[i] && ini[i]<=100000000);
}
GetAns();
for(int i=1;i<=n;++i) {
PrintAnswer(i);
}
read(m);
assert(1<=m && m<=500);
int acnt=0;
while(m--) {
int op, x, y;
read(op);
assert(1<=op && op<=4);
if(op==1) {
++acnt;
assert(acnt<=300);
read(x); read(y);
assert(1<=x && x<=n);
assert(1<=y && y<=100000000);
ModifyG(x, y);
} else if(op==2) {
read(x);
assert(0<=x && x<=100000000);
k=x;
for(int i=1;i<=n;++i) {
F[i][i]=k;
}
GetExp();
} else if(op==3) {
read(x); read(y);
assert(1<=x && x<=n);
assert(0<=y && y<=100000000);
ModifyIni(x, y);
} else {
read(x);
assert(1<=x && x<=n);
PrintAnswer(x);
}
}
return 0;
}
C++ 解法, 执行用时: 2752ms, 内存消耗: 244600K, 提交时间: 2022-01-24 20:04:51
#include <bits/stdc++.h>
#define int long long
#define For(i,a,b)for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b)for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i, a)for(int i=1,i##end=a;i<=i##end;i++)
using namespace std;
const int N=311,p=998244353;
struct matrix{
int v[N][N];
int n;
matrix(int _n=0){n=_n;memset(v,0,sizeof v);}
int* operator [] (int k){return v[k];}
};
matrix F[N],R,G,H,tp;
int P[N],ini[N],res[N],Hs[N][N],Q[N][N],ans[N][N];
int w[N],iw[N],fac[N],ifa[N];
int n,m,k;
void read(int&x){
x=0; char ch=getchar();
while(!isdigit(ch)){if(ch==EOF)return; ch=getchar();}
while(isdigit(ch)){x=x*10+(ch-'0'); ch=getchar();}
}
int add(int x,int y){x+=y; return x>=p ? x-p : x;}
int del(int x,int y){x-=y; return x<0 ? x+p : x;}
int Mul(int x,int y){return x*y%p;}
int inv(int x,int base=p-2){
int res=1;
while(base){
if(base&1)res=res*x%p;
x=x*x%p;
base>>=1;
}
return res;
}
void getinv(){
int inv1=inv(n-1,p-2);
rep(i,n){
iw[i]=inv(w[i],p-2);
rep(j,n){
if(i!=j)H[j][i]=Mul(inv1,iw[i]);
else H[j][i]=Mul(inv1,Mul(del(2,n),iw[i]));
}
}
rep(i,n)Rof(j,n,1)
Hs[j][i]=add(Hs[j+1][i],H[j][i]);
}
matrix operator + (matrix A,matrix B){
matrix res=matrix(A.n);
rep(i,n)rep(j,n)
res[i][j]=add(A[i][j],B[i][j]);
return res;
}
matrix operator * (matrix A,matrix B){
matrix res=matrix(A.n);
rep(k,n)rep(i,n)rep(j,n)
res[i][j]=add(res[i][j],Mul(A[i][k],B[k][j]));
return res;
}
matrix operator * (matrix A,int k){
matrix res=matrix(A.n);
rep(i,n)rep(j,n)
res[i][j]=Mul(A[i][j],k);
return res;
}
void Calc(){
matrix res=matrix(n);
rep(i,n)res[i][i]=1;
int now=1;F[0]=res;
fac[0]=ifa[0]=1;
For(x,1,n-1){
rep(i,n)rep(j,n)
res[i][j]=del(res[i][j],Mul(G[i][1],H[x][j]));
For(i,x+1,n)rep(j,n)
res[i-x+1][j]=add(res[i-x+1][j],Mul(w[i-x+1],H[i][j]));
For(i,x+1,n)rep(j,n)
res[i-x][j]=del(res[i-x][j],Mul(w[i-x],H[i][j]));
now=Mul(now,x);
fac[x]=now;
ifa[x]=inv(now,p-2);
F[x]=res*ifa[x];
}
fac[n]=Mul(fac[n-1],n);ifa[n]=inv(fac[n],p-2);
}
void initk(){
P[0]=1;
int kp=k;
rep(i,n){
P[i]=Mul(kp,ifa[i]);
kp=Mul(kp,k);
}
}
void GetAns(){
memset(Q,0,sizeof Q);
rep(i,n)For(j,0,n)rep(k,n)
Q[i][j]=add(Q[i][j],Mul(ini[k],F[j][i][k]));
}
void output(int x){
For(i,0,n)res[i]=0;
For(i,0,n)For(j,0,n-i)
res[i+j]=add(res[i+j],Mul(Q[x][i],P[j]));
For(i,0,n)
printf("%d%c",res[i]," \n"[i==n]);
}
void work(int x,int y){
rep(i,n){
if(i==x)continue;
For(j,0,n)Q[i][j]=del(Q[i][j],Mul(ini[x],F[j][i][x]));
}
int nw=y,niw=inv(y,p-2),now=1,invn=inv(n-1);
int dif1=del(y,w[x]),dif2=Mul(invn,niw),dif3=Mul(dif2,del(2,n));
rep(i,n){
int inv=ifa[i];
int ddif1=Mul(dif1,inv),ddif2=Mul(dif2,inv),ddif3=Mul(dif3,inv);
rep(j,n)if(j!=x)
F[i][x][j]=add(F[i][x][j],Mul(ddif1,del(Hs[i+1][j],(i+x<=n ? H[i+x][j] : 0))));
rep(j,n){
if(j!=x){
int res=Mul(n-i,w[j]),res2=0;
if(i+j<=n)res=del(res,w[j]);
if(x>=i+1&&x<=n&&i+j!=x)res=del(res,w[j]),res2=w[j];
F[i][j][x]=(res*ddif2+res2*ddif3)%p;
} else{
int res=Mul(n-i,nw),res2=0;
if(i+j<=n)res=del(res,nw);
if(x>=i+1&&x<=n&&i+j!=x)res=del(res,nw),res2=nw;
F[i][j][x]=(res*ddif2+res2*ddif3)%p;
}
}
}
rep(i,n){
if(i!=x)G[x][i]=y,H[i][x]=Mul(invn,niw);
else G[x][i]=0,H[i][x]=Mul(Mul(invn,del(2,n)),niw);
}
Rof(i,n,1)Hs[i][x]=add(Hs[i+1][x],H[i][x]);
w[x]=nw;
iw[x]=niw;
For(i,0,n){
Q[x][i]=0;
rep(j,n)Q[x][i]=add(Q[x][i],Mul(ini[j],F[i][x][j]));
}
rep(i,n){
if(i==x)continue;
For(j,0,n)Q[i][j]=add(Q[i][j],Mul(ini[x],F[j][i][x]));
}
}
void initini(int x,int y){
int dif=del(y,ini[x]);
For(i,0,n)rep(j,n)Q[j][i]=add(Q[j][i],Mul(dif,F[i][j][x]));
ini[x]=y;
}
signed main(){
read(n);
G.n=H.n=F[0].n=n;
for(int i=1,x;i<=n;++i){
F[i].n=n;
read(x);w[i]=x;
rep(j,n)if(i!=j)G[i][j]=x;
}
getinv();read(k);
Calc();initk();rep(i,n)read(ini[i]);
GetAns();rep(i,n)output(i);
read(m);
while(m--){
int op,x,y;
read(op);
if(op==1){read(x);read(y);work(x,y);}
else if(op==2){read(x);k=x;initk();}
else if(op==3){read(x); read(y);initini(x,y);}
else{read(x);output(x);}
}
return 0;
}
，权值为
；同时图 B 中有边
，权值为
，那么在新图 C 中添加边
，权值设为
。
，则在新图 D 中添加一条
运算。故上述过程有
。可以发现图的复合不满足交换律。
与
复合得到
和 
。所产生的两张图满足： 
等于原图。这里两张图相同当且仅当两张图点数相同，并且对于所有的有序点对 u, v ，都满足：要么边 
（是一个属性） 。对于每个有序点对 )
，在图 
。图 
中不存在其它边。根据这一点可以唯一确定图 
的形态。 
时，图 
。这张图满足： )
，存在边 
，权值为 k 。 )
，存在边 
，权值为 1 。 
修改为 y 。保证 
。 
。 
。 
。 ，表示图 G' 中每个点在 0 时刻的梦幻值。
、各项系数模 998244353 意义下的答案。从低次到高次依次输出，共 n+1 个数。同一行中的相邻两个数用一个空格隔开。