{"id":527,"date":"2020-08-24T22:43:54","date_gmt":"2020-08-24T14:43:54","guid":{"rendered":"http:\/\/bytew.net\/?p=527"},"modified":"2021-09-08T20:20:07","modified_gmt":"2021-09-08T12:20:07","slug":"%e6%9d%ad%e7%94%b5%e5%a4%9a%e6%a0%a1%e7%ac%ac%e4%b9%9d%e5%9c%ba-1005-resistance","status":"publish","type":"post","link":"https:\/\/bytew.net\/?p=527","title":{"rendered":"\u676d\u7535\u591a\u6821\u7b2c\u4e5d\u573a-1005-Resistance"},"content":{"rendered":"\n

\u65e2\u7136\u5f00\u59cb\u6c34\u535a\u5ba2\u4e86\uff0c\u5c31\u591a\u6c34\u70b9\u5427\u2026\u2026<\/p>\n\n\n\n

\u4f60\u6709\u4e00\u9897\u4ed9\u4eba\u638c\uff08\u6bcf\u4e24\u4e2a\u73af\u81f3\u591a\u6709\u4e00\u4e2a\u4ea4\u70b9\uff09\u5f62\u72b6\u7684\u7535\u8def\uff0c\u4e00\u6761\u8fb9\u7684\u7535\u963b\u662f1\u3002\u4f60\u9700\u8981\u6c42\u51fa\u6240\u6709\u70b9\u5bf9\u4e4b\u95f4\u7684\u7535\u963b\u7684\u548c\uff0c\u5bf91e9+7\u53d6\u6a21\u3002<\/p>\n\n\n\n

\u7b2c\u4e00\u773c\u770b\u5230\u201c\u4ed9\u4eba\u638c\u201d\uff0c\u53ea\u80fd\u60f3\u5230\u67d0\u4e9b\u4ed9\u4eba\u638c\u6570\u636e\u7ed3\u6784\u3002\u518d\u4ed4\u7ec6\u4e00\u770b\uff0c\u624d\u53d1\u73b0\u633a\u5999\u7684\u2026\u2026<\/p>\n\n\n\n\n\n\n\n

OCR\u5b9e\u5728\u662f\u592a\u5f3a\u5927\u4e86\uff0c\u6211\u76f4\u63a5\u590d\u5236\u4e86\u51fa\u9898\u4eba\u7684\u9898\u89e3\uff0c\u53cd\u6b63\u5c31\u662f\u8fd9\u4e48\u505a\u7684\u3002\u6ce8\u610fdfs\u6811\u7684\u6027\u8d28\uff0c\u6240\u6709\u4e0d\u662f\u6811\u8fb9\u7684\u8fb9\u90fd\u662f\u8fd4\u7956\u8fb9\uff0c\u53ef\u4ee5\u5199\u8d77\u6765\u5f88\u7b80\u5355\u3002\u636e\u8bf4fft\u53ef\u80fdtle\uff0c\u4f46\u662f\u6211\u8fd8\u662f\u4e00\u904d\u8fc7\u4e86\uff0c\u53ef\u80fd\u662fkactl\u7684\u6a21\u7248\u5b9e\u5728\u592a\u5feb\u4e86\u5427\uff0c\u725b\u903c\u3002\u3002<\/p>\n\n\n\n

\u51fa\u9898\u4eba\u7684\u9898\u89e3\u5982\u4e0b<\/p>\n\n\n\n

\u8003\u8651\u4e24\u70b9\u4e4b\u95f4\u7684\u7535\u963b\uff0c\u9996\u5148\u4f60\u628a\u8def\u5f84\u62ff\u51fa\u6765\uff0c\u53ef\u4ee5\u770b\u6210\u82e5\u5e72\u6761\u6811\u8fb9\u548c\u73af\u4e32\u8054\u8d77\u6765\uff0c\u4e5f\u5c31\u662f\u76f8\u52a0\u3002\u6240\u4ee5\u8003\u8651\u4e5f\u5c31\u662f\u5bf9\u4e8e\u6bcf\u4e2a\u6811\u8fb9\u548c\u73af\u5206\u522b\u8003\u8651\u5bf9\u7b54\u6848\u7684\u8d21\u732e\u3002
\u6bcf\u4e2a\u6811\u8fb9\u7684\u8d21\u732e\u4e3a\u901a\u8fc7\u6811\u8fb9\u7684\u70b9\u5bf9\uff0c\u4e5f\u5c31\u662f\u4e24\u8fb9\u5927\u5c0f\u76f8\u4e58\u3002\u5bf9\u4e8e\u73af\u8fb9\uff0c\u5047\u8bbe\u4e24\u4e2a\u70b9\u4e0b\u9762\u7684\u5b50\u6811\u5927\u5c0f\u5206\u522b \u4e3a \"S_{i}\" \u548c \"S_{j},\" \u73af\u957f\u4e3al\uff0c\u8ddd\u79bb\u4e3a \"j-i,\" \u90a3\u4e48\u7b49\u6548\u7535\u963b\u4e3a \"j-i\" \u4e0e \"l-j+i\" \u5e76\u8054\uff0c\u4e5f\u5c31\u662f \"(l-j+i)(j-i) / l\" \u5171\u6709 \"S_{i} S_{j}\" \u5bf9\uff0c\u53ef\u4ee5\u5c06\u5f0f\u5b50\u5c55\u5f00\u4e4b\u540e\u4f7f\u7528\u524d\u7f00\u548c\u4e4b\u7c7b\u7684\u65b9\u6cd5\u8ba1\u7b97\uff0c\u4f7f\u7528FFT\u53ef\u80fd\u4f1aTLE\u3002\u3002<\/p>\n\n\n\n

\u4ee3\u7801\u5982\u4e0b<\/p>\n\n\n\n

#include <bits\/stdc++.h>\nusing namespace std;\n\ntemplate <typename A, typename B>string to_string(pair<A, B> p);template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p);template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p);string to_string(const string& s) {  return '\"' + s + '\"';}string to_string(const char* s) {  return to_string((string) s);}string to_string(bool b) {  return (b ? \"true\" : \"false\");}string to_string(vector<bool> v) {  bool first = true;  string res = \"{\";  for (int i = 0; i < static_cast<int>(v.size()); i++) {    if (!first) {      res += \", \";    }    first = false;    res += to_string(v[i]);  }  res += \"}\";  return res;}template <size_t N>string to_string(bitset<N> v) {  string res = \"\";  for (size_t i = 0; i < N; i++) {    res += static_cast<char>('0' + v[i]);  }  return res;}template <typename A>string to_string(A v) {  bool first = true;  string res = \"{\";  for (const auto &x : v) {    if (!first) {      res += \", \";    }    first = false;    res += to_string(x);  }  res += \"}\";  return res;}template <typename A, typename B>string to_string(pair<A, B> p) {  return \"(\" + to_string(p.first) + \", \" + to_string(p.second) + \")\";}template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p) {  return \"(\" + to_string(get<0>(p)) + \", \" + to_string(get<1>(p)) + \", \" + to_string(get<2>(p)) + \")\";}template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p) {  return \"(\" + to_string(get<0>(p)) + \", \" + to_string(get<1>(p)) + \", \" + to_string(get<2>(p)) + \", \" + to_string(get<3>(p)) + \")\";}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {  cerr << \" \" << to_string(H);  debug_out(T...);}\n\n#ifdef LOCAL\n#define debug(...) cerr << \"[\" << #__VA_ARGS__ << \"]:\", debug_out(__VA_ARGS__)\n#else\n#define debug(...) 42\n#endif\n\n#define set0(x) memset(x,0,sizeof(x))\n#define F first\n#define S second\n#define PB push_back\n#define MP make_pair\n#define rep(i, a, b) for(int i = a; i < (b); ++i)\n#define trav(a, x) for(auto& a : x)\n#define all(x) x.begin(), x.end()\n#define sz(x) (int)(x).size()\n\ntypedef long long ll;\ntypedef pair<int,int> pii;\ntypedef pair<ll,ll> pll;\ntemplate<typename T> void read(T &x){\n    x = 0;char ch = getchar();ll f = 1;\n    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}\n    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;\n}\ntemplate<typename T, typename... Args> void read(T &first, Args& ... args) {\n    read(first);\n    read(args...);\n}\n\nconst long double M_PIl = acosl(-1);\ntypedef complex<double> C;\ntypedef vector<double> vd;\ntypedef vector<int> vi;\nvoid fft(vector<C>& a) {\n    int n = sz(a), L = 31 - __builtin_clz(n);\n    static vector<complex<long double>> R(2, 1);\n    static vector<C> rt(2, 1);  \/\/ (^ 10% faster if double)\n    for (static int k = 2; k < n; k *= 2) {\n        R.resize(n); rt.resize(n);\n        auto x = polar(1.0L, M_PIl \/ k); \/\/ M_PI, lower-case L\n        rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i\/2] * x : R[i\/2];\n    }\n    vi rev(n);\n    rep(i,0,n) rev[i] = (rev[i \/ 2] | (i & 1) << L) \/ 2;\n    rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);\n    for (int k = 1; k < n; k *= 2)\n        for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {\n            \/\/ C z = rt[j+k] * a[i+j+k]; \/\/ (25% faster if hand-rolled)  \/\/\/ include-line\n            auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k];        \/\/\/ exclude-line\n            C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           \/\/\/ exclude-line\n            a[i + j + k] = a[i + j] - z;\n            a[i + j] += z;\n        }\n}\nvd conv(const vd& a, const vd& b) {\n    if (a.empty() || b.empty()) return {};\n    vd res(sz(a) + sz(b) - 1);\n    int L = 32 - __builtin_clz(sz(res)), n = 1 << L;\n    vector<C> in(n), out(n);\n    copy(all(a), begin(in));\n    rep(i,0,sz(b)) in[i].imag(b[i]);\n    fft(in);\n    trav(x, in) x *= x;\n    rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);\n    fft(out);\n    rep(i,0,sz(res)) res[i] = imag(out[i]) \/ (4 * n);\n    return res;\n}\n\nconst int mod = 1000000007;\ninline int mul(int x,int y){return 1ll*x*y%mod;}\ninline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}\ninline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}\ninline int sq(int x){return 1ll*x*x%mod;}\nint mpow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(mpow(a,b\/2))) : sq(mpow(a,b\/2)));}\n\nint T,n,m,u,v,vis[200020],depth[200020],sz[200020],fa[200020],ok[200020];\nvector<int> G[200020];\n\nint ans = 0;\n\nvoid dfs(int num){\n    debug(num);\n    vis[num] = 1;\n    sz[num] = 1;\n    for(auto ct:G[num]){\n        if(!vis[ct]){\n            depth[ct] = depth[num]+1;\n            fa[ct] = num;\n            dfs(ct);\n            sz[num]+=sz[ct];\n        }else{\n            if(depth[ct] == depth[num]-1 || depth[ct] > depth[num]+1)continue;\n            debug(num,ct);\n            int p = num;\n            while(p!=ct){\n                debug(p);\n                ok[p] = 0;\n                p = fa[p];\n            }\n        }\n    }\n}\n\nvoid dfs2(int num){\n    debug(num);\n    if(ok[num] && num!=1){\n        ans = add(ans,mul(sz[num],n-sz[num]));\n    }\n    for(auto ct:G[num]){\n        if(depth[ct] == depth[num]+1)dfs2(ct);\n        else{\n            if(depth[ct] == depth[num]-1 || depth[ct] > depth[num]+1)continue;\n            debug(num,ct,depth[num],depth[ct]);\n            int circsize = depth[num]-depth[ct]+1;\n            vector<int> val;\n            val.PB(sz[num]);\n            int v1 = fa[num],v2 = num;\n            while(v2!=ct){\n                val.PB(sz[v1]-sz[v2]);\n                v2 = v1;\n                v1 = fa[v1];\n            }\n            val[val.size()-1]+=n-sz[ct];\n            vd a,b;\n            for(auto ct:val)a.PB(ct);\n            b = a;\n            reverse(all(b));\n            a = conv(a,b);\n            int cv = 0;\n            for(int i=0;i<a.size();i++){\n                ll c = ((ll)(a[i]+0.5))%mod;\n                int d = abs(i-(circsize-1));\n                cv = add(cv,mul(c,mul(d,circsize-d)));\n            }\n            cv = mul(cv,(mod+1)\/2);\n            cv = mul(cv,mpow(circsize,mod-2));\n            ans = add(ans,cv);\n        }\n    }\n}\n\nint main() {\n    read(T);\n    while(T--){\n        ans = 0;\n        read(n,m);\n        fa[1] = 1;\n        for(int i=1;i<=n;i++){\n            vis[i] = 0;\n            depth[i] = 0;\n            ok[i] = 1;\n            G[i].clear();\n        }\n        for(int i=1;i<=m;i++){\n            read(u,v);\n            G[u].PB(v);\n            G[v].PB(u);\n        }\n        debug(1);\n        dfs(1);\n        debug(1);\n        dfs2(1);\n        cout<<ans<<endl;\n    }\n    return 0;\n}<\/code><\/pre>\n ","protected":false},"excerpt":{"rendered":"
\u65e2\u7136\u5f00\u59cb\u6c34\u535a\u5ba2\u4e86\uff0c\u5c31\u591a\u6c34\u70b9\u5427\u2026\u2026 \u4f60\u6709\u4e00\u9897\u4ed9\u4eba\u638c\uff08\u6bcf\u4e24\u4e2a\u73af\u81f3\u591a\u6709\u4e00\u4e2a\u4ea4\u70b9\uff09\u5f62\u72b6\u7684\u7535\u8def\uff0c\u4e00\u6761\u8fb9\u7684\u7535\u963b\u662f1\u3002\u4f60\u9700\u8981 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/527"}],"collection":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=527"}],"version-history":[{"count":1,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/527\/revisions"}],"predecessor-version":[{"id":528,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/527\/revisions\/528"}],"wp:attachment":[{"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=527"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=527"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=527"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}