{"id":103,"date":"2010-09-09T08:22:59","date_gmt":"2010-09-09T00:22:59","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=103"},"modified":"2012-03-03T08:23:25","modified_gmt":"2012-03-03T00:23:25","slug":"hoj-2969-sanguosha-and-card","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/hoj-2969-sanguosha-and-card\/","title":{"rendered":"HOJ 2969. Sanguosha and Card"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>\u77e9\u9635\u4e58\u3002\u3002\u3002<br \/>\n<!--more--><\/p>\n<pre lang=\"cpp\">\r\n\/*\r\n    Author : xiaodao\r\n    Prob : HOJ 2969. Sanguosha and Card\r\n    Status: Accepted\r\n*\/\r\n\r\n\r\n#include <iostream>\r\nusing namespace std;\r\nconst int N = 100;\r\nconst int M = 20092009;\r\n\r\n\r\nclass Matrix {\r\n        friend Matrix operator +(const Matrix& , const Matrix&);\r\n        friend Matrix operator *(const Matrix& , const Matrix&);\r\n    public:\r\n        int d[N][N];\r\n        Matrix(){memset(d, 0, sizeof(d));};\r\n        Matrix& operator *=(const Matrix&);\r\n        void unify();\r\n};\r\n\r\nclass Vector {\r\n        friend Vector operator *(const Vector& , const Matrix&);\r\n    public:\r\n        int d[N];\r\n        Vector(){memset(d, 0, sizeof(d));};\r\n        Vector& operator *=(const Matrix&);\r\n        void unify();\r\n};\r\n\r\n\r\nint n, m, k, q;\r\n\r\nvoid Matrix::unify(){\r\n    for (int i=0;i<n;i++)\r\n        d[i][i] = 1;\r\n}\r\n\r\nvoid Vector::unify(){\r\n    for (int i=0;i<n;i++)\r\n        d[i] = 1;\r\n}\r\n\r\nMatrix operator +(const Matrix&#038; a, const Matrix&#038; b){\r\n    Matrix c;\r\n    for (int i=0;i<n;i++)\r\n        for (int j=0;j<n;j++)\r\n            c.d[i][j] = (a.d[i][j] + b.d[i][j]) % M;\r\n    return c;\r\n}\r\n\r\n\r\nMatrix operator *(const Matrix&#038; a, const Matrix&#038; b) {\r\n    Matrix c; long long buf;\r\n    for(int i=0;i<n;i++)\r\n        for(int j=0;j<n;j++){\r\n            buf = 0;\r\n            for(int k=0;k<n;k++)\r\n                buf += (long long)(a.d[i][k]) * b.d[k][j], buf %= M;\r\n            c.d[i][j] = buf;\r\n        }\r\n    return c;\r\n}\r\n\r\nMatrix&#038; Matrix::operator *=(const Matrix&#038; a){\r\n    (*this) = (*this)*a;\r\n}\r\n\r\nMatrix pow(Matrix a, int b){\r\n    Matrix c; c.unify();\r\n\twhile (b!=0) {\r\n\t\tif ((b&#038;1)==1) c*=a;\r\n\t\ta*=a; b>>=1;\r\n\t}\r\n\r\n\treturn c;\r\n}\r\n\r\n\r\nVector operator *(const Vector& a, const Matrix& b) {\r\n    Vector c;\r\n    for(int i=0;i<n;i++)\r\n        for(int j=0;j<n;j++)\r\n            c.d[i] += b.d[j][i], c.d[i] %= M;\r\n    return c;\r\n}\r\n\r\nVector&#038; Vector::operator *=(const Matrix&#038; a){\r\n    (*this) = (*this)*a;\r\n}\r\n\r\n\r\n\r\n\r\nint main(){\r\n    while(scanf(\"%d%d%d\",&#038;n,&#038;m,&#038;k)==3 &#038;&#038; n!=0){\r\n\t\tMatrix A; Vector V;\r\n\r\n        A.unify(); V.unify();\r\n\t\tint x, y, z;\r\n\t\tfor(int i=0;i<k;i++){\r\n           scanf(\"%d%d%d\", &#038;x, &#038;y, &#038;z);\r\n           A.d[x][y] = z % M;\r\n\t\t}\r\n\r\n\t\tA = pow(A, m);\r\n        V *= A;\r\n\r\n        scanf(\"%d\", &#038;q);\r\n        for (int i=0;i<q-1;i++){\r\n            scanf(\"%d\", &#038;x);\r\n            printf(\"%d \", V.d[x]);\r\n        }\r\n        scanf(\"%d\", &#038;x);\r\n        printf(\"%d\\n\", V.d[x]);\r\n    }\r\n}\r\n<\/pre>\n<h3>Background :<\/h3>\n<p>\u516b\u59d0\u7684\u7a0b\u5e8f\u5e94\u8be5\u4e5f\u662f\u5bf9\u7684\uff0c\u6211\u6309\u7167\u4ed6\u7684\u60f3\u6cd5\u91cd\u5199\u4e86\u4e00\u904d\uff0c\u5404\u79cd\u91cd\u8f7d\u8fd0\u7b97\u7b26\u662f\u6211\u7684\u4e60\u60ef\uff0c<br \/>\n\u81f3\u4e8e\u4e4b\u524d\u7684\u7a0b\u5e8f\u4e3a\u4ec0\u4e48\u9519\uff0c\u6211\u60f3\u662f\u5feb\u901f\u5e42\u65f6\u7206\u6808\u6240\u81f4\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u77e9\u9635\u4e58\u3002\u3002\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-103","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-1F","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/103","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=103"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/103\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=103"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=103"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=103"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}