学堂刷题班"/>
10.24afternoon清北学堂刷题班
/* 这是什么题... */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm>#define N 100007 #define ll long longusing namespace std; ll n,m,cnt; ll a[N],b[N];inline ll read() {int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; }inline int cmp(ll x,ll y) {return x>y; }int main() {freopen("stone.in","r",stdin);freopen("stone.out","w",stdout);int T,res;T=read();while(T--){ll ans=0;n=read();m=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=m;i++) b[i]=read();sort(a+1,a+n+1,cmp);sort(b+1,b+m+1);for(int i=1;i<=n;i++){if(a[i]<b[i]) break;if(i>m) break;ans+=a[i]-b[i];}cout<<ans<<endl; }fclose(stdin);fclose(stdout);return 0; }
/* 因为二进制的每一位是互相独立的,只需要算出m*n的矩阵或起来是1的方案数 最后算k次方 容斥原理总情况2^(n*m) 由于“i-1行j列”和“i行j-1列”的重复计算 使得“i行j列”的情况多减了,需要与上述运算的符号相反 即:i,j组合的符号是根据上面的计算推出来的 res:仅考虑i行j列中没有1的情况总数 C(n,i)*C(m,j)是把行列选出来 Pow(2^(n*m-i*m-j*n+i*j))是说:剩下的格子随意,当前仅考虑选出的i行j列中没有1 */ #include<bits/stdc++.h>#define N 100005 #define ll long long #define mod 1000000007using namespace std; long long a[55];void pre() {a[0]=1;for(int i=1; i<=50; i++) a[i]=a[i-1]*i%mod; }inline void putout(long long x) {char c[15];int k=0;if(x<0) putchar('-'),x=-x;do{c[++k]=x%10+48;x/=10;}while(x);while(k) putchar(c[k--]); }inline long long ksm(long long now,int k) {long long mul=now;long long ret=1LL;while(k){if(k%2){ret=ret*mul%mod;}mul=mul*mul%mod;k>>=1;}return ret; }long long C(int n,int m) {ll ret=1LL*(a[n]*ksm(a[m],mod-2)%mod)*ksm(a[n-m],mod-2)%mod;return ret; }int main() {freopen("code.in","r",stdin);freopen("code.out","w",stdout);int T;pre();scanf("%d",&T);while(T--){int n,m,k;scanf("%d%d%d",&n,&m,&k);long long ans=0;for(int i=0; i<=n; i++) for(int j=0; j<=m; j++){int plus=((i+j)%2) ? -1:1;long long fast=ksm(2,n*m-i*m-j*n+i*j);long long res=(1LL*C(n,i)*C(m,j)%mod)*fast%mod;ans=(ans+res*plus)%mod; }ans=(ans+mod)%mod; ans=ksm(ans,k);printf("%I64d\n",ans);}return 0; }
/*环有四种存在情况 1.三条边已知 2.两条边已知 3.一条边已知 4.没有边已知 1.首先考虑三条边已知 对于每个点,记录出度,并把每个点连着的点用vector存储,按照点的编号大小排序 从一个点x出发,沿着一条边走到另一个点y,由此先确定两个点x,y 设置俩指针,同时扫它们连着的点,扫到相同的,ans+1 此过程需要做两个标记, 一个在点上,用于避免2.中点x连出的俩点直接相连的情况 一个在边上,用于计算3.中与一条边的两端点x y都不相连的点的个数 考虑贡献: 如果三边各不相同,ans++; 如果有相同的边,没有贡献。 2.考虑两条边已知 一个点连出的边按照帮(yan)派(se)编号排序 对于每个点x,记录出度(假设为n),则环的数量:C(n,2)-(x连出的俩点之间直接相连) 此处需要一个标记,在1.步骤中找到三元环时需要在起点x标记从x连出的点直接相连的情况 考虑贡献: 排序后的边,会呈几段分布,每段中都是颜色相同的,如果一个点连出的俩边颜色相同,那这仨点围成的环就不会产生贡献,用组合数求出不会贡献的情况个数,就可以计算出能产生贡献的情况数,每个能产生贡献的环的贡献都是(m-2) 3.考虑一条边已知 从一个点x出发,到另一个点y,需要找到这样一个点:既不与x相连,也不与y相连 可以通过在步骤1.中做标记实现 考虑贡献: 每个环的贡献:(m-1)*(m-2) 4.没有边已知 那么环的个数可以根据上面的个数直接算出来 每个环对答案的贡献:m*(m-1)*(m-2)哦漏了 还需要考虑一种情况,在两条边已知的情况下,如果连出的两条边颜色相同, 并且会有第三边将炼出的两个节点连接,那么我们容斥的时候还会多算他一次,还要再次考虑回去。 方法是在找三元环的时候,假如其中两条边相等,那么将这两条边的公共节点打一次标记。 */ #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <algorithm> using std::vector; typedef unsigned int uint; const int EDGE_SIZE = 524288; const int POINT_SIZE = 131072;struct edge_list {int point, color;uint tri;edge_list();edge_list(int, int);bool operator < (const edge_list & ) const; }; struct edge_tuple {int u, v, color;void get(); };int getint(); uint comb_2(int); // equal to C(n, 2) uint comb_3(int); // equal to C(n, 3) void add_edge(int, int, int); void init(int); bool cmp_color(const edge_list & , const edge_list & );edge_tuple a[EDGE_SIZE]; vector<edge_list> e[POINT_SIZE]; vector<std::pair<int, int> > common; int deg[POINT_SIZE]; uint tri[POINT_SIZE]; uint tri0[POINT_SIZE];int main() {freopen("triangle.in", "r", stdin);freopen("triangle.out", "w", stdout);uint T, n, m, p;uint ans;for (T = getint(); T; T--){n = getint(), m = getint(), p = getint();uint tmp = m * (m - 1) * (m - 2);init(n);for (int i = 0; i < p; i++){a[i].get();deg[a[i].u]++;deg[a[i].v]++;}for (int i = 0; i < p; i++)if (deg[a[i].u] < deg[a[i].v])add_edge(a[i].u, a[i].v, a[i].color);elseadd_edge(a[i].v, a[i].u, a[i].color);for (int i = 1; i <= n; i++)std::sort(e[i].begin(), e[i].end());ans = comb_3(n) * tmp;//type3for (int u = 1; u <= n; u++)for (int i = 0; i < e[u].size(); i++){int v = e[u][i].point;int j = 0, k = 0;common.clear();while (j < e[u].size() && k < e[v].size()){for ( ; j < e[u].size() && e[u][j].point < e[v][k].point; j++);if (j >= e[u].size()) break;for ( ; k < e[v].size() && e[v][k].point < e[u][j].point; k++);if (k >= e[v].size()) break;if (e[u][j].point == e[v][k].point)common.push_back(std::make_pair(j, k)), j++, k++;}for (int j = 0; j < common.size(); j++){int w = e[u][common[j].first].point;int c1, c2, c3;e[u][i].tri++;e[u][common[j].first].tri++;e[v][common[j].second].tri++;c1 = e[u][i].color;c2 = e[u][common[j].first].color;c3 = e[v][common[j].second].color;tri[u]++, tri[v]++, tri[w]++;if (c1 != c2 && c2 != c3 && c3 != c1)ans -= tmp - 1;else{ans -= tmp;if (c1 == c2) tri0[u]++;if (c1 == c3) tri0[v]++;if (c2 == c3) tri0[w]++;}}}//type1for (int u = 1; u <= n; u++)for (int i = 0; i < e[u].size(); i++){int v = e[u][i].point;uint cnt = n - deg[u] - deg[v] + e[u][i].tri;ans -= cnt * (tmp - (m - 1) * (m - 2));}//type2for (int i = 0; i < p; i++)if (deg[a[i].u] >= deg[a[i].v])add_edge(a[i].u, a[i].v, a[i].color);elseadd_edge(a[i].v, a[i].u, a[i].color);for (int i = 1; i <= n; i++){std::sort(e[i].begin(), e[i].end(), cmp_color);uint cnt = comb_2(deg[i]) - tri[i];ans -= cnt * (tmp - (m - 2));cnt = 1;for (int j = 1; j < e[i].size(); j++)if (e[i][j].color == e[i][j - 1].color)cnt++;else{ans -= comb_2(cnt) * (m - 2);cnt = 1;}ans -= comb_2(cnt) * (m - 2);ans += tri0[i] * (m - 2);}if (m < 3) ans = 0;printf("%u\n", ans);}return 0; }edge_list::edge_list(int _point, int _color) {point = _point;color = _color;tri = 0; } bool edge_list::operator < (const edge_list & other) const {return point < other.point; } void edge_tuple::get() {u = getint();v = getint();color = getint(); }int getint() {int num = 0;char ch;do ch = getchar();while (ch < '0' || ch > '9');do num = num * 10 + ch - '0', ch = getchar();while (ch >= '0' && ch <= '9');return num; } uint comb_2(int n) {uint f = 1;if (n < 2)return 0;if (n & 1)f = n - 1 1, f *= n;elsef = n 1, f *= n - 1;return f; } uint comb_3(int n) {uint f = 1, a = n, b = n - 1, c = n - 2;if (n < 3)return 0;if (a % 3 == 0) a /= 3;else if (b % 3 == 0) b /= 3;else c /= 3;if (a & 1) b = 1;else a = 1;f = a * b * c;return f; } void add_edge(int u, int v, int color) {e[u].push_back(edge_list(v, color)); } void init(int n) {for (int i = 1; i <= n; i++)e[i].clear();memset(tri, 0, sizeof(tri));memset(tri0, 0, sizeof(tri0));memset(deg, 0, sizeof(deg)); } bool cmp_color(const edge_list & a, const edge_list & b) {return a.color < b.color; }
转载于:.html
更多推荐
10.24afternoon清北学堂刷题班
发布评论