test20190715

Posted on | Views:

神仙题,又被虐了.

$graph$

  • $60$ 分做法:将所有方程列出来,因为保证有唯一解,所以不用管方程个数,直接高斯消元.时间复杂度 $O(m^3)$ .
  • 满分做法:比较神仙,注意到条件 $2$ 的形式是电学中基尔霍夫方程组,将 $A$ 看做 $\epsilon$ , $B$ 看做 $R$ , $C$ 看做 $I$ .
  • 为每个节点定义一个电压 $\phi(u)$ ,规定 $\phi (1)=0$ , $\phi(u)=\sum_{i=0}^{k-1} I(v_i,v_{i+1})\cdot R(v_i,v_{i+1})-\epsilon (v_i,v_{i+1})$ ,其中 $<v_0=1,v_1,\dots,v_{k-1},v_k=u>$ 是原图中一条路径,这样定义也满足了条件 $3$ .
  • 容易验证无论选择怎样的路径,每个点的电压值都是不变的.利用条件 $1$ 列出 $n-1$ 个方程,高斯消元解出 $2\sim n$ 的电压,再根据 $I(u,v)=\frac {\phi(u)-\phi(v)+\epsilon(u,v)} {R(u,v)}$ 求出电流.时间复杂度 $O(n^3)$ .

考试情况:只写了 $60$ 分的做法.

$std$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <string.h>
#include <memory.h>
#include <map>
#include <vector>
#include <set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repk(i,a,b) rep(i,a,(b)-1)
#define rrep(i,a,b) for(int i=(b);i>=(a);i--)
#define rrepk(i,a,b) rrep(i,a,(b)-1)
#define fe(e,x) for(edge *e = (x)->first;e;e = e->next)
#define foreach(tank_type,iterator_name,set_name) \
	for(tank_type::iterator iterator_name = (set_name).begin();iterator_name != (set_name).end();iterator_name++)
#define comp_def(cmp_name,type) bool cmp_name(type l,type r)
#define ifn(x) if(!(x))
#define vind(p_point) (p_point-points)
#define eind(p_edge) (p_edge-edges)
#define eopp(p_edge) (edges+(eind(p_edge)^1))
#define mp(x,y) make_pair((x),(y))
typedef long long ll;
const int inf = 0x3fffffff,upinf = 0x7fffffff,geps = 10;
const double eps = 1e-12,dinf = 1e20;

ll modnum;
struct modll{
	ll x;
	modll():x(0){}
	modll(ll _x){
		_x < 0 ? x = _x % modnum + modnum : (_x >= modnum ? x = _x % modnum : x = _x);
	}

	inline static ll pmod(ll _x){
		return _x >= modnum ? _x - modnum : _x;
	}
	inline static ll plus(ll x,ll y){
		return pmod(x + y);
	}
	inline static ll minus(ll x,ll y){
		return pmod(x + modnum - y);
	}
	inline static ll multi(ll x,ll y){
		ll s = 0;
		for(;y;y>>=1){
			if(y&1) s = plus(s,x);
			x = plus(x,x);
		}return s;
	}
	inline static ll inv(ll a){
		ll b = modnum,c = a%b,q = a/b,k1 = 1,k2 = 0,k3 = pmod(minus(k1,multi(q,k2)));
		while(c^1) a = b,b = c,c = a%b,q = a/b,k1 = k2,k2 = k3,k3 = pmod(minus(k1,multi(q,k2)));
		return k3;
	}
	inline static ll llpow(ll b,ll p){
		ll s = 1;
		for(;p;p>>=1){
			if(p&1) s = multi(s,b);
			b = multi(b,b);
		}return s;
	}
};
bool operator==(modll l,modll r){return l.x == r.x;}
bool operator!=(modll l,modll r){return l.x != r.x;}

modll operator+(modll l,modll r){return modll(modll::plus(l.x,r.x));}
modll operator-(modll l,modll r){return modll(modll::minus(l.x,r.x));}
modll operator*(modll l,modll r){return modll(modll::multi(l.x,r.x));}
modll operator/(modll l,modll r){return modll(modll::multi(l.x,modll::inv(r.x)));}
modll operator^(modll l,ll r){
	return r < 0 ? modll(modll::llpow(modll::inv(l.x),-r)) : modll(modll::llpow(l.x,r));
}
modll operator-(modll l){return modll(-l.x);}

