Đề bài:
Chuyện là Sơn senpai ảo tưởng mình được isekai đến một thế giới toàn loli và làm thần ở thế giới đó, vì mong muốn thống trị của bản thân Sơn đã có một kế hoạch đó là biến thế giới này thành một thế giới hòa bình mà không có chiến tranh nhằm đảm bảo Sơn có nhiều loli nhất có thể ( ͡° ͜ʖ ͡°), và để làm được việc đó, sơn phải phân chia lại vùng đất của 2 vương quốc lớn đó là Betty, Reggy để sao cho 2 vuông quốc này không chiếm lẫn nhau. Thần sơn nhận ra rằng nếu bất kỳ thành phố của vương quốc nào không được kết nối với ít nhất một thành phố đồng mình khác thì thành phố đó sẽ bị chiếm bởi vương quốc kẻ thù. Bài toán này đối với một thằng wibu như Sơn thì không có gì khó nhưng Sơn đang muốn tuyển nhân viên để nghiên cứu máy tính lượng cho Sơn. Vì thế bạn! Tôi nói bạn đó, người đang đọc bài này, Sơn yêu cầu bạn tìm số cách phân chia cho các vùng đất trên. Biết rằng các thành phố kết nối với nhau và tạo thành một CâyInput
Dòng đầu tiên ghi số nút (n)
(n-1) dòng tiếp theo ghi các kết nối giữa 2 nút
Output
Một số duy nhất là số cách phân chia vùng đất trên, vì giá trị có thể rất lớn nên bạn chỉ cần mod cho (10^9 + 7)
Limits
Time limit: 1 seconds per test set.
Memory limit: 1GB.
Thuật toán ngây thơ (40%) :
2 ≤ n ≤ 20
1 ≤ u,v ≤ n
Test set 2 (60%):
2 ≤ n ≤ 10^5
1 ≤ u,v ≤ n
Sample
Input
5 1 2 1 3 3 4 3 5
Output
4
Minh họa 4 trường hợp thỏa mãn:
Hướng dẫn giải:
Quy hoạch động dp[now][cur][ally], trong đó now là nút xét hiện tại, cur là thành phố của vương quốc nào (1, 0), ally là đồng minh hay kẻ thù. code mẫu ở dưới
Thuật full O(n)
// _____ _ _ // / ____| | | (_) // | (___ ___ _ __ __| | ___ _ __ ______ _ _ // \___ \ / _ \| '_ \ / _` |/ _ \ '_ \ |_ / _` | | // ____) | (_) | | | | | (_| | __/ |_) | / / (_| | | // |_____/ \___/|_| |_| \__,_|\___| .__/ /___\__,_|_| // | | // |_|#include <bits/stdc++.h> #define nmax 100005 #define oo 10000000007 #define mod 1000000007 #define reset(x) memset(x, 0, sizeof x) #define F first #define S second #define sonin cin #define sonout cout #define debug(x) cout << "Loli -> " << #x << " : " << x << "\n" #define debugAry(x, a, b, y) for(int y = a; y<=b; y++) cout << #x << "[" << y << "]" << " -> " << x[y] << "\n" #define filename "" #define fileNX freopen(filename".inp", "r", stdin); freopen(filename".out", "w", stdout); #define fileN freopen(filename".inp", "r", stdin); #define fileX freopen(filename".out", "w", stdout); #define toiuuhoa ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define SZ(a) (int) a.size() #define FOU(x,a,b) for (lli x=a;x<=b;x++) #define FOD(x,a,b) for (lli x=a;x>=b;x--) #define FOA(a,b) for(auto &a:b) #define ALLvec(a) a.begin(),a.end() #define REU(x,a,b) for (lli x=a;x<b;x++) #define RED(x,a,b) for (lli x=a;x>b;x--) #define AutoCinAry(a,b,x) for(int a = 1; a<=b; a++) cin >> x[i]; #define dembit1(x) __builtin_popcount(x) #define bit(x,i) ((x>>(i-1))&1ll) #define on(x,i) (x|(1ll<<(i-1))) #define off(x,i) (x&~(1ll<<(i-1))) #define EL cout << "\n"; #define EX exit(0); #define Ary(x, i, j, a) x[(i - 1) * a + j] #define epsinon 1e-8 #define Son_onii_chan main #define times double stime = clock(); #define gettime cerr << "Time executed: " << (clock() - stime) / CLOCKS_PER_SEC * 1000 << "ms.\n"; using namespace std; typedef long long lli; typedef long double ldo; typedef double dou; typedef vector vi; typedef vector vvi; typedef pair<lli, lli> pii; typedef vector vpi; typedef deque dqll;
lli n; vi ary[nmax]; lli dp[nmax][2][2];
lli noovermod(lli &x){ if(x >= mod) x -= mod; return x; }
lli sdp(lli s, lli p, lli c, lli cur, lli ally){ lli res = 0; if(c >= ary[s].size()) return ally; lli t = ary[s][c]; if(t == p){ res = sdp(s, p, c+1, cur, ally); return res; } if(dp[t][cur][ally] >= 0) return dp[t][cur][ally]; dp[t][cur][ally] = 0; res = (sdp(s, p, c+1, cur, 1) * sdp(t, s, 0, cur, 1))%mod; res += (sdp(s, p, c+1, cur, ally) * sdp(t, s, 0, 1-cur, 0))%mod; noovermod(res); dp[t][cur][ally] = res; return res; }
int Son_onii_chan(){ //fileNX toiuuhoa sonin >> n; FOU(i,1,n-1){ lli st, ed; sonin >> st >> ed; ary[st].push_back(ed); ary[ed].push_back(st); } memset(dp, -1, sizeof dp); lli res = sdp(1,0,0,0,0) + sdp(1,0,0,1,0); noovermod(res); sonout << res; return 0; }
Tổng cộng 3 trả lời
dcm
Lại loli -.-