Kyoya and Train
一个有(n)个节点(m)条边的有向图，每条边连接了(a_i)和(b_i)，花费为(c_i)。
每次经过某一条边就要花费该边的(c_i)。
第(i)条边耗时为(j)的概率为(p_{i,j})。
现在你从(1)开始走到(n)，如果你在(t)单位时间内（包括(t)）到了(n)，不需要任何额外花费，否则你要额外花费(x)。
问你在最优策略下的期望花费最小为多少。（注意你每走一步都会根据当前情况制定最好的下一步）
(nleq 50 ,m leq 100, tleq 20000, xleq 10^6)
毛啸论文
看别人的代码，我学会了怎么用线性的空间预处理单位根。
[frac{2pi}{2step} imes i=frac{2pi}{lim} imes frac{lim}{2step} imes i
]
而(frac{lim}{2step} imes i < frac{lim}{2},iin [0,step))，所以预处理(omega^{frac{2pi}{lim}})的次幂即可。
co double pi=acos(-1);
struct node {double x,y;};
il node operator+(co node&a,co node&b){
return (node){a.x+b.x,a.y+b.y};
}
il node operator-(co node&a,co node&b){
return (node){a.x-b.x,a.y-b.y};
}
il node operator*(co node&a,co node&b){
return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}
co int N=55,M=105,T=20005,S=1<<15;
int n,m,t,punish;
int a[M],b[M],c[M],dis[N][N];
double dp[N][T],sum[M][T],p[M][T];
int rev[S];
node w[S],A[S],B[S];
void fourier_trans(node a[],int lim){
for(int i=0;i<lim;++i)
if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int step=1;step<lim;step<<=1){
int quot=lim/(step<<1);
for(int i=0;i<lim;i+=step<<1){
int j=i+step;
for(int k=0;k<step;++k){
node t=w[quot*k]*a[j+k];
a[j+k]=a[i+k]-t,a[i+k]=a[i+k]+t;
}
}
}
}
void solve(int l,int r){
if(l==r){
for(int e=1;e<=m;++e)
dp[a[e]][l]=min(dp[a[e]][l],sum[e][l]+c[e]);
return;
}
int mid=(l+r)>>1;
solve(mid+1,r);
int len=int(ceil(log2(r-mid+r-l-1))),lim=1<<len;
for(int i=0;i<lim;++i){
rev[i]=rev[i>>1]>>1|(i&1)<<(len-1);
w[i]=(node){cos(i*2*pi/lim),sin(i*2*pi/lim)};
}
for(int e=1;e<=m;++e){
for(int i=0;i<lim;++i)
A[i]=B[i]=(node){0,0};
for(int i=mid+1;i<=r;++i)
A[i-mid-1]=(node){dp[b[e]][i],0};
for(int i=1;i<=r-l;++i)
B[r-l-i]=(node){p[e][i],0};
fourier_trans(A,lim),fourier_trans(B,lim);
for(int i=0;i<lim;++i){
A[i]=A[i]*B[i];
w[i].y=-w[i].y;
}
fourier_trans(A,lim);
for(int i=0;i<lim;++i){
A[i].x/=lim;
w[i].y=-w[i].y;
}
for(int i=l;i<=mid;++i)
sum[e][i]+=A[i-mid-1+r-l].x;
}
solve(l,mid);
}
int main(){
scanf("%d%d%d%d",&n,&m,&t,&punish);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dis[i][j]=i==j?0:1e9;
for(int i=1;i<=m;++i){
scanf("%d%d%d",a+i,b+i,c+i);
dis[a[i]][b[i]]=min(dis[a[i]][b[i]],c[i]);
for(int j=1;j<=t;++j)
scanf("%lf",p[i]+j),p[i][j]/=100000;
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
for(int i=0;i<N;++i)
for(int j=0;j<T;++j)
dp[i][j]=1e9;
for(int i=1;i<=n;++i) dp[i][t+1]=punish+dis[i][n];
for(int i=0;i<=t;++i) dp[n][i]=0;
for(int e=1;e<=m;++e){
double P=0;
for(int i=1;i<=t;++i){
P+=p[e][t+1-i];
sum[e][i]=P*dp[b[e]][t+1];
}
}
solve(0,t);
printf("%lf
",dp[1][0]);
return 0;
}