B. Filling the Grid
分行和列进行染色，扫完图以后没有被染色的格子数，就是对答案产生的贡献值，wa了一发，因为没看清样例，会有冲突情况产生，这种情况下的答案是0
#include<bits/stdc++.h> const double pi=3.14159; typedef long long int ll; const int mod=1e9+7; int amap[1010][1010]; int hh[1010],ww[1010]; ll qpow(ll a,ll b){ ll res=1; while(b>0){ if(b&1){ res=res*a%mod; } b=b>>1; a=a*a%mod; } return res; } int main(){ int h,w; scanf("%d%d",&h,&w); for(int i=1;i<=h;i++){ scanf("%d",&hh[i]); } for(int i=1;i<=w;i++){ scanf("%d",&ww[i]); } for(int i=1;i<=h;i++){ for(int j=1;j<=hh[i];j++){ amap[i][j]=1; } amap[i][hh[i]+1]=-1; } for(int i=1;i<=w;i++){ for(int j=1;j<=ww[i];j++){ if(amap[j][i]==-1){ printf("0\n"); return 0; } else amap[j][i]=1; } if(amap[ww[i]+1][i]==1){ printf("0\n"); return 0; } else amap[ww[i]+1][i]=-1; } int cnt=0; for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ //printf("%d ",amap[i][j]); if(amap[i][j]==0) cnt++; } //printf("\n"); } //printf("cnt:%d\n",cnt); printf("%lld",qpow(2,cnt)); return 0; }
C. Primes and Multiplication
定义了三种操作
g(x,p)、 f(x,y)、prime(x)
1、prime（x）定义为x的素因数集合。
Let prime(x)prime(x) be the set of prime divisors of xx. For example, prime(140)={2,5,7}prime(140)={2,5,7}, prime(169)={13}prime(169)={13}.
2、g（x,p）定义为出x的因数，这个因数是p的k次，并且k要最大。
Let g(x,p) be the maximum possible integer pkpk where kk is an integer such that xx is divisible by pkpk. For example:
- g(45,3)=9 (45 is divisible by 3^2=9 but not divisible by 3^3=27),
- g(63,7)=7 (63 is divisible by 7^1=7 but not divisible by 7^2=49).
3、f（x,y）定义为g（y，p）的乘积，p为prime（x）集合中的元素。
Let f(x,y) be the product of g(y,p)g(y,p) for all p in prime(x)prime(x). For example:
- f(30,70)=g(70,2)⋅g(70,3)⋅g(70,5)=2^1⋅3^0⋅5^1=10
- f(525,63)=g(63,3)⋅g(63,5)⋅g(63,7)=3^2⋅5^0⋅7^1=6
最后给出一个x，n，求出f（x，1）*f（x，2）……*f（x，n）的乘积
数据范围：The only line contains integers x and n (2≤x≤10^9 1≤n≤10^18) — the numbers used in formula.
题目很复杂，看完脑壳疼。
慢慢分析
1、对于给定的x，我们可以先进行质因数分解，因为早晚要用到
2、最后求的是多个f（x，y）的乘积，所以连乘中的1是可以被忽略的，那么怎么样才会产生1呢？
显然，对于g（y，p）来说，p本身不是y的因数，那么就会是1
3、这时候我们会自然的想到，对于1~n这个区间来说，以Pi为因数的数的乘积就是答案
例如对于x=6，n=11
prime（x）={2,3}；
那么所以求得就是g(1,2)*g(2,2)*g(3,2)……*g(11,2)*g(1,3)*f(2,3)……*g(11,3)
这时候我们就可以发现，
2,6,10的贡献是2，2^1;
4的贡献是4,2^2;
8的贡献是8,2^3;
3,6的贡献是3,3^1;
9的贡献是9,3^2;
这时候题目就变成了，求出1~n中，所有数的最大素因数以及素数的次方数因数的乘积。
再看题面时，我们会发现素数范围在1^9，一个欧拉筛筛不出范围（可能有改进一下可以筛出的办法，但是我太菜了，并想不出）
但是再思考一下，1e5*1e5=1e10>1e9所以只要筛出1e5范围内的所有素数，最后看一下这个数本身是不是素数就可以了。
另外一个问题就是素数的最大次方数因数，2这个因数，对于4的时候，贡献就是4，对于8这个数，贡献就是8，我也不知道该怎么计算，最后看了网上别人的博客
虽然看懂了处理方法，但是并不知道什么原理，也说不清楚，反正以后就这么用吧。
反正没毛病。
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<string.h> #include<set> using namespace std; const double pi = 3.14159; typedef long long int ll; const int mod = 1e9 + 7; long long int maxn = 1e5, m, n; bool number[100005]; ll prime1[100005]; ll prime[100005]; int c = 0; int c1 = 0; void isprime() { int i, j; memset(number, true, sizeof(number)); for (i = 2; i <= maxn; i++) { if (number[i]) { prime[c++] = i; } for (j = 0; j<c&&prime[j] * i <= maxn; j++) { number[prime[j] * i] = false; if (i%prime[j] == 0) //保证每个合数只会被它的最小质因数筛去，因此每个数只会被标记一次 break; } } } ll qpow(ll a, ll b) { ll res = 1; while (b>0) { if (b & 1) res = res*a%mod; b=b>>1; a = a*a%mod; } return res; } int main() { isprime(); scanf("%lld %lld", &m, &n); for (int i = 0; i<c; i++) { if (m<prime[i]) break; if(m%prime[i] == 0){ prime1[c1++] = prime[i]; } while(m%prime[i]==0) m/=prime[i]; } if(m>1) prime1[c1++]=m; ll x; ll ans = 1; ll cnt = 0; for (int i = 0; i<c1; i++) { x = n; cnt = 0; while (x) { cnt += x / prime1[i]; x /= prime1[i]; } ans = ans*qpow(prime1[i], cnt) % mod; } printf("%lld\n", ans); return 0; }
D. Complete Tripartite
给一张图
有点和边，没有重边，没有自环，
分成三个集合，每个集合里的元素互相不相连，和另两个图的元素一一相连。
这不是扫一遍染色就完事了?
还是wa了一发，有可能一条边都没有，也有可能是边数不够，有些点没用到
加个vis和cnt维护
暴力出奇迹！
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<string.h> #include<set> using namespace std; const double pi = 3.14159; typedef long long int ll; const int mod = 1e9 + 7; long long int maxn = 1e5 + 9; int n, m; int color[300005]; int vis[300005]; int cnt1, cnt2, cnt3; struct node { int s, t; }p[300005]; bool cmp(node a, node b) { if (a.s == b.s) return a.t < b.t; else return a.s < b.s; } int main() { scanf("%d %d", &n, &m); int a, b; for (int i = 1; i <= n; i++)color[i] = 1; for (int i = 1; i <= m; i++) { scanf("%d %d", &a, &b); vis[a]++; vis[b]++; p[i].s = min(a, b); p[i].t = max(a, b); } sort(p + 1, p + 1 + m, cmp); for (int i = 1; i <= m; i++) { a = p[i].s, b = p[i].t; if (color[a] != color[b]) continue; else { if (color[a] == 3) { printf("-1\n"); return 0; } else { color[b] = color[a] + 1; } } } for (int i = 1; i <= n; i++) { if (color[i] == 1) cnt1++; else if (color[i] == 2) cnt2++; else cnt3++; } if (cnt1 == 0 || cnt2 == 0 || cnt3 == 0) { printf("-1\n"); return 0; } for (int i = 1; i <= n; i++) { if (color[i] == 1 && vis[i] == cnt2 + cnt3&&vis[i]) {} else if (color[i] == 2 && vis[i] == cnt1 + cnt3&&vis[i]) {} else if (color[i] == 3 && vis[i] == cnt1 + cnt2&&vis[i]) {} else { printf("-1\n"); return 0; } } for (int i = 1; i <= n; i++) printf("%d ", color[i]); return 0; }