Submission #1354166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354166		vahagng	Lego Wall (EGOI22_legowall)	C++20	62 / 100	13 ms	18136 KiB

Main

///////mon777///////
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
#include <climits>
#include <complex>

using namespace std;

// typedefs//
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;

// define//
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define all(o) (o).begin(), (o).end()
#define chkpav cout << -1 << '\n'
#define ppf pop_front
#define pf push_front
#define rall(v) v.rbegin(), v.rend()
#define inf 1e18
#define infint 1e9
#define PII pair<int, int>

const ll N = 1e5 + 2;
const ll mod = 1e9 + 7;

void setIO(string name = "")
{
    if (!name.empty())
    {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

void FastIO()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int reverseDigits(int n)
{
    int revNum = 0;
    int basePos = 1;
    if (n > 0)
    {
        reverseDigits(n / 10);
        revNum += (n % 10) * basePos;
        basePos *= 10;
    }
    return revNum;
}

void setPrecision(int x)
{
    if (x == 0)
        return;
    cout.setf(ios::fixed);
    cout.precision(x);
}

vector<ll> fibo(int x) {

    vector<ll> fib(x + 1, 0);
    
    fib[0]=fib[1]=1;
    if (x <= 1) return fib;
  
    for (int i = 2; i <= x; ++i){
        fib[i] = fib[i - 1] + fib[i - 2];
        fib[i]%=mod;
    }
    return fib;
}

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b)
{
    return (a * b) / gcd(a, b);
}

/*

     0.1 2 3 4   5  6  7
0    1
1    1 1
2    1 2 1
3    1 3 3 1
4    1 4 6 4 1
5    1 5 10 10 5 1
6    1 6 15 20 15 6 1
7    1 7 21 35 35 21 7 1

c72= 6*7/2=21;

*/

// ll binlen(ll x) {// binarniov nerkayacman erkarutyun
//     if (x == 0) return -1;
//     return 64 - __builtin_clzll(x);
// }

ll C[750][750];

void cnk(){
    C[0][0]=1;
    for(int i=1;i<750;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j){
            if(j>i) C[i][j]=0;
            else if(i==j) C[i][j]=1;
            else C[i][j]=C[i-1][j-1]+C[i-1][j];
            C[i][j]%=mod;
        }
    }
    return;
}

ll binpow(int x, int y){
    if(y==0) return 1;
    ll res= binpow(x, y/2);
    res*=res;
    res%=mod;
    if(y&1) res*=x; res%=mod;
    return res;

}

///////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////
ll totalner[750], G[750];
void solve() {
    int h, w;
    cin>>w>>h;
    if(w>=h) {
        cnk();

        // for(int i =0;i<=w;++i){
        //     for(int j=0;j<=i;++j){
        //         cout<<C[i][j]<<' ';
        //     }
        //     cout<<'\n';
        // }

        vector<vector<ll>>dp(w+1, vector<ll> (h+1));
        for(int i=1; i<=w;++i){
            dp[1][i]= C[h][i];
        }
        for(int i=2;i<w;++i){
            for(int c=1;c<=h;++c){
                for(int k=1;k<=h;++k){
                    if(h - k < c) break;
                    dp[i][c]+=(dp[i-1][k]* C[h-k][c]) % mod;
                    dp[i][c]%=mod;
                }
            }
        }
        ll ans=0;
        for(int i=1;i<=h;++i){
            ans+=dp[w-1][i];
            ans%=mod;
        }
        cout<<ans<<'\n';

    }
    else {

        vector<ll> F = fibo(w+2);

        for(int i=1;i<=w+1;++i){
            totalner[i]=binpow(F[i], h);
            totalner[i]%=mod;
        }

        G[1]=totalner[1];
        for(int i=2;i<=w;++i){
            G[i]=totalner[i];
            for(int j=1;j<i;++j){
                G[i] -= (G[j]*totalner[i-j]) % mod;
                G[i] = (G[i]%mod+mod)%mod;
            }
        }

        // for(int i=0;i<=w;++i){
        //     cout<<totalner[i]<<' ';
        // }
        // cout<<'\n';
        // for (int i = 0; i <= w; ++i)
        // {
        //     cout << G[i] << ' ';
        // }
        // cout<<'\n';
        cout<<G[w]<<'\n';

        // cout<<"fibo "<<'\n';
        // for(int i=0;i<=w+1;++i){
        //     cout<<F[i]<<' ';
        // }
    }

}

int main()
{ // int32_t

    // setIO("fenceplan");
    FastIO();

    // setPrecision(1);

    int test_case = 1;
    // cin >> test_case;

    while (test_case--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 12
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 6