Submission #2210210


Source Code Expand

//package com.company;

import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static long TIME_START, TIME_END;
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner(System.in);
//        MyScanner sc = new MyScanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(System.out);
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));
        TIME_START = System.currentTimeMillis();
        Task.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
//        pw.println("Time used: " + (TIME_END - TIME_START) + ".");
        pw.close();
    }

    public static class Task {
        static final int MOD = 1000000007;
        static long[][] dp;
        static long[] fact;
        static long[] invfact;
        static int N, A, B, C, D;
        public static void solve(MyScanner sc, PrintWriter pw) throws IOException {
            N = sc.nextInt();
            A = sc.nextInt();
            B = sc.nextInt();
            C = sc.nextInt();
            D = sc.nextInt();
            precompute();
            dp = new long[2][N + 1];
            dp[(A - 1) % 2][0] = 1;
            for (int i = A; i <= B; i++) {
                int cutI = i % 2;
                int prevI = (i - 1) % 2;
                for (int j = C; j <= D; j++) {
                    int count = i * j;
                    if (count > N) break;
                    long subChoose = fact[count] * pow(invfact[i], j) % MOD * invfact[j] % MOD;
                    for (int k = count; k <= N; k++) {
                        long choose = fact[k] * invfact[count] % MOD * invfact[k - count] % MOD;
                        long add = dp[prevI][k - count] * subChoose % MOD * choose % MOD;
                        dp[cutI][k] += add;
                        if (dp[cutI][k] >= MOD) dp[cutI][k] -= MOD;
                    }
                }
                for (int j = 0; j <= N; j++) {
                    dp[cutI][j] += dp[prevI][j];
                    if (dp[cutI][j] >= MOD) dp[cutI][j] -= MOD;
                }
                Arrays.fill(dp[prevI], 0);

            }
            pw.println(dp[B % 2][N]);
        }

        public static long pow(long a, int b) {
            if (b == 0) return 1;
            if ((b & 1) == 0) return pow(a * a % MOD, b >> 1);
            return  (a * pow(a * a % MOD, b >> 1) % MOD);
        }

        public static void precompute(){
            fact = new long[1001];
            invfact = new long[1001];
            fact[0] = 1; invfact[0] = (int)pow(1, MOD - 2);
            for (int i = 1; i < 1001; i++) {
                fact[i] = i * fact[i - 1];
                fact[i] %= MOD;
                invfact[i] = (int) pow(fact[i], MOD - 2);
            }
        }



    }

    static class MyScanner {
        StringTokenizer st;
        BufferedReader br;

        public MyScanner(InputStream s){  br = new BufferedReader(new InputStreamReader(s));}

        public MyScanner(FileReader s) throws FileNotFoundException {br = new BufferedReader(s);}

        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {return Integer.parseInt(next());}

        public long nextLong() throws IOException {return Long.parseLong(next());}

        public String nextLine() throws IOException {return br.readLine();}

        public double nextDouble() throws IOException { return Double.parseDouble(next()); }

        public boolean ready() throws IOException {return br.ready();}
    }
}

Submission Info

Submission Time
Task E - Grouping
User zihanw
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3887 Byte
Status CE

Compile Error

./Main.cpp:3:1: error: ‘import’ does not name a type
 import java.io.*;
 ^
./Main.cpp:4:1: error: ‘import’ does not name a type
 import java.lang.reflect.Array;
 ^
./Main.cpp:5:1: error: ‘import’ does not name a type
 import java.math.BigInteger;
 ^
./Main.cpp:6:1: error: ‘import’ does not name a type
 import java.util.*;
 ^
./Main.cpp:8:1: error: expected unqualified-id before ‘public’
 public class Main {
 ^