{"id":129,"date":"2010-02-25T12:22:00","date_gmt":"2010-02-25T04:22:00","guid":{"rendered":"http:\/\/localhost\/?p=129"},"modified":"2010-02-25T12:22:00","modified_gmt":"2010-02-25T04:22:00","slug":"sgu_476","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=129","title":{"rendered":"SGU 476"},"content":{"rendered":"\n<p>\u8fd9\u4e24\u5929\u6211\u5728\u62fc\u547d\u5237SGU\u3002\u3002\u672c\u6765\u60f3\u5f04\u54e5country hero\u723d\u4e00\u4e0b\u7684\u3002\u3002\u7ed3\u679c\u6ca1\u6210\u529f<img decoding=\"async\" src=\"http:\/\/wjmzbmr.com\/wp-content\/uploads\/pic\/other_site\/img_baidu_j_0012.gif\" \/><\/p>\n<p>\u8fd9\u9053\u9898\u662f\u8bf4\u4e00\u4e2a\u6559\u7ec3\uff0c\u67093*N\u4e2a\u5b66\u751f\uff0c\u8981\u628a\u4ed6\u4eec3\u4e2a3\u4e2a\u5206\u6210N\u7ec4\uff0c\u540c\u65f6\u6709k\u4e2a3\u5143\u7ec4\u7684\u5b66\u751f\u4e0d\u80fd\u6210\u4e3a\u4e00\u7ec4\uff0c\u6709\u591a\u5c11\u79cd\u65b9\u6cd5\u3002<\/p>\n<p>\u7531\u4e8eN&lt;=1000\uff0ck&lt;=20\u3002\u3002\u6211\u7684\u529e\u6cd5\u662f\u5229\u7528\u5197\u65a5\u539f\u7406\u6765\u505a\uff0c\u679a\u4e3e\u6bcf\u79fb\u4e00\u79cdk\u4e2a3\u5143\u7ec4\u7684\u5b50\u96c6\uff0c\u7136\u540e\u5206\u522b\u8ba1\u7b97\u5404\u79cd\u65b9\u6cd5\u6570\u3002\u3002\u5c31\u53ef\u4ee5\u4e86\u3002\u3002<\/p>\n<p>\u4f46\u662f\u8fd9\u6837\u662f\u8981TLE\u7684\u3002\u3002\u6211\u53d1\u73b0\u4e0d\u7528\u6bcf\u4e00\u4e2a\u7b97\u51fa\u6765\u90fd\u52a0\u4e00\u4e0b\u3002\u3002\u7531\u4e8e\u5b9e\u9645\u4e0a+\u7684\u503c\u53ea\u6709k+1\u79cd\uff0c\u5f04\u4e00\u4e2aadd\u6570\u7ec4\u8868\u793a\u6bcf\u79cd\u60c5\u51b5\u88ab+\u7684\u6b21\u6570\u3002\u3002\u5230\u6700\u540e\u4e58\u4e00\u4e0b\u5c31\u53ef\u4ee5\u4e86\u3002\u3002<\/p>\n<p>Code\uff1a\u56e0\u4e3a\u662f\u9ad8\u7cbe\u5ea6\uff0c\u6240\u6709\u6211\u7528\u4e86Java<\/p>\n<p>import java.math.*;import java.util.*;import static java.math.BigInteger.*;public class Solution {    static Scanner in=new Scanner(System.in);    static BigInteger[] P;    static int[] Add;    static int[][] L;    static int n,k;    static void CalP()    {        BigInteger now=ONE;        if(n&lt;=k) P[n]=ONE;        for(int i=1;i&lt;=n;i++)        {            now=now.multiply(valueOf(i*3-2));            now=now.multiply(valueOf(i*3-1));            now=now.multiply(valueOf(i*3));            now=now.divide(valueOf(6));            now=now.divide(valueOf(i));            if(n-i&lt;=k)                P[n-i]=now;        }    }    static boolean[] In;    static void dfs(int pos,int ch)    {        if(pos==k)        {                if(ch%2==0)                Add[ch]++;            else                Add[ch]&#8211;;            return;        }        boolean check=true;        for(int i=0;i&lt;3;i++)            if(In[L[pos][i]])            {                check=false;                break;            }        if(check)        {            for(int i=0;i&lt;3;i++)                In[L[pos][i]]=true;            dfs(pos+1,ch+1);            for(int i=0;i&lt;3;i++)                In[L[pos][i]]=false;                }        dfs(pos+1,ch);    }    public static void main(String[] args)     {        n=in.nextInt();k=in.nextInt();        L=new int[k][3];        for(int i=0;i&lt;k;++i)        {            for(int j=0;j&lt;3;j++)                L[i][j]=in.nextInt()-1;        }        P=new BigInteger[k+1];        Add=new int[k+1];        In=new boolean[n*3];        CalP();        dfs(0,0);        BigInteger Ans=ZERO;        for(int i=0;i&lt;=k;i++)            if(P[i]!=null)                Ans=Ans.add(P[i].multiply(valueOf(Add[i])));        System.out.println(Ans);    }}<\/p>\n<p>\u672c\u9ad8\u4eae\u4ee3\u7801\u4f7f\u7528codeHl\u751f\u6210\uff0c<a href=\"http:\/\/hi.baidu.com\/onlys_c\/blog\/item\/ef1149948c22d715d31b707e.html\" target=\"_blank\">\u67e5\u770b\u8be6\u60c5<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u8fd9\u4e24\u5929\u6211\u5728\u62fc\u547d\u5237SGU\u3002\u3002\u672c\u6765\u60f3\u5f04\u54e5country hero\u723d\u4e00\u4e0b\u7684\u3002\u3002\u7ed3\u679c\u6ca1\u6210\u529f \u8fd9\u9053\u9898\u662f\u8bf4\u4e00\u4e2a\u6559\u7ec3\uff0c\u67093*N\u4e2a\u5b66\u751f\uff0c\u8981\u628a\u4ed6\u4eec3\u4e2a3\u4e2a\u5206\u6210N\u7ec4\uff0c\u540c\u65f6\u6709k\u4e2a3\u5143\u7ec4\u7684\u5b66\u751f\u4e0d\u80fd\u6210\u4e3a\u4e00\u7ec4\uff0c\u6709\u591a\u5c11\u79cd\u65b9\u6cd5\u3002 \u7531\u4e8eN&lt;=1000\uff0ck&lt;=20\u3002\u3002\u6211\u7684\u529e\u6cd5\u662f\u5229\u7528\u5197\u65a5\u539f\u7406\u6765\u505a\uff0c\u679a\u4e3e\u6bcf\u79fb\u4e00\u79cdk\u4e2a3\u5143\u7ec4\u7684\u5b50\u96c6\uff0c\u7136\u540e\u5206\u522b\u8ba1\u7b97\u5404\u79cd\u65b9\u6cd5\u6570\u3002\u3002\u5c31\u53ef\u4ee5\u4e86\u3002\u3002 \u4f46\u662f\u8fd9\u6837\u662f\u8981TLE\u7684\u3002\u3002\u6211\u53d1\u73b0\u4e0d\u7528\u6bcf\u4e00\u4e2a\u7b97\u51fa\u6765\u90fd\u52a0\u4e00\u4e0b\u3002\u3002\u7531\u4e8e\u5b9e\u9645\u4e0a+\u7684\u503c\u53ea\u6709k+1\u79cd\uff0c\u5f04\u4e00\u4e2aadd\u6570\u7ec4\u8868\u793a\u6bcf\u79cd\u60c5\u51b5\u88ab+\u7684\u6b21\u6570\u3002\u3002\u5230\u6700\u540e\u4e58\u4e00\u4e0b\u5c31\u53ef\u4ee5\u4e86\u3002\u3002 Code\uff1a\u56e0\u4e3a\u662f\u9ad8\u7cbe\u5ea6\uff0c\u6240\u6709\u6211\u7528\u4e86Java import java.math.*;import java.util.*;import static java.math.BigInteger.*;public class Solution { static Scanner in=new Scanner(System.in); static BigInteger[] P; static int[] Add; static int[][] L; static int n,k; static void CalP() { BigInteger now=ONE; if(n&lt;=k) P[n]=ONE; for(int i=1;i&lt;=n;i++) { now=now.multiply(valueOf(i*3-2)); now=now.multiply(valueOf(i*3-1)); now=now.multiply(valueOf(i*3)); now=now.divide(valueOf(6)); now=now.divide(valueOf(i)); if(n-i&lt;=k) P[n-i]=now; } } static boolean[] In; static void [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/129"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=129"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/129\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=129"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=129"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=129"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}