A
拓扑排序+倍增哈希
或者
拓扑排序对于每个点计一个rank，每个点优先选取rank靠前的最小边权点
每次依然按照rank排序更新rank
#include<bits/stdc++.h>
using namespace std;
template <typename T> void chmax(T &x,const T &y)
{
if(x<y)x=y;
}
template <typename T> void chmin(T &x,const T &y)
{
if(x>y)x=y;
}
typedef long long s64;
typedef unsigned long long u64;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
int rand_32()
{
return (RAND_MAX<=32768)?(rand()*32768+rand()):rand();
}
u64 rand_64()
{
return ((u64)rand_32()<<30)+rand_32();
}
const int N=1e6+5,L=20,D=998244353;
vector<pii>lk[N],nlk[N];
int to_fa[N];
int fa[N][L];u64 h[N][L];
int f[N];s64 g[N];
u64 w1[L],w2[L];
int du[N],q[N];
int smaller(int x,int y)
{
per(j,L-1,0)
if(h[x][j]==h[y][j])
{
x=fa[x][j];y=fa[y][j];
}
return to_fa[x]<to_fa[y];
}
int main()
{
// freopen("1.in","r",stdin);freopen("std.out","w",stdout);
int n,m;
cin>>n>>m;
rep(i,0,L-1){w1[i]=rand_64();w2[i]=rand_64();}
rep(i,1,m)
{
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
lk[x].push_back(pii(y,w));
nlk[y].push_back(pii(x,w));
++du[x];
}
//cerr<<clock()<<endl;
int tail=0;
rep(x,1,n)
if(!du[x])q[++tail]=x;
rep(head,1,tail)
{
int x=q[head];
for(auto pr:nlk[x])
{
int y=pr.first;
if(!--du[y])q[++tail]=y;
}
if(lk[x].empty())continue;
for(auto pr:lk[x])
{
int y=pr.first,w=pr.second;
chmax(f[x],f[y]+1);
}
to_fa[x]=1e9;
for(auto pr:lk[x])
{
int y=pr.first,w=pr.second;
if(f[x]==f[y]+1)chmin(to_fa[x],w);
}
for(auto pr:lk[x])
{
int y=pr.first,w=pr.second;
if(f[x]==f[y]+1&&to_fa[x]==w)
if(!fa[x][0]||smaller(y,fa[x][0]))fa[x][0]=y;
}
g[x]=29*(g[fa[x][0]]+to_fa[x])%D;
rep(j,1,L-1)fa[x][j]=fa[fa[x][j-1]][j-1];
h[x][0]=to_fa[x];
rep(j,1,L-1)h[x][j]=(h[x][j-1]^w2[j])*w1[j]+h[fa[x][j-1]][j-1];
}
//cerr<<clock()<<endl;
//cerr<<cnt<<endl;
rep(x,1,n)
if(du[x])puts("Infinity");
else printf("%d\n",int(g[x]));
}
B
概率dp
对于个人的每个mx的每个选项考虑
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define rep(a,b,c) for(int a = b; a <= c;++ a)
#define per(a,b,c) for(int a = b; a >= c; -- a)
#define gc getchar()
#define pc putchar
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
void print(int x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
#define LL long long
const int mod = 998244353;
const int maxn = 2007;
int n;
int P[maxn][4],W[4][4];
LL ans[maxn];
LL f[maxn],g[maxn]; // all / base x
inline void m(LL &x) {
x = x >= mod ? x - mod : x;
}
inline int fstpow(int x,int k) {
int ret = 1;
for(;k;k >>= 1,x = 1ll * x * x % mod)
if(k & 1) ret = 1ll * ret * x % mod;
return ret;
}
void solve(int mx) {
memset(f,0,sizeof f);
f[0] = 1;
rep(i,1,n) {
LL p = P[i][mx];
per(j,i,1)
f[j] = (f[j - 1] * p % mod + f[j] * (1 + mod - p) % mod) % mod;
f[0] = f[0] * (1 + mod - p) % mod;
}
rep(i,1,n) {
LL p = P[i][mx];
if(p != 1) {
LL inv = fstpow(mod + 1 - p,mod - 2);
g[0] = 1ll * f[0] * inv % mod;
rep(j,1,n) g[j] = 1ll * (f[j] - 1ll * p * g[j - 1] % mod) * inv % mod;
}
else
{rep(j,0,n - 1) g[j] = f[j + 1];g[n] = 0; }
LL sum = 0;
rep(j,n / 2 + 1,n) sum += g[j];
sum %= mod;
rep(j,0,3) (ans[i] += 1ll * W[mx][j] * P[i][j] % mod * (sum + (mx == j ? g[n / 2] : 0)) % mod) %= mod;
}
}
int main() {
n = read();
rep(i,1,n)
P[i][0] = read(),P[i][1] = read(),P[i][2] = read(),P[i][3] = read();
rep(i,0,3)
W[i][0] = read(),W[i][1] = read(),W[i][2] = read(),W[i][3] = read();
rep(i,0,3) solve(i);
for(int i = 1;i <= n;++ i) print((ans[i] % mod + mod) % mod),pc('\n');
return 0;
}