SGU 476

这两天我在拼命刷SGU。。本来想弄哥country hero爽一下的。。结果没成功





import java.math.*;import java.util.*;import static java.math.BigInteger.*;public class Solution { static Scanner in=new Scanner(; static BigInteger[] P; static int[] Add; static int[][] L; static int n,k; static void CalP() { BigInteger now=ONE; if(n<=k) P[n]=ONE; for(int i=1;i<=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<=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]–; return; } boolean check=true; for(int i=0;i<3;i++) if(In[L[pos][i]]) { check=false; break; } if(check) { for(int i=0;i<3;i++) In[L[pos][i]]=true; dfs(pos+1,ch+1); for(int i=0;i<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<k;++i) { for(int j=0;j<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<=k;i++) if(P[i]!=null) Ans=Ans.add(P[i].multiply(valueOf(Add[i]))); System.out.println(Ans); }}


3 thoughts on “SGU 476

  1. of course like your web-site but you need to test the spelling on several of your posts. Several of them are rife with spelling problems and I find it very bothersome to inform the reality nevertheless Ill certainly come again again.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>