modll operator+=(modll& l,modll r){return modll(l.x = modll::plus(l.x,r.x));}
modll operator-=(modll& l,modll r){return modll(l.x = modll::minus(l.x,r.x));}
modll operator*=(modll& l,modll r){return modll(l.x = modll::multi(l.x,r.x));}
modll operator/=(modll& l,modll r){return modll(l.x = modll::multi(l.x,modll::inv(r.x)));}
modll operator^=(modll& l,ll r){
	return modll(
			l.x = r < 0 ?
				modll::llpow(modll::inv(l.x),-r) :
				modll::llpow(l.x,r)
		);
}

const int maxn = 100,maxm = 2000;
struct equation{
	modll dat[maxn][maxn + geps];
	int n;

	void clear(int _n){
		n = _n;
		repk(i,0,n) repk(j,0,n+1) dat[i][j].x = 0;
	}
	modll& operator()(int i,int j){return dat[i][j];}
	
	void rowswap(int r1,int r2){
		repk(j,0,n+1) swap(dat[r1][j],dat[r2][j]);
	}
	void elimination(int r1,int r2){//eliminate r2 from r1
		modll g = dat[r2][r1]/dat[r1][r1];
		repk(j,0,n+1) dat[r2][j] -= dat[r1][j] * g;
	}
	vector<modll> getans(){
		vector<modll> ans;
		repk(i,0,n){
			if(dat[i][i] == 0){
				repk(j,i+1,n) if(dat[i][j] != 0) {rowswap(i,j);break;}
				if(dat[i][i] == 0) return ans;
			}repk(j,0,n) if(i != j) elimination(i,j);
		}repk(i,0,n) ans.push_back(dat[i][n] / dat[i][i]);
		return ans;
	}
};

struct Graph{
	equation Eq;pair<int,int> edge[maxm];
	modll As[maxm],Bs[maxm];
	int V,E;
	void create(int _V){Eq.clear(V = _V);E = 0;}
	void addedge(int u,int v,modll A,modll B){
		Eq(v,v) += 1/B;
		Eq(v,u) -= 1/B;
		Eq(v,V) -= A/B;
		Eq(u,v) -= 1/B;
		Eq(u,u) += 1/B;
		Eq(u,V) += A/B;
		As[E] = A,Bs[E] = B;
		edge[E++] = make_pair(u,v);
	}
	vector<ll> solve_graph(){
		repk(j,0,V+1) Eq(V-1,j) = 0;
		Eq(V-1,V-1) = 1;
		vector<modll> Por = Eq.getans();
		vector<ll> ans;
		if(Por.size() == 0) return ans;
		repk(i,0,E){
			int u = edge[i].first,v = edge[i].second;
			ans.push_back(((Por[v] - Por[u] + As[i]) / Bs[i]).x);
		}return ans;
	}
}G;

int n,m;
void Init(){
	scanf("%d%d%lld",&n,&m,&modnum);G.create(n);
	int x,y;ll A,B;
	repk(i,0,m){
		scanf("%d%d%lld%lld",&x,&y,&A,&B);
		G.addedge(x-1,y-1,A,B);
	}
}

void solve(){
	vector<ll> ans = G.solve_graph();
	if(ans.size() == 0) printf("-1\n");
	else
		foreach(vector<ll>,it,ans) printf("%lld\n",*it);
}

int main(){
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);

	Init();
	solve();

	return 0;
}

$grid$

  • $40$ 分做法:设 $f(s,i,j,d)$ 表示两人各自都走了 $s$ 步,以 $(1,1)$ 作为左下角,第一个人向右走了 $i$ 步,第二个人向右走了 $j$ 步,一共已经经过了 $d$ 个特殊点时的方案数.两人交换算一种方案,限制 $j\le i$ , $O(n^4)$ 大力 $dp$ .
  • 满分做法:先考虑一条路径的方案数,将特殊点按照 $x+y$ 排序,那么一条路径上出现的特殊点的编号递增.
  • 设 $f(i,j)$ 表示走到了第 $i$ 个特殊点,此前经过了 $j$ 个特殊点的方案数, $g(i,j)$ 表示从第 $i$ 个特殊点走到第 $j$ 个特殊点而不经过其他特殊点的方案数.枚举上一个走过的特殊点是 $k$ ,

