\u9898\u76ee\u63cf\u8ff0\uff1a
\nA\u4e3a\u4e00\u4e2a\u65b9\u9635\uff0c\u5219Tr A\u8868\u793aA\u7684\u8ff9\uff08\u5c31\u662f\u4e3b\u5bf9\u89d2\u7ebf\u4e0a\u5404\u9879\u7684\u548c\uff09\uff0c\u73b0\u8981\u6c42Tr(A^k)%9973\u3002
\n\u8f93\u5165\uff1a
\n\u6570\u636e\u7684\u7b2c\u4e00\u884c\u662f\u4e00\u4e2aT\uff0c\u8868\u793a\u6709T\u7ec4\u6570\u636e\u3002
\n\u6bcf\u7ec4\u6570\u636e\u7684\u7b2c\u4e00\u884c\u6709n(2 <= n <= 10)\u548ck(2 <= k < 10^9)\u4e24\u4e2a\u6570\u636e\u3002\u63a5\u4e0b\u6765\u6709n\u884c\uff0c\u6bcf\u884c\u6709n\u4e2a\u6570\u636e\uff0c\u6bcf\u4e2a\u6570\u636e\u7684\u8303\u56f4\u662f[0,9]\uff0c\u8868\u793a\u65b9\u9635A\u7684\u5185\u5bb9\u3002
\n\u8f93\u51fa\uff1a
\n\u5bf9\u5e94\u6bcf\u7ec4\u6570\u636e\uff0c\u8f93\u51faTr(A^k)%9973\u3002
\n\u6837\u4f8b\u8f93\u5165\uff1a
\n2
\n2 2
\n1 0
\n0 1
\n3 99999999
\n1 2 3
\n4 5 6
\n7 8 9
\n\u6837\u4f8b\u8f93\u51fa\uff1a
\n2
\n2686 <\/p>\n
\u603b\u7ed3\uff1a
\n– \u8f93\u5165\u6ca1\u6709\u770b\u6e05\u695a\uff0c\u4e60\u60ef\u6027\u7684\u81ea\u6709\u8f93\u5165\uff0c\u5176\u5b9e\u662f\u6709\u6570\u91cf\u9650\u5236\u7684<\/p>\n
– \u4e0d\u8981\u8bbe\u7f6e\u5f88\u591a\u5168\u5c40\u53d8\u91cf\uff0c\u6700\u540e\u4f1a\u6df7\u5728\u4e00\u8d77\uff0c\u53ef\u4ee5\u4f7f\u7528\u7ed3\u6784\u4f53\uff0c\u5f88\u597d\u7528<\/p>\n
– \u77e9\u9635\u4e58\u6cd5\u4e0d\u8981\u81ea\u5df1\u81c6\u60f3\uff0c\u8981\u80cc\u8c03
\n<\/p>\n
\u4ee3\u7801<\/p>\n
#include<iostream>\r\n#include<stdio.h>\r\n#include<cstdio>\r\n#include<math.h>\r\n#include<string.h>\r\n#define M 9973\r\n#define H 102\r\nusing namespace std;\r\ntypedef struct Matrix{\r\n int v[H][H];\r\n} matrix;\r\n\/\/Matrix E;\r\n\/\/Matrix Ans;\r\nMatrix Mul(Matrix aa,Matrix bb,int n){\r\n\/\/ cout<<\"get in now\"<<endl;\r\n Matrix cc;\r\n memset(cc.v,0,sizeof(cc.v)); \/\/\u5c06\u6240\u6709\u7684v\u7f6e0\r\n for(int i=0;i<n;i++){\r\n for(int j=0;j<n;j++){\r\n for(int c=0;c<n;c++){\r\n cc.v[i][j]+=aa.v[i][c]*bb.v[c][j];\r\n cc.v[i][j]%=M;\r\n }\r\n }\r\n }\r\n return cc;\r\n} \r\n \r\nMatrix pow(Matrix E,int k,int n){ \/\/\u6c42x^y x\u53ef\u80fd\u662flonglong E(n)^k 910^9==10^10 <21\u4ebf\r\n Matrix Ans;\r\n memset(Ans.v,0,sizeof(Ans.v));\r\n for(int i=0;i<n;i++){\r\n Ans.v[i][i]=1;\r\n }\r\n while(k!=0){\r\n if(k%2==1){\r\n Ans=Mul(E,Ans,n);\r\n }\r\n k\/=2;\r\n E=Mul(E,E,n);\r\n }\r\n return Ans;\r\n}\r\n \r\nint main(){\r\n int t,n;\r\n int k;\r\n Matrix E;\r\n Matrix Ans;\r\n cin>>t;\r\n for(int j=0;j<t;j++){\r\n cin>>n>>k;\r\n for(int a=0;a<n;a++){\r\n for(int b=0;b<n;b++){\r\n cin>>E.v[a][b];\r\n E.v[a][b]%=M;\r\n }\r\n }\r\n \/\/\u77e9\u9635\u8f93\u5165\u5b8c\u6bd5\uff1b\r\n \r\n Ans=pow(E,k,n);\r\n int count=0;\r\n for(int p=0;p<n;p++){\r\n count=count + Ans.v[p][p];\r\n count%=M;\r\n }\r\n cout<<count<<endl;\r\n \r\n }\r\n return 0;\r\n}\r\n\/**************************************************************\r\n Problem: 1443\r\n User: WZDCJ0206\r\n Language: C++\r\n Result: Accepted\r\n Time:20 ms\r\n Memory:1688 kb\r\n****************************************************************\/\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"\u9898\u76ee\u63cf\u8ff0\uff1a A\u4e3a\u4e00\u4e2a\u65b9\u9635\uff0c\u5219Tr A\u8868\u793aA\u7684\u8ff9\uff08\u5c31\u662f\u4e3b\u5bf9\u89d2\u7ebf\u4e0a\u5404\u9879\u7684\u548c\uff09\uff0c\u73b0\u8981\u6c42Tr(A^k)%9973\u3002 \u8f93 […]<\/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","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-254","post","type-post","status-publish","format-standard","hentry","category-python"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/s9Hs6X-1443","_links":{"self":[{"href":"https:\/\/tastestars.com\/index.php\/wp-json\/wp\/v2\/posts\/254","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tastestars.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tastestars.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tastestars.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tastestars.com\/index.php\/wp-json\/wp\/v2\/comments?post=254"}],"version-history":[{"count":3,"href":"https:\/\/tastestars.com\/index.php\/wp-json\/wp\/v2\/posts\/254\/revisions"}],"predecessor-version":[{"id":258,"href":"https:\/\/tastestars.com\/index.php\/wp-json\/wp\/v2\/posts\/254\/revisions\/258"}],"wp:attachment":[{"href":"https:\/\/tastestars.com\/index.php\/wp-json\/wp\/v2\/media?parent=254"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tastestars.com\/index.php\/wp-json\/wp\/v2\/categories?post=254"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tastestars.com\/index.php\/wp-json\/wp\/v2\/tags?post=254"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}