[51nod1610]路径计数

　　路径上所有边权的最大公约数定义为一条路径的值。
　　给定一个有向无环图。
　　T次修改操作，每次修改一条边的边权，每次修改后输出有向无环图上路径的值为1的路径数量(对1,000,000,007取模)。
　Input
　　第一行两个整数n和m，分别表示有向无环图上的点数和边数。（1<=n<=100，1<=m<=50,000）
　　第2~m+1行每行三个数x,y,z，表示有一条从x到y权值为z的边。(1<=x,y<=n，1<=z<=100)
　　第m+2行一个数T，表示修改操作次数(1<=T<=500)。
　　接下来T行每行两个数x,y,表示修改第x条边(按照读入的顺序)的边权为y(1<=x<=m,1<=y<=100)。
　Output
　　T+1行，修改前和每次修改操作后输出答案。

　　朴素的想法...一开始先求出f[i][j]表示在DAG上从i点开始的路径的值为j的方案数，然后每次修改边权的时候，只要求g[i][j]表示从i点开始，经过修改的那条边的路径的值为j的方案数，然后更新f[i][j]就好了（修改就是一次删除一次添加）。

　　为了跑得快一点...可以先求出拓扑序、预处理出每个点可以到达哪些点、修改的时候先计算一下有哪些路径值可能被影响...以避免不必要的计算和更新T_T

　　复杂度O(100*n*m+T*因子个数*m)大概4亿左右...最后900+ms险过..

　　正解是容斥、floyd....其实复杂度和正解也差不多？（常数感人

值为1的路径数量= sum{ 值为x的倍数的路径数量∗u[x] } ，1<=x<=100, u[x] 为莫比乌斯函数。
值为x的倍数的路径数量可以把所有边权为x的倍数的边取出来计算路径条数。
dp[x][i][j]表示只考虑所有边权为x的倍数的边时，点i到点j的路径数量。

初始化的时候，枚举x，然后跑一次floyd即可。
那么删除一条边权为k的倍数的、从x到y的边，可以用如下代码完成：
 for(i=;i<=n;++i)

 {

     for(j=;j<=n;j++)

     {

         dp[k][i]][j]-=dp[k][i][x]*dp[k][y][j];

     }

 }
添加一条边类似，如此便可以做到修改边权的操作。
时间复杂度 O(100∗n^3+T∗因子个数∗n^2) 。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 #include<bitset>

 #define ll long long

 #define ui unsigned int

 #define ull unsigned long long

 #define d double

 const int maxn=,mxm=,modd=;

 struct zs1{int too,pre,dis;}e[mxm];int tot,last[maxn],x[mxm],y[mxm],val[mxm];

 struct zs{int zt,id;}a[maxn];int cnt;

 int p[maxn],np,mn[maxn],bel[maxn],zt[maxn];

 int dl[maxn],pos[maxn],deg[maxn],too[][maxn];

 int f[maxn][],g[maxn][];

 int i,j,k,n,m;

 char s[maxn];

 int ra;char rx;

 inline int read(){

     rx=getchar(),ra=;

     while(rx<''||rx>'')rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;

 }

 inline void MOD(int &x){if(x>=modd)x-=modd;}

 inline void UPD(int &x){if(x<)x+=modd;if(x>=modd)x-=modd;}

 bool cmpa(zs a,zs b){return a.zt<b.zt;}

 inline void prerun(){

     a[]=(zs){,};

     for(i=;i<=;i++){

         for(j=;j<=np;j++)if(!(i%p[j]))break;

         if(j>np)p[++np]=i,mn[i]=np;else mn[i]=j;

         int tmp=i;

         while(tmp>)a[i].zt|=<<(mn[tmp]-),tmp/=p[mn[tmp]];

         a[i].id=i;

     }

     cnt=,a[].zt=-,

     std::sort(a+,a++,cmpa);

     for(i=;i<=;bel[a[i].id]=cnt,i++)

         if(a[i].zt!=a[i-].zt)zt[++cnt]=a[i].zt;

     for(i=;i<=cnt;i++)for(j=;j<=;j++){

         int now=zt[bel[j]],k;

         if(i)now&=zt[i];

         for(k=;zt[k]!=now;k++);

         too[i][j]=k;

     }

 }

 inline void insert(int a,int b,int c){e[++tot].too=b,e[tot].dis=c,e[tot].pre=last[a],last[a]=tot;}

 std::bitset<> con[];

 inline void topo(){

     int l=,r=,i,j,now,to;

     for(i=;i<=n;i++){

         con[i][i]=;

         if(!deg[i])dl[++r]=i;

     }

     for(i=;i<=n;i++)f[i][]=;

     while(l<r)for(i=last[now=dl[++l]];i;i=e[i].pre){

         to=e[i].too,

         con[to]|=con[now];

         if(!--deg[to])dl[++r]=to;

         for(j=;j<=cnt;j++)MOD(f[to][too[j][e[i].dis]]+=f[now][j]);

     }

     for(i=;i<=n;i++)pos[dl[i]]=i;

 }

 int mp[],id[maxn];

 inline void getg(int edge,int fh){

     register int i,j,k;

     int e_id=bel[val[edge]],e_x=x[edge],e_y=y[edge],e_dis=val[edge];

     int num=,now,to;

     for(i=;i<=cnt;i++)if((zt[i]&zt[e_id])==zt[i])mp[++num]=i,id[i]=num;

     memset(g[e_x]+,,num<<);

     for(i=;i<=cnt;i++)if(f[e_y][i])MOD(g[e_x][id[too[i][e_dis]]]+=f[e_y][i]);

     for(i=pos[e_x]+;i<=n;i++){

         if(!con[now=dl[i]][e_y])continue;

         for(j=;j<=num;j++)g[now][j]=;

         for(j=last[now];j;j=e[j].pre)if(con[(to=e[j].too)][e_x])

             for(k=num;k;k--)

                 MOD(g[now][id[too[mp[k]][e[j].dis]]]+=g[to][k]);

     }

     for(i=pos[e_x];i<=n;i++)if(con[now=dl[i]][e_x])

         for(j=num;j;j--)if(g[now][j])UPD(f[now][mp[j]]+=fh*g[now][j]);

 }

 inline int getans(){

     int ans=;for(int i=;i<=n;i++)MOD(ans+=f[i][]);

     return ans;

 }

 int main(){

     prerun();

     n=read(),m=read();

     for(i=;i<=m;i++)

         x[i]=read(),y[i]=read(),val[i]=read(),

         deg[x[i]]++,insert(y[i],x[i],val[i]);

     topo(),printf("%d\n",getans());

     int tmp=tot;tot=,memset(last+,,n<<);

     for(i=;i<=tmp;i++)insert(x[i],y[i],val[i]);

     for(int q=read();q;q--){

         int edge=read(),v=read();

         getg(edge,-),val[edge]=e[edge].dis=v,getg(edge,),printf("%d\n",getans());

     }

 }

巴特西

[51nod1610]路径计数

最新文章

热门文章