2020-03-08 18:30:28 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> #define ALL(A) (A).begin(), (A).end() #define ll long long #define rep(i, n) for (int i = 0; i < (n); i++) using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const ll mod = 1e5; int ans[100][3003]; int memo[100][3003]; // memo[i][j]:= i人で合計jとなるように配る方法の総数 x[0]<=x[1]<=x[2]<= x[i]; int n,m,s; int f(int n,int k,int d){ // n 人で 合計 k となるようにわける方法 if(ans[n][k]++)return memo[n][k]; // 0 人で 合計 0 となるように分ける方法は1通り if(n==0)return !k; // f(n-1,k) は次の人にわたす場合 // k-n>=0 ? f(n,k-n) はとりあえず現時点の人が1加算する場合 //cout << "n = " << n << " k = " << k << " d = " << d << endl; return memo[n][k] = ( f(n-1,k,d) + (k-n>=0&&d+1<m?f(n,k-n,d+1):0) ) % mod; } int main(void){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); cin >> n >> m >> s; s -= n*n; // 各マスは0以上m-1以下の整数になる s -= ( n * n ) * ( (n*n) - 1 ) / 2; // 各マスは広義単調増加列になる cout << s << endl; cout << f(n*n,s,0)%mod << endl; }
RECOMMEND