学长写的
F. Fantastic Graph "Oh, There is a bipartite graph.""Make it Fantastic."
X wants to check whether a bipartite graph is a fantastic graph. He has two fantastic numbers, and he wants to let all the degrees to between the two boundaries. You can pick up several edges from the current graph and try to make the degrees of every point to between the two boundaries. If you pick one edge, the degrees of two end points will both increase by one. Can you help X to check whether it is possible to fix the graph?
Input There are at most 3030 test cases.
For each test case,The first line contains three integers NN the number of left part graph vertices, MM the number of right part graph vertices, and KK the number of edges ( 1 \le N \le 20001≤N≤2000,0 \le M \le 20000≤M≤2000,0 \le K \le 60000≤K≤6000 ). Vertices are numbered from 11 to NN.
The second line contains two numbers L, RL,R (0 \le L \le R \le 300)(0≤L≤R≤300). The two fantastic numbers.
Then KK lines follows, each line containing two numbers UU, VV (1 \le U \le N,1 \le V \le M)(1≤U≤N,1≤V≤M). It shows that there is a directed edge from UU-th spot to VV-th spot.
Note. There may be multiple edges between two vertices.
Output One line containing a sentence. Begin with the case number. If it is possible to pick some edges to make the graph fantastic, output "Yes" (without quote), else output "No" (without quote). 
1#include<bits/stdc++.h> 2#define LL long long 3#define INF 0x3f3f3f3f 4#define inf 0x3f3f3f3f 5#define fi first 6#define se second 7using namespace std; 8const int maxn = 6e3+32; 9int n,m,k; 10int du[2000+42]; 11int du2[2000+32]; 12int L,R; 13const int MX = 4000+54; 14const int MXE = 19000+43; 15struct MaxFlow 16{ 17 struct Edge 18 { 19 int v, w, nxt; 20 } edge[MXE],edge2[MXE]; 21 int tot, num, s, t; 22 int head[MX]; 23 void init() 24 { 25 memset(head, -1, sizeof(head)); 26 tot = 0; 27 } 28 void add(int u, int v, int w) 29 { 30 edge[tot].v = v; 31 edge[tot].w = w; 32 edge[tot].nxt = head[u]; 33 head[u] = tot++; 34 35 edge[tot].v = u; 36 edge[tot].w = 0; 37 edge[tot].nxt = head[v]; 38 head[v] = tot++; 39 } 40 41 int d[MX], vis[MX], gap[MX]; 42 void bfs() 43 { 44 memset(d, 0, sizeof(d)); 45 memset(gap, 0, sizeof(gap)); 46 memset(vis, 0, sizeof(vis)); 47 queue<int>q; 48 q.push(t); 49 vis[t] = 1; 50 while (!q.empty()) 51 { 52 int u = q.front(); 53 q.pop(); 54 for (int i = head[u]; ~i; i = edge[i].nxt) 55 { 56 int v = edge[i].v; 57 if (!vis[v]) 58 { 59 d[v] = d[u] + 1; 60 gap[d[v]]++; 61 q.push(v); 62 vis[v] = 1; 63 } 64 } 65 } 66 } 67 68 int last[MX]; 69 int dfs(int u, int f) 70 { 71 if (u == t) return f; 72 int sap = 0; 73 for (int i = last[u]; ~i; i = edge[i].nxt) 74 { 75 int v = edge[i].v; 76 if (edge[i].w > 0 && d[u] == d[v] + 1) 77 { 78 last[u] = i; 79 int tmp = dfs(v, min(f - sap, edge[i].w)); 80 edge[i].w -= tmp; 81 edge[i ^ 1].w += tmp; 82 sap += tmp; 83 if (sap == f) return sap; 84 } 85 } 86 if (d[s] >= num) return sap; 87 if (!(--gap[d[u]])) d[s] = num; 88 ++gap[++d[u]]; 89 last[u] = head[u]; 90 return sap; 91 } 92 93 int solve(int st, int ed, int n) 94 { 95 int flow = 0; 96 num = n; 97 s = st; 98 t = ed; 99 bfs(); 100 memcpy(last, head, sizeof(head)); 101 while (d[s] < num) flow += dfs(s, inf); 102 return flow; 103 } 104} F; 105int S,T; 106void update(int u,int v,int L,int R) 107{ 108 F.add(u,v,R-L); 109 F.add(S, v, L); 110 F.add(u, T, L); 111 112} 113pair<int,int>Q[6000+53]; 114 115int main() 116{ 117 int ka = 1; 118 while(~scanf("%d%d%d",&n,&m,&k)) 119 { 120 F.init(); 121 S = n+m+2; 122 T = n+m+3; 123 F.add(n+m+1, 0, INF); 124 for(int i = 0;i<=max(n,m);i++){ 125 du[i] = du2[i] = 0; 126 } 127 scanf("%d%d",&L,&R); 128 129 for(int i = 1;i<=n;i++){ 130 update(0,i,L,R); 131 } 132 for(int i = n+1;i<=n+m;i++) 133 { 134 update(i,n+m+1,L,R); 135 } 136 137 for(int i = 0;i<k;i++){ 138 int u,v; 139 scanf("%d%d",&u,&v); 140 Q[i].first = u; 141 Q[i].second = v; 142 du[u]++; 143 du2[v]++; 144 F.add(u, v+n, 1); 145 } 146 printf("Case %d: ",ka++); 147 int ret = F.solve(S, T, T + 11); 148 if(ret != (n+m)*L) puts("No"); 149 else puts("Yes"); 150 } 151}
B. Call of Accepted
You and your friends are at the table, playing an old and interesting game - the Call of Cthulhu.
There is a mechanism in the game: rolling the dice. You use a notation to communicate the type of dice that needs to be rolled - the operator "\mathop{\rm d}d". "x\mathop{\rm d}yxdy" means that an yy-sided dice should be rolled xx times and the sum of the results is taken.
Formally, for any two integers x, yx,y satisfying x \geq 0x≥0 and y \geq 1y≥1 , "x\mathop{\rm d}yxdy" means the sum of xx random integers in the range of [1, y][1,y]. It's obvious that either x < 0x<0 or y < 1y<1 makes the expression x\ {\rm d}\ yx d y illegal. For example: "2\mathop{\rm d}62d6" means that rolling a 66-sided dice 22 times. At this time, the result can be at least [1, 1] = 2[1,1]=2, and at most [6, 6] = 12[6,6]=12. The results of rolling can be used extensively in many aspects of the game. For example, an "1\mathop{\rm d}1001d100" can be used to determine whether an action with a percentage probability is successful, and a "3\mathop{\rm d}6+33d6+3 * 22" can be used to calculate the total damage when being attacked by 33 monsters simultaneously. In particular, the precedence of "\mathop{\rm d}d" is above "*". Since the operator "\mathop{\rm d}d" does not satisfy the associative law, it's necessary to make sure that "\mathop{\rm d}d" is right-associative.
Now the game has reached its most exciting stage. You are facing the Great Old One - Cthulhu. Because the spirit has been greatly affected, your sanity value needs to be deducted according to the result of rolling. If the sanity value loses too much, you will fall into madness. As a player, you want to write a program for knowing the minimum and maximum loss of sanity value before rolling, in order to make a psychological preparation.
The oldest and strongest emotion of mankind is fear, and the oldest and strongest kind of fear is fear of the unknown. ----H. P. Lovecraft
Input There are multiple sets of input, at most 3030 cases.
Each set of input contains a string of only '+', '-', '*', 'd', '(', ')' and integers without spaces, indicating the expression of this sanity loss. The length of the expression will be at most 100100.
It is guaranteed that all expressions are legal, all operators except for '(' and ')' are binary, and all intermediate results while calculating are integers in the range of [-2147483648, 2147483647][−2147483648,2147483647].
The most merciful thing in the world, I think, is the inability of the human mind to correlate all its contents. We live on a placid island of ignorance in the midst of black seas of infinity, and it was not meant that we should voyage far. ----H. P. Lovecraft
Output For each set of data, output a line of two integers separated by spaces, indicating the minimum and maximum possible values of the sanity loss. 
1#include<bits/stdc++.h> 2#define lson l,m,rt<<1 3#define rson m+1,r,rt<<1|1 4#define x first 5#define y second 6#define rep(i,a,b) for(int i=a;i<(b);++i) 7#define per(i,a,b) for(int i=a-1;i>=(b);--i) 8#define fuck(x) cout<<'['<<#x<<' '<<(x)<<']' 9#define sub(x,y) x=((x)-(y)<0)?(x)-(y)+mod:(x)-(y) 10#define clr(a,b) memset(a,b,sizeof(a)) 11#define eps 1e-10 12using namespace std; 13typedef long long ll; 14typedef unsigned long long ull; 15typedef vector<int> VI; 16typedef pair<int, int> PII; 17typedef unsigned int ui; 18const int INF = 0x3f3f3f3f; 19const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 20const int mod = 1e9 + 7; 21const int MX = 2e6 + 5; 22 23vector<string>pre, s; 24string str; 25 26bool isoperator(string op) { 27 if(op == "+" || op == "-" || op == "*" || op == "d") return 1; 28 return 0; 29} 30int priority(string op) { 31 if(op == "#") return -1; 32 if(op == "(") return 0; 33 if(op == "+" || op == "-") return 1; 34 if(op == "*") return 2; 35 if(op == "d") return 3; 36 return -1; 37} 38 39void postfix() { 40 stack<string> OPTR; //运算符栈 41 stack<string> OPND; //数据栈 42 43 OPTR.push("#"); 44 rep(i, 0, pre.size()) { 45 if (pre[i] == "(") OPTR.push(pre[i]); 46 else if(pre[i] == ")") { 47 while(OPTR.top() != "(") { 48 OPND.push(OPTR.top()); 49 OPTR.pop(); 50 } 51 OPTR.pop(); 52 } else if (isoperator(pre[i])) { 53 while(!OPTR.empty() && (priority(pre[i]) < priority(OPTR.top()) || priority(pre[i]) == priority(OPTR.top()) && pre[i] != "d")) { 54 OPND.push(OPTR.top()); 55 OPTR.pop(); 56 } 57 OPTR.push(pre[i]); 58 } else OPND.push(pre[i]); 59 } 60 61 while(OPTR.top() != "#") { 62 OPND.push(OPTR.top()); 63 OPTR.pop(); 64 } 65 OPTR.pop(); 66 67 //利用操作符栈逆序即可得到后缀表达式 68 while(!OPND.empty()) { 69 OPTR.push(OPND.top()); 70 OPND.pop(); 71 } 72 73 s.clear(); 74 while(!OPTR.empty()) { 75 s.push_back(OPTR.top()); 76 OPTR.pop(); 77 } 78} 79 80bool is_dig(char ch) {return ch >= '0' && ch <= '9';} 81void pre_solve() { 82 pre.clear(); 83 rep(i, 0, str.length()) { 84 if(is_dig(str[i])) { 85 rep(j, i, str.length()) { 86 if(!is_dig(str[j])) { 87 pre.push_back(str.substr(i, j - i)); 88 i = j - 1; 89 break; 90 } 91 if(j == str.length() - 1) { 92 pre.push_back(str.substr(i, j - i + 1)); 93 i = j; 94 break; 95 } 96 } 97 } else pre.push_back(str.substr(i, 1)); 98 } 99} 100ll str_to_int(string st) { 101 ll ret = 0; 102 rep(i, 0, st.length()) ret = ret * 10 + st[i] - '0'; 103 return ret; 104} 105 106struct node { 107 ll l, r; 108 node(ll l = 0, ll r = 0): l(l), r(r) {} 109 node(string st) {l = r = str_to_int(st);} 110 node operator-(const node& _A)const { 111 return node(l - _A.r, r - _A.l); 112 } 113 node operator+(const node& _A)const { 114 return node(l + _A.l, r + _A.r); 115 } 116 node operator*(const node& _A)const { 117 node ret; 118 ll a = l * _A.l; 119 ll b = l * _A.r; 120 ll c = r * _A.l; 121 ll d = r * _A.r; 122 ret.l = min(min(a, b), min(c, d)); 123 ret.r = max(max(a, b), max(c, d)); 124 return ret; 125 } 126 node operator/(const node& _A)const { 127 node ret; 128 ll l1 = max(l, 0ll), r1 = r; 129 ret.l = l1, ret.r = r1 * _A.r; 130 return ret; 131 } 132}; 133 134int main() { 135#ifdef local 136 freopen("in.txt", "r", stdin); 137#endif // local 138 while(cin >> str) { 139 pre_solve(); 140 postfix(); 141 stack<node>stk; 142 node a, b; 143 rep(i, 0, s.size()) if(isoperator(s[i])) { 144 b = stk.top(); stk.pop(); 145 a = stk.top(); stk.pop(); 146// printf("[%lld %lld]\n", a.l, a.r); 147// printf("[%lld %lld]\n", b.l, b.r); 148 if(s[i] == "-") a = a - b; 149 if(s[i] == "+") a = a + b; 150 if(s[i] == "*") a = a * b; 151 if(s[i] == "d") a = a / b; 152 stk.push(a); 153 } else stk.push(node(s[i])); 154 a = stk.top(); 155 printf("%lld %lld\n", a.l, a.r); 156 } 157 return 0; 158}
G.Spare time 
$a_{n} = a_{n-1}+2\times n$ $a_{n} = (a_{n}-a_{n-1})+(a_{n-1}-a_{n-2})+...+(a_{2}-a_{1})+a_{1} = n\times (n+1)$ $S_{n} = \sum_{i=1}^n i\times(i+1) = n\times(n+1)/2 + n\times(n+1)\times(2n+1)/6$
利用容斥思想，如当$m=6$时，有$2$，$3$两个质因子。既然要求与$m$互素的下标的数之和，我们枚举素因子的倍数，二进制枚举最简的倍数。
当枚举到$2$时，要删去$2(2_1)，4(2_2)，6(2_3)$；当枚举到$3$时，要删去$3(3_1)，6(3*2)$；(注意到$6$被删了两次)；当枚举到$6$时，要加上$6$哦。
容斥：
令$tmp = tot_get_num1(cnt)+tot_tot*get_num2(cnt);$
tmp = tot*get_num1(cnt)+tot*tot*get_num2(cnt);
若tot是偶数个质因子的倍数，答案加上这个数及其倍数的贡献，即tmp。 若tot是奇数个质因子的倍数，答案减去这个数及其倍数的贡献，即tmp。
1#include <bits/stdc++.h> 2using namespace std; 3typedef long long LL; 4const LL MOD = (LL)1e9 + 7; 5LL n, m, inv2, inv6; 6vector<int> ve; 7LL inv(LL t){ 8 return t == 1LL? 1LL: (MOD-MOD/t)*inv(MOD%t)%MOD; 9} 10LL get_num1(LL n){ 11 return n*(n+1)%MOD*inv2%MOD; 12} 13LL get_num2(LL n){ 14 return n*(n+1)%MOD*(2*n%MOD+1)%MOD*inv6%MOD; 15} 16int main(){ 17 inv2 = inv(2), inv6 = inv(6); 18 while(~scanf("%lld%lld", &n, &m)){ 19 ve.clear(); 20 int tm = m; 21 for(int i = 2; (LL)i * i <= m && i <= n; ++i){ 22 if(tm % i == 0){ 23 ve.push_back(i); 24 while(tm % i == 0)tm /= i; 25 } 26 if(tm == 1)break; 27 } 28 if(tm != 1)ve.push_back(tm); 29 int len = ve.size(), state = 1 << len; 30 LL ans = (get_num1(n)+get_num2(n))%MOD; 31 ans = 0; 32 for(int i = 0; i < state; ++i){ 33 LL tot = 1, cnt; 34 int num = 0; 35 for(int j = 0; j < len; ++j){ 36 if(i&(1<<j)){ 37 ++num; 38 tot *= ve[j]; 39 } 40 } 41 cnt = n/tot; 42 //printf("*%lld %lld %d\n", tot,cnt,num); 43 if(num % 2 == 0){ 44 ans = (ans+ tot*tot%MOD*get_num2(cnt)%MOD+tot*get_num1(cnt)%MOD)%MOD; 45 }else{ 46 ans = (ans- tot*tot%MOD*get_num2(cnt)%MOD-tot*get_num1(cnt)%MOD)%MOD; 47 ans = (ans + MOD)%MOD; 48 } 49 } 50 printf("%lld\n", ans); 51 } 52 return 0; 53}
<br> #### HDU6397容斥
1#include <cstdio> 2#include <cstring> 3#include <algorithm> 4#include <queue> 5#include <map> 6 7using namespace std; 8 9typedef long long LL; 10 11const int MXN = 3e5 + 6; 12const int MXT = 1e5 + 5; 13const int mod = 998244353; 14 15LL n, m, k; 16LL f[MXN], invF[MXN]; 17LL niyuan(int t) { 18 return t == 1? 1: (mod-mod/t)*niyuan(mod%t)%mod; 19} 20LL ksm(LL a, int b) { 21 LL ans = 1; 22 while(b) { 23 if(b&1) ans = ans * a %mod; 24 b >>= 1; 25 a = a * a %mod; 26 } 27 return ans; 28} 29void init() { 30 f[0] = 1; invF[0] = 1; 31 for(int i = 1; i < MXN; ++i) f[i] = f[i-1] * i % mod; 32 //invF[MXN-1] = niyuan(f[MXN-1]); 33 invF[MXN-1] = ksm(f[MXN-1], mod-2); 34 for(int i = MXN-2; i >= 1; --i) invF[i] = invF[i+1]*(i+1)%mod; 35} 36LL COMB(LL n, LL m) { 37 if(n < m) return 0; 38 return f[n] * invF[m] % mod * invF[n-m] % mod; 39} 40int main(int argc, char const *argv[]) { 41#ifndef ONLINE_JUDGE 42 //freopen("E://ADpan//in.in", "r", stdin); 43#endif 44 init(); 45 int tim; 46 scanf("%d", &tim); 47 while(tim--) { 48 scanf("%lld%lld%lld", &n, &m, &k); 49 LL ans = COMB(k+m-1,m-1), tmp; 50 for(int i = 1; i <= m; ++i) { 51 tmp = COMB(k+m-i*n-1, m-1) * COMB(m, i) % mod; 52 if(i & 1) ans = (ans - tmp + mod)%mod; 53 else ans = (ans + tmp)%mod; 54 } 55 printf("%lld\n", ans); 56 } 57 return 0; 58} 59 60/* 61字母xi=[0,n-1],问有多少个长度为m的单词,其和为k 62*/