$$
f(i,j)=\sum_{k=1}^{i-1} f(k,j-1)\cdot g(k,i)
$$

  • 把起点看做 $0$ 号点,终点看做 $C+1$ 号点,方案数为:

$$
ans=\sum_{i=0}^D f(C+1,i)
$$

  • 考虑如何求 $g(i,j)$ .若不考虑特殊点,从 $(x_0,y_0)$ 走到 $(x_1,y_1)$ 的方案数显然是 $x_1-x_0+y_1-y_0\choose x_1-x_0$ .
  • 记 $h(i,j)$ 表示从特殊点 $i$ 到特殊点 $j$ 的方案数(不考虑限制),枚举不合法路径上的第一个点 $k$ ,

$$
g(i,j)=h(i,j)-\sum_{k=i+1}^{j-1} g(i,k)\cdot h(k,j)
$$

  • 于是我们用 $O(C^3)$ 的时间复杂度解决了一条路径经过特殊点个数不超过 $D$ 的方案数.

到目前为止的部分和 这个题 做法是差不多的.

  • 若要求两条不相交路径的方案数,将两条路径看做 $(1,2)\to (n-1,m)$ 与 $(2,1) \to (n,m-1)$ .
  • 记它们为 $s_1\to t_1,s_2\to t_2$ .容斥一下,用总方案数减去路径相交的方案数.
  • 若两条路径相交于点 $p$ ,可以将它们的后半段交换,得到 $s_1\to p\to t_2$ 与 $s_2\to p \to t_1$ 两条路径.
  • 于是可以断言,所有的 $s_1\to t_2$ 与所有的 $s_2\to t_1$ 一定是一一对应的,且对应的两条路径一定相交.
  • 那么最终答案为 $s_1\to t_1,s_2\to t_2$ 的方案数乘积减去 $s_1\to t_2$ 与 $s_2\to t_1$ 的方案数之和,不需要不相交,直接套用前部分算一条路径的方案数即可.
  • 模数不为质数时,无法直接预处理阶乘逆元,需要分解质因子, $mod=\prod p_i^k$ ,处理每个质因子的时候,位置 $p_i^j$ 特判,其余位置直接求逆元,最后再用 $CRT$ 合并答案.

考试情况:只写了 $40$ 分的部分.

$std$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
#define mkp make_pair
#define fir first
#define sec second
using namespace std;

const int MaxN = 200010, Log = 10;
int fac[MaxN], facpow[MaxN][Log], facinv[MaxN];
int factor[Log], ftot;
int mod;

void exgcd(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1, y = 0;
		return;
	}
	exgcd(b, a % b, y, x);
	y -= a / b * x;
}
int get_inv(int a) {
	int x, y;
	exgcd(a, mod, x, y);
	return ((x % mod) + mod) % mod;
}
int power(ll x, int l) {
	ll ret = 1;
	for (; l; l >>= 1, x = x * x % mod)
		if (l & 1) ret = ret * x % mod;
	return ret;
}
void init(int n) {
	ftot = 0;
	int x = mod;
	for (int i = 2; i * i <= mod; ++i) 
		if (x % i == 0) {
			factor[ftot++] = i;
			while (x % i == 0) x /= i;
		}
	if (x != 1) factor[ftot++] = x;

	fac[0] = facinv[0] = 1;
	for (int i = 1; i <= n; ++i) {
		int x = i;
		memcpy(facpow[i], facpow[i - 1], sizeof facpow[i]);
		for (int j = 0; j < ftot; ++j)
			while (x % factor[j] == 0) {
				x /= factor[j];
				++facpow[i][j];
			}
		fac[i] = 1ll * fac[i - 1] * x % mod;
		facinv[i] = get_inv(fac[i]);
	}
}

int comb(int n, int m) {
	int ret = 1ll * fac[n] * facinv[m] % mod * facinv[n - m] % mod;
	for (int j = 0; j < ftot; ++j)
		ret = 1ll * ret * power(factor[j], facpow[n][j] - facpow[m][j] - facpow[n - m][j]) % mod;
	return ret;
}

const int MaxC = 210;
int n, m, c, d;
int f[MaxC][MaxC], g[MaxC][MaxC], ways[MaxC][MaxC];
bool mark[MaxC][MaxC];
int a[2][2][MaxC], ans[MaxC];
pair <int, int> car[MaxN];

