51nod 1610 路径计数(数论+容斥+拓扑+Floyd)

分析:gcd的问题可以考虑用容斥原理做,注意到y<=100,只需要枚举不超过100的数k,算出图中有多少条边权是k的倍数的路径,然后容斥一下即可。关键在于怎么算路径条数。

可以考虑用dp,记dp[i][j][k]为从i到j路径值为k倍数的路径数,dp[i][j][k]=∑dp[c][j][k],c满足存在从i到c的边且边权为k的倍数。为了快速处理dp,先预处理出拓扑序和不超过100的数的因子以及各点是否能到达。

更新时,先删掉路径值为v的因子的路径,再重新加上y即可,总的复杂度为O(n^3+n*m*√y+T*n^2*√y)。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 using namespace std;
  5 const int maxn=105,p=1000000007;
  6 typedef long long ll;
  7 struct Edge{
  8     int s,t,v;
  9 };
 10 Edge edge[50005];
 11 int e[maxn][50005],factor[maxn][100],connect[maxn][maxn];
 12 int countedge=0,counte[maxn],countfactor[maxn],countconnect[maxn];
 13 int dp[maxn][maxn][maxn],mu[maxn],topo[maxn],countside[maxn][maxn],in[maxn];
 14 bool d[maxn][maxn];
 15 int n,m,ans=0,sum[maxn];
 16 void Caldp(){
 17     memset(dp,0,sizeof(dp));
 18     for(int i=1;i<=n;i++){
 19         for(int k=1;k<=100;k++)
 20             dp[i][i][k]=1;
 21     }
 22     for(int a=0;a<n;a++){
 23         int i=topo[a];
 24         for(int j=1;j<=n;j++){
 25             for(int h=0;h<counte[i];h++){
 26                 Edge &_e=edge[e[i][h]];
 27                 for(int b=0;b<countfactor[_e.v];b++){
 28                     int &v=factor[_e.v][b];
 29                     dp[i][j][v]=(dp[i][j][v]+dp[_e.t][j][v])%p;
 30                 }
 31             }
 32         }
 33     }
 34 }
 35 void Depose(){
 36     for(int i=1;i<=100;i++){
 37         for(int j=i;j<=100;j+=i){
 38             factor[j][countfactor[j]++]=i;
 39         }
 40     }
 41 }
 42 void Floyd(){
 43     for(int i=1;i<=n;i++)
 44         d[i][i]=true;
 45     for(int k=1;k<=n;k++){
 46         for(int i=1;i<=n;i++){
 47             for(int j=1;j<=n;j++){
 48                 d[i][j]=d[i][j]||(d[i][k]&&d[k][j]);
 49             }
 50         }
 51     }
 52     for(int i=1;i<=n;i++){
 53         for(int j=1;j<=n;j++){
 54             if(d[i][j])
 55                 connect[i][countconnect[i]++]=j;
 56         }
 57     }
 58 }
 59 void Topo(){
 60     int t=n;
 61     while(t){
 62         for(int i=1;i<=n;i++){
 63             if(in[i])continue;
 64             topo[--t]=i;
 65             in[i]=5e5+5;
 66             for(int j=1;j<=n;j++){
 67                 in[j]-=countside[i][j];
 68             }
 69         }
 70     }
 71 }
 72 void CalMu(){
 73     mu[1]=1;
 74     int p[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
 75     for(int i=0;i<25;i++){
 76         mu[p[i]]=-1;
 77     }
 78     for(int i=2;i<=100;i++){
 79         for(int j=0;j<25&&p[j]<=i;j++){
 80             if(i%p[j]==0){
 81                 if(i%(p[j]*p[j])==0)mu[i]=0;
 82                 else
 83                     mu[i]=-mu[i/p[j]];
 84             }
 85         }
 86     }
 87 }
 88 void Updata(int x,int y){
 89     int k=edge[x].v;
 90     for(int l=0;l<countfactor[k];l++){
 91         int v=factor[k][l];
 92         for(int i=1;i<=n;i++){
 93             if(!d[i][edge[x].s])continue;
 94             for(int h=0;h<countconnect[i];h++){
 95                 int j=connect[i][h];
 96                 if(i==j||!d[edge[x].t][j])
 97                     continue;
 98                 dp[i][j][v]=(dp[i][j][v]-(ll)dp[i][edge[x].s][v]*dp[edge[x].t][j][v])%p;
 99                 sum[v]=(sum[v]-(ll)dp[i][edge[x].s][v]*dp[edge[x].t][j][v])%p;
100             }
101         }
102     }
103     edge[x].v=y;
104     for(int l=0;l<countfactor[y];l++){
105         int v=factor[y][l];
106         for(int i=1;i<=n;i++){
107             if(!d[i][edge[x].s])continue;
108             for(int h=0;h<countconnect[i];h++){
109                 int j=connect[i][h];
110                 if(i==j||!d[edge[x].t][j])
111                     continue;
112                 dp[i][j][v]=(dp[i][j][v]+(ll)dp[i][edge[x].s][v]*dp[edge[x].t][j][v])%p;
113                 sum[v]=(sum[v]+(ll)dp[i][edge[x].s][v]*dp[edge[x].t][j][v])%p;
114             }
115         }
116     }
117     ans=0;
118     for(int i=1;i<=100;i++){
119         ans=(ans+mu[i]*sum[i])%p;
120     }
121     ans=(ans+p)%p;
122 }
123 int main(){
124     //freopen("e:\in.txt","r",stdin);
125     //freopen("e:\out.txt","w",stdout);
126     memset(d,0,sizeof(d));
127     memset(countside,0,sizeof(countside));
128     memset(in,0,sizeof(in));
129     memset(counte,0,sizeof(counte));
130     memset(countfactor,0,sizeof(countfactor));
131     memset(countconnect,0,sizeof(countconnect));
132     Depose();
133     CalMu();
134     Edge ee;
135     scanf("%d%d",&n,&m);
136     for(int i=0;i<m;i++){
137         scanf("%d%d%d",&ee.s,&ee.t,&ee.v);
138         edge[countedge++]=ee;
139         e[ee.s][counte[ee.s]++]=i;
140         d[ee.s][ee.t]=true;
141         countside[ee.s][ee.t]++;
142         in[ee.t]++;
143     }
144     Floyd();
145     Topo();
146     Caldp();
147     for(int k=1;k<=100;k++){
148         sum[k]=0;
149         for(int i=1;i<=n;i++){
150             for(int j=1;j<=n;j++){
151                 if(i==j)continue;
152                 sum[k]=(sum[k]+dp[i][j][k])%p;
153             }
154         }
155     }
156     for(int i=1;i<=100;i++){
157         ans=(ans+mu[i]*sum[i])%p;
158     }
159     ans=(ans+p)%p;
160     printf("%d
",ans);
161     int t,x,y;
162     scanf("%d",&t);
163     while(t--){
164         scanf("%d%d",&x,&y);
165         Updata(x-1,y);
166         printf("%d
",ans);
167     }
168     return 0;
169 }
原文地址:https://www.cnblogs.com/7391-KID/p/7141663.html