{"id":381,"date":"2020-04-25T15:12:53","date_gmt":"2020-04-25T07:12:53","guid":{"rendered":"http:\/\/nocriz.com\/?p=381"},"modified":"2021-09-08T20:20:07","modified_gmt":"2021-09-08T12:20:07","slug":"noi-online-r2-%e9%a2%98%e8%a7%a3","status":"publish","type":"post","link":"https:\/\/nocriz.com\/?p=381","title":{"rendered":"NOI Online R2 \u9898\u89e3"},"content":{"rendered":"\n

\u7531\u4e8e\u9519\u8bef\u7684\u6bd4\u8d5b\u7b56\u7565\u3001\u8fc7\u5ea6\u7684\u6c34\u7fa4\u548c\u6211\u65e9\u4e0a\u4e0d\u77e5\u9053\u6709\u8fd9\u4e2a\u6bd4\u8d5b\u7684\u6b8b\u9177\u4e8b\u5b9e\uff0c\u6211\u6700\u591a\u5c31\u62ff200\u5206\u4e86\uff0c\u60e8\u8d25\u2026\u2026\u6bd4\u8d5b\u7ed3\u675f15\u5206\u949f\u4e4b\u540e\u624d\u5199\u5b8cC\u3002\u65e0\u8bba\u5982\u4f55\uff0c\u6211\u4f3c\u4e4e\u8fd8\u662f\u53ef\u4ee5\u653e\u4e00\u4e0b\u4ee3\u7801\uff0c\u6c34\u4e00\u7bc7\u535a\u5ba2\u7684\uff1f<\/p>\n\n\n\n

\u6240\u6709\u4ee3\u7801\u672a\u7ecf\u8bc1\u5b9e\u3002<\/p>\n\n\n\n\n\n\n\n

\u7b2c\u4e00\u9898<\/h2>\n\n\n\n
#include <iostream>\n\nusing namespace std;\ntypedef long long ll;\nint gcd(int a,int b){\n\treturn b != 0?gcd(b,a%b):a;\n}\nint T,p1,p2,k;\nint main(){\n\tfreopen(\"color.in\",\"r\",stdin);\n\tfreopen(\"color.out\",\"w\",stdout);\n\tios::sync_with_stdio(false);\n\tcin>>T;\n\twhile(T--){\n\t\tcin>>p1>>p2>>k;\n\t\tint d = gcd(p1,p2);\n\t\tp1\/=d;\n\t\tp2\/=d;\n\t\tif(p1>p2)swap(p1,p2);\n\t\tint lim = (p2+p1-2)\/p1;\n\t\tif(lim>=k){\n\t\t\tcout<<\"No\\n\";\n\t\t}else{\n\t\t\tcout<<\"Yes\\n\";\n\t\t}\n\t}\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
\u7b2c\u4e8c\u9898<\/h2>\n\n\n\n
#include <algorithm>\n#include <iostream>\n#include <cstring>\n#include <vector>\nchar buf[1000000],*p1,*p2;\ninline bool isdigit(const char &ch){\n\treturn ch>=48&&ch<=57;\n}\ninline char nextchar(){\n\treturn p1==p2&&(p2=buf+fread(p1=buf,1,1000000,stdin),p1==p2)?EOF:*p1++;\n}\ninline void getint(int &des){\n\tchar ch=des=0;\n\twhile(!isdigit(ch)&&ch!=EOF)ch=nextchar();\n\twhile(isdigit(ch))des=des*10+ch-48,ch=nextchar();\n}\nusing namespace std;\ntypedef long long ll;\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 pow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(pow(a,b\/2))) : sq(pow(a,b\/2)));}\n\nint n,A[1000010],V[1000010];\nvector<int> po[1000010];\nint d1[1000010],d2[1000010];\ninline void update(const int &left,const int &right,const int &w){\n\tregister int i;\n\tfor(i=left;i<=1000005;i+=i&-i){\n\t\td1[i]=add(d1[i],w);\n\t\td2[i]=add(d2[i],mul(left,w));\n\t}\n\tfor(i=right;i<=1000005;i+=i&-i){\n\t\td1[i]=sub(d1[i],w);\n\t\td2[i]=sub(d2[i],mul(right,w));\n\t}\n}\ninline int query(const int &left,const int &right){\t\t\t\t\t\t\t\/\/\u00d7\u00f3\u00b1\u00d5\u00d3\u00d2\u00bf\u00aa\n\tregister int i;register int ans=0;\n\tfor(i=left-1;i>=1;i-=i&-i){\n\t\tans=sub(ans,(1ll*d1[i]*left-d2[i]+mod)%mod);\n\t}\n\tfor(i=right-1;i>=1;i-=i&-i){\n\t\tans=(1ll*d1[i]*right-d2[i]+ans+mod)%mod;\n\t}\n\treturn ans;\n}\n\nint main() {\n\tfreopen(\"sequence.in\",\"r\",stdin);\n\tfreopen(\"sequence.out\",\"w\",stdout);\n\tgetint(n);\n\tfor(int i=0;i<n;i++){\n\t\tgetint(A[i]);V[i] = A[i];\n\t}\n\tsort(V,V+n);\n\tint m = unique(V,V+n)-V;\n\tfor(int i=0;i<n;i++){\n\t\tA[i] = lower_bound(V,V+m,A[i])-V;\n\t\tpo[A[i]].push_back(i);\n\t}\n\tfor(int i=0;i<n;i++)reverse(po[i].begin(),po[i].end());\n\tint ans = 0,cu = 0;\n\tint cv = 0;\n\tfor(int i=0;i<n;i++){\n\t\tif(i == po[A[i]].back()){\n\t\t\tcv+=1;\n\t\t\tupdate(i+1,n-1+2,1);\n\t\t}\n\t\tcu = add(cu,sq(cv));\n\t}\n\tfor(int i=0;i<n;i++){\n\t\tans = add(ans,cu);\n\t\tpo[A[i]].pop_back();\n\t\tint r = po[A[i]].size()?po[A[i]].back():n;\n\t\tcu = sub(cu,mul(2,query(i+1,r-1+2)));\n\t\tcu = add(cu,r-i);\n\t\tupdate(i+1,r-1+2,mod-1);\n\t}\n\tcout<<ans<<endl;\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
\u7b2c\u4e09\u9898<\/h2>\n\n\n\n
\u8bbedp[i][j]\u4e3a\u7b2ci\u53f7\u70b9\u7684\u5b50\u6811\u4e2d\u9009\u53d6j\u5bf9\u914d\u5bf9\u8282\u70b9\u7684\u9009\u62e9\u65b9\u6848\u6570\u3002<\/p>\n\n\n\n
\u53d6\"f_i = dp[1][i]*(n/2-i)!\"\uff0c\u7b54\u6848\u5e8f\u5217\u4e3a\"g_i\"\uff0c\u90a3\u4e48\u6211\u4eec\u6709\uff1a<\/p>\n\n\n\n
   <\/span>   <\/span>\"\[f_k = sum_{i=k}^nC_k^i g_k\]\"<\/p><\/p>\n\n\n\n
\u4e8e\u662f\u4f7f\u7528\u4e8c\u9879\u5f0f\u53cd\u6f14\u5c31\u53ef\u4ee5\u6c42\u51fa\u7b54\u6848\u4e86\u3002<\/p>\n\n\n\n
#include <algorithm>\n#include <iostream>\n#include <cstring>\n#include <vector>\n\nusing namespace std;\nint mod = 998244353;\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)));}\nconst int N = 1000000;\nint fac[N+10],invfac[N+10];\n\n\nint C(int n,int m){\n\tif(n<0 || m<0 || m>n)return 0;\n\treturn mul(fac[n],mul(invfac[m],invfac[n-m]));\n}\nint n,u,v;\nvector<int> G[5050];\nchar ch[5050];\nint dp[5050][5050],sz[5050],sc[5050][2];\n\nvoid dfs(int num,int cf = -1){\n\tdp[num][0] = 1;\n\tfor(auto ct:G[num]){\n\t\tif(ct == cf)continue;\n\t\tdfs(ct,num);\n\t\tvector<int> ndp(sz[num]+sz[ct]+2,0);\n\t\tfor(int i=0;i<=sz[num];i++){\n\t\t\tfor(int j=0;j<=sz[ct];j++){\n\t\t\t\tndp[i+j] = add(ndp[i+j],mul(dp[num][i],dp[ct][j]));\n\t\t\t}\n\t\t}\n\t\tfor(int i=0;i<ndp.size();i++)dp[num][i] = ndp[i];\n\t\tsz[num]+=sz[ct];\n\t\tsc[num][0]+=sc[ct][0];\n\t\tsc[num][1]+=sc[ct][1];\n\t}\n\tvector<int> ndp(sz[num]+2,0);\n\tfor(int i=0;i<=sz[num];i++){\n\t\tif(!dp[num][i])continue;\n\t\tndp[i] = add(ndp[i],dp[num][i]);\n\t\tint ca = sc[num][(ch[num]-'0')^1]-i;\n\t\tif(ca<0)break;\n\t\tndp[i+1] = add(ndp[i+1],mul(dp[num][i],ca));\n\t}\n\tfor(int i=0;i<ndp.size();i++)dp[num][i] = ndp[i];\n\tsz[num] +=1;\n\tsc[num][ch[num]-'0']+=1;\n}\nint main() {\n\t\/\/freopen(\"match.in\",\"r\",stdin);\n\t\/\/freopen(\"match.out\",\"w\",stdout);\n\tfac[0] = 1;\n\tfor(int i=1;i<=N;i++)fac[i] = mul(fac[i-1],i);\n\tinvfac[N] = mpow(fac[N],mod-2);\n\tfor(int i=N-1;i>=0;i--) invfac[i] = mul(invfac[i+1],i+1);\n\tcin>>n;\n\tcin>>(ch+1);\n\tfor(int i=1;i<n;i++){\n\t\tcin>>u>>v;\n\t\tG[u].push_back(v);\n\t\tG[v].push_back(u);\n\t}\n\tdfs(1);\n\tfor(int i=0;i<=n\/2;i++){\n\t\tdp[1][i] = mul(dp[1][i],fac[n\/2-i]);\n\t}\n\tfor(int i=0;i<=n\/2;i++){\n\t\tint cans = 0;\n\t\tfor(int j=i;j<=n\/2;j++){\n\t\t\tif((j-i)%2 == 1){\n\t\t\t\tcans = sub(cans,mul(C(j,i),dp[1][j]));\n\t\t\t}else{\n\t\t\t\tcans = add(cans,mul(C(j,i),dp[1][j]));\n\t\t\t}\n\t\t}\n\t\tcout<<cans<<\" \\n\"[i == n\/2];\n\t}\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
Total Page Visits: 5312<\/span><\/div>\n ","protected":false},"excerpt":{"rendered":"
\u7531\u4e8e\u9519\u8bef\u7684\u6bd4\u8d5b\u7b56\u7565\u3001\u8fc7\u5ea6\u7684\u6c34\u7fa4\u548c\u6211\u65e9\u4e0a\u4e0d\u77e5\u9053\u6709\u8fd9\u4e2a\u6bd4\u8d5b\u7684\u6b8b\u9177\u4e8b\u5b9e\uff0c\u6211\u6700\u591a\u5c31\u62ff200\u5206\u4e86\uff0c\u60e8\u8d25\u2026\u2026\u6bd4\u8d5b\u7ed3\u675f15\u5206 […]<\/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:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/381"}],"collection":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=381"}],"version-history":[{"count":2,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/381\/revisions"}],"predecessor-version":[{"id":388,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/381\/revisions\/388"}],"wp:attachment":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=381"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=381"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=381"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}