inline bool tless(pair <int, int> a, pair <int, int> b) {
	return (a.fir <= b.fir) && (a.sec <= b.sec);
}

void init_car() {
	memset(ways, 0, sizeof(ways));
	memset(f, 0, sizeof(f));
	memset(mark, 0, sizeof(mark));
	for (int i = 1; i <= c; ++i)
		for (int j = i; j <= c; ++j) 
			if (tless(car[i], car[j])) {
				ways[i][j] = comb(car[j].fir - car[i].fir + car[j].sec - car[i].sec, car[j].fir - car[i].fir);
				mark[i][j] = 1;
			}
	for (int i = 1; i <= c; ++i)
		for (int j = 1; j <= c; ++j) 
			if (mark[i][j]) {
				f[i][j] = ways[i][j];
				for (int k = i + 1; k < j; ++k)
					if (mark[i][k] && mark[k][j] && f[i][k]) {
						f[i][j] = (f[i][j] - 1ll * f[i][k] * ways[k][j]) % mod;
					}
			}
}

void calc(int a[], int sx, int sy, int tx, int ty) {
	fill(a, a + c + 1, 0);
	car[0] = mkp(sx, sy);
	car[c + 1] = mkp(tx, ty);
	if (!tless(car[0], car[c + 1])) return;
	//init f[0][], f[][c + 1]
	for (int i = 0; i <= c + 1; ++i)
		if (tless(car[0], car[i])) {
			f[0][i] = ways[0][i] = comb(car[i].fir - sx + car[i].sec - sy, car[i].fir - sx);			
			mark[0][i] = 1;
			for (int j = 1; j < i; ++j)
				if (mark[0][j] && mark[j][i] && f[0][j])
					f[0][i] = (f[0][i] - 1ll * f[0][j] * ways[j][i]) % mod;
		} else {
			f[0][i] = ways[0][i] = mark[0][i] = 0;
		}
	for (int i = c + 1; i >= 0; --i)
		if (tless(car[i], car[c + 1])) {
			f[i][c + 1] = ways[i][c + 1] = comb(tx - car[i].fir + ty - car[i].sec, tx - car[i].fir);
			mark[i][c + 1] = 1;
			for (int j = i + 1; j <= c; ++j)
				if (mark[i][j] && mark[j][c + 1] && f[i][j]) {
					f[i][c + 1] = (f[i][c + 1] - 1ll * f[i][j] * ways[j][c + 1]) % mod;
				}
		} else {
			f[i][c + 1] = ways[i][c + 1] = mark[i][c + 1] = 0;
		}

	memset(g, 0, sizeof(g));
	g[0][0] = 1;
	for (int i = 1; i <= c + 1; ++i)
		for (int j = 1; j <= d + 1; ++j)
			for (int k = 0; k < i; ++k) {
				g[i][j] = (g[i][j] + 1ll * g[k][j - 1] * f[k][i]) % mod;
			}
	for (int i = 0; i <= d + 1; ++i) a[i] = g[c + 1][i + 1];
//	for (int i = 0; i <= d + 1; ++i) printf("%d ", a[i]); puts(";");
}

void Main() {
	scanf("%d%d%d%d%d", &n, &m, &c, &d, &mod);
	init(n + m);
	for (int i = 1; i <= c; ++i) 
		scanf("%d%d", &car[i].fir, &car[i].sec);
	sort(car + 1, car + c + 1);
	init_car();
	calc(a[0][0], 1, 2, n - 1, m);
	calc(a[0][1], 1, 2, n, m - 1);
	calc(a[1][0], 2, 1, n - 1, m);
	calc(a[1][1], 2, 1, n, m - 1);
	int ret = 0;
	memset(ans, 0, sizeof(ans));
	for (int i = 0; i <= d; ++i) {
		for (int j = 0; j <= i; ++j) 
			ans[i] = (ans[i] + 1ll * a[0][0][j] * a[1][1][i - j] - 1ll * a[0][1][j] * a[1][0][i - j]) % mod;
		ret += (ans[i] < 0 ? ans[i] += mod : ans[i]);
		ret >= mod ? ret -= mod : ret;
	}
	cout << ret << endl;
}

int main()
{
  freopen("grid.in", "r", stdin);
  freopen("grid.out", "w", stdout);
	int T;
	scanf("%d", &T);
	while (T--) Main();
	return 0;
}