Submission #341547

#	Time	Username	Problem	Language	Result	Execution time	Memory
341547		KWang31	Tents (JOI18_tents)	Java	100 / 100	422 ms	82100 KiB

tents

import java.io.*; import java.util.*;
public class tents{
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        
    } 
    public static class Pair implements Comparable<Pair>{
        int vtx; int val;
        public Pair(int a, int b){
            this.vtx=a; this.val=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.vtx<other.vtx)return -1;
            return 1;
        }
    }
    static int MOD=1000000007;
    static int[] rk, p,siz;
    public static void main(String[] args){
        FastReader br=new FastReader();
        int N=br.nextInt(); int M=br.nextInt();
        long[][] dp=new long[N+1][M+1];
        for (int i = 0; i <=N; i++) {
            dp[i][0]=1;
        }
        for (int i = 1; i <=M; i++) {
            dp[0][i]=1;
        }
        for (int x = 1; x <=N; x++) {
            for (int y = 1; y <=M; y++) {//x rows, y columns
                dp[x][y]=dp[x][y-1];
                if(x>=2){dp[x][y]+=(x*(x-1)/2)*dp[x-2][y-1]; dp[x][y]%=MOD;}
                dp[x][y]+=dp[x-1][y-1]*4*x; dp[x][y]%=MOD;
                if(y>=2)dp[x][y]+=dp[x-1][y-2]*x*(y-1); dp[x][y]%=MOD;
            }
        }
        System.out.println(dp[N][M]-1);
    }
    
    public static int find(int x, int[] p){
        if(p[x]==x)return x;
        int ans=find(p[x],p); p[x]=ans; return ans;
    }
    
    public static void merge(int a, int b) {
        if(rk[a]<rk[b]) {
            p[a]=b; siz[b]+=siz[a];
        }else if(rk[a]==rk[b]) {
            p[a]=b; rk[b]++;siz[b]+=siz[a];
        }else {
            p[b]=a; siz[a]+=siz[b];
        }
    }
    
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52