結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
![]() |
提出日時 | 2020-03-09 17:47:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 5,809 bytes |
コンパイル時間 | 1,975 ms |
コンパイル使用メモリ | 183,796 KB |
実行使用メモリ | 35,456 KB |
最終ジャッジ日時 | 2024-11-08 10:54:07 |
合計ジャッジ時間 | 5,222 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include "bits/stdc++.h"#include <random>#include <algorithm>#include <unordered_set>#define rep(i,n) for(int i = 0; i < n; i++)typedef long long ll;typedef unsigned long long ull;using namespace std;#define vll vector<vector<long long>>#define vl vector<long long>#define vi vector<int>#define vii vector<vector<int>>#define pb push_back#define pf push_front#define ld long double#define Sort(a) sort(a.begin(),a.end())#define cSort(a,cmp) sort(a.begin(),a.end(),cmp)#define reSort(a) sort(a.rbegin(), a.rend())static const ll llMAX = numeric_limits<long long>::max();static const int intMAX = numeric_limits<int>::max();static const ll llMIN = numeric_limits<long long>::min();static const int intMIN = numeric_limits<int>::min();static const ll d_5 = 100000;static const ll d9_7 = 1000000007;static const ll d_9 = 1000000000;static const double PI=3.14159265358979323846;template<class T>void Printvector(std::vector<T> a){int size = a.size();rep(i,size){cout<<a[i]<<" ";}cout<<endl;}template<class T>void Printvector(std::vector<std::vector<T>> a){int size = a.size();rep(i,size){int size2=a[i].size();rep(j,size2){cout<<a[i][j]<<" ";}cout<<endl;}cout<<endl;}template<class T>vector<T> getaccum(vector<T> a){int size=a.size();vector<T> ans(size);ans[0]=a[0];for(int i=0;i<size-1;i++){ans[i+1]=ans[i]+a[i+1];//ans[i+1]%=d9_7;}return ans;}template<class T>vector<vector<T>> getaccum2D(vector<vector<T>> a){int sizey=a.size();int sizex=a[0].size();vector<vector<T>> ans(sizey,vector<T>(sizex,0));//ans=a;ans[0][0]=a[0][0];for(int i=1;i<sizex;i++){ans[0][i]=ans[0][i-1]+a[0][i];}for(int i=1;i<sizex;i++){ans[i][0]=ans[i-1][0]+a[i][0];}for (int i = 0; i < sizey-1; i++)for (int j = 0; j < sizex-1; j++)ans[i+1][j+1] = ans[i][j+1] + ans[i+1][j] - ans[i][j] + a[i+1][j+1];return ans;}ll getaccumnum(vector<ll> accum,int l,int r){//閉区間[l,r]の総和if(l==0){return accum[r];}else{return accum[r]-accum[l-1];}}template<class T>T getaccumnum2D(vector<vector<T>>& accum,int x1,int y1,int x2,int y2){//2の方が右下、閉区間T ans=accum[y2][x2];if(x1==0 && y1==0){;}else if(x1>0 && y1==0){ans-=accum[y2][x1-1];}else if(x1==0 && y1>0){ans-=accum[y1-1][x2];}else{ans-=accum[y1-1][x2];ans-=accum[y2][x1-1];ans+=accum[y1-1][x1-1];}return ans;}ll digitpower(ll a,ll b){//aのb乗を計算if(b==1){return a;}else if(b==0){return 1;}int mode=0;if(b%2==1){ll tmp = digitpower(a,(b-1)/2);if(mode==1){tmp%=d9_7;}tmp*=tmp;if(mode==1){tmp%=d9_7;}tmp*=a;if(mode==1){return tmp%d9_7;}else{return tmp;}}else{ll tmp = digitpower(a,(b)/2);if(mode==1){tmp%=d9_7;}tmp*=tmp;if(mode==1){tmp%=d9_7;}if(mode==1){return tmp%d9_7;}else{return tmp;}}}vl facs(2000010,-1);ll Factrial(ll num){if(facs[num]!=-1){return facs[num];}if(num==1||num<=0){return 1;}else if(num<0){printf("ERROR_minus\n");return 0;}else{facs[num]=(num*Factrial(num-1))%d9_7;return facs[num];}}long long modinv(long long a, long long m) {//modの逆元long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}vl invs(2000010,-1);ll linercomb(ll n,ll k, ll mod){//n,kの線形時間で求めるif(n<k)return 0;if(n<0)return 0;if(k==0 || k==n)return 1;ll ans=Factrial(n);if(invs[k]==-1){invs[k]=modinv(Factrial(k),mod);}ans*=invs[k];ans%=d9_7;ll k1=Factrial(n-k);k1%=mod;ans*=modinv(k1,mod);ans%=mod;return ans;}unordered_map<ll,ll> prime_factor(int64_t n) {unordered_map<ll,ll> ret;for(int64_t i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}struct datas{ll p;ll q;};/*bool cmp(const datas &a, const datas &b){return a.num < b.num;}*/template<class T>T gcd(T a,T b){if(a==0){return b;}else if(b==0){return a;}while(1) {if(a < b) swap(a, b);if(!b) break;a %= b;}return a;}int LCS(string s,string t) {int n=s.size();int m=t.size();vector<vector<int>> dp=vector<vector<int>>(n+1,vector<int>(m+1,0));for (int i=0; i<n; ++i) {for (int j=0; j<m; ++j) {if (s[i] == t[j]) {dp[i+1][j+1] = dp[i][j] + 1;}else {dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);}}}return dp[n][m];}//素数列挙#define P 100000vl primes;vl primenum(P+1);vector<bool> bprime(P+200);ll searchprime(ll max){//発見した素因数の個数を返す//max+=180;bprime[1]=false;// cout<<"rrr"<<endl;;//cout<<max<<" "<<bprime.size()<<endl;for(ll i=2;i<=max;i++){bprime[i]=true;}//// cout<<"r";ll nowprimes=1;primes.pb(2);for(ll i=4;i<max;i+=2){bprime[i]=false;}// cout<<"e";for(ll i=3;i<=max;i+=2){if(bprime[i]==true){//primes[nowprimes]=i;primes.pb(i);nowprimes++;for(ll j=2;i*j<=max;j++){bprime[i*j]=false;}}}return nowprimes;}int main(void){ll n;cin>>n;rep(i,n){Factrial(i);}ll ans=linercomb(10+n-1,n,d9_7);cout<<ans<<endl;return 0;}//<<std::setprecision(30)//重複削除/* std::sort(vec.begin(), vec.end());vec.erase(std::unique(vec.begin(), vec.end()), vec.end());*/