也是CF985G。。。
容斥+三元环计数
CF数据太弱啦
vis没赋初值-1竟然过了QAQ
所以又调了我半个小时才搞掉QAQ
数数真难QAQ
记得要写#include<vector>！！！
Dev给加的奇奇怪怪的编译选项会给你自动填补的！！！
QAQ长个记性QAQ
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<vector> #define ull unsigned long long #define ll long long #define inf 20021225 #define N 400010 #define it vector<int>::iterator using namespace std; int sz[N],deg[N],n,m; vector<ull> sum[N]; vector<int> ed[N]; struct edge{int to,lt;}e[N]; int in[N],cnt; int vis[N]; void add(int x,int y){e[++cnt].to=y;e[cnt].lt=in[x];in[x]=cnt;} void go(int x){for(int i=in[x];i;i=e[i].lt) vis[e[i].to]=x;} ull calc(int x){if(x<0) return 0; return (ll)x*(x-1)/2;} ull up(int l,int r){if(l>r) return 0; return (ll)(r+l)*(r-l+1)/2;} int main() { scanf("%d%d",&n,&m); ull A,B,C,res=0; scanf("%llu%llu%llu",&A,&B,&C); int x,y; //scanf("%I64d%I64d%I64d",&A,&B,&C); int x,y; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); ed[x].push_back(y); ed[y].push_back(x); } //ull edg=(ull)n*(n-1)>>1; //at least 0 for(int i=0;i<n;i++) res+=A*i*calc(n-i-1), res+=B*i*i*(n-i-1), res+=C*i*calc(i), sort(ed[i].begin(),ed[i].end()), sum[i].push_back(0); //printf("%llu ",res); for(x=0;x<n;x++) for(it i=ed[x].begin();i!=ed[x].end();i++) sz[x]=(*i)>x?sz[x]:sz[x]+1,++deg[x],sum[x].push_back(sum[x][deg[x]-1]+(*i)); //at least 1 for(x=0;x<n;x++) for(it i=ed[x].begin();i!=ed[x].end();i++) if((*i)<x) { y=*i; //x as B res-=B*x*(n-x-1); res-=A*y*(n-x-1); res-=C*up(x+1,n-1); //x as C res-=A*up(0,y-1); res-=B*y*y; res-=B*up(y+1,x-1); res-=A*y*(x-y-1>0?x-y-1:0); res-=C*x*(x-1); } //printf("%llu ",res); //at least 2 //int dig; //printf("%llu ",res); for(x=0;x<n;x++) for(int i=1;i<=deg[x];i++) { //printf("%d %llu ",x,sum[x][i]); //x has 2 edges out y=ed[x][i-1]; if(y>x) { //x is A res+=A*x*(deg[x]-i); res+=B*y*(deg[x]-i); res+=C*(sum[x][deg[x]]-sum[x][i]); //printf("%d %d %llu ",x,y,res); } else// if(y<x) { //x is B res+=B*x*(deg[x]-sz[x]); res+=A*y*(deg[x]-sz[x]); res+=C*(sum[x][deg[x]]-sum[x][sz[x]]); //x is C res+=C*x*(i-1); res+=B*y*(i-1); res+=A*sum[x][i-1]; } } //printf("%llu ",res); //at least 3 /**for(int i=1;i<=n;i++) { if(deg[i]<=top) { for(int j=0;j<deg[i];j++) { for(int k=j+1;k<deg[i];k++) { x=i; y=ed[x][j]; z=ed[x][k]; if(x>y) swap(x,y); if(x>z) swap(x,z); res-=A*x+B*y+C*z; } } } else big.push_back(i); }*/ for(x=0;x<n;x++) for(int i=0;i<deg[x];i++) if(deg[ed[x][i]]<deg[x] || (deg[ed[x][i]]==deg[x]&&ed[x][i]<x)) add(x,ed[x][i]); memset(vis,-1,sizeof(vis)); for(x=0;x<n;x++) { go(x); for(int i=in[x];i;i=e[i].lt) { y=e[i].to; for(int j=in[y];j;j=e[j].lt) { if(vis[e[j].to]==x) { int xx=x,yy=y,zz=e[j].to; if(xx>yy) swap(xx,yy); if(xx>zz) swap(xx,zz); if(yy>zz) swap(yy,zz); res-=A*xx+B*yy+C*zz; } } } } printf("%llu ",res); //printf("%I64u ",res); return 0; } /** 4 1 2 3 4 1 0 */
由于这个题调的我太过痛苦 写作业都写不进去
bug列举一下
1.我不会冒泡排序排三个数
2.(0,n-1)看成(1,n)重调系数非常蛋疼
3.初值就是忘了赋
4.系数和值少一个
5.手贱