結果
問題 | No.1629 Sorting Integers (SUM of M) |
ユーザー |
![]() |
提出日時 | 2021-07-30 20:52:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 950 bytes |
コンパイル時間 | 3,883 ms |
コンパイル使用メモリ | 229,088 KB |
実行使用メモリ | 9,600 KB |
最終ジャッジ日時 | 2024-09-15 22:42:54 |
合計ジャッジ時間 | 4,901 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<pair<int,int>>>; #define MAX 100000 #define MOD 1000000007 #define INF 1000000000 int main(){ int N; cin>>N; vector<ll> c(9); for(int i=0;i<9;i++){ cin>>c[i]; } vector<ll> res(N,1); for(int i=1;i<N;i++){ res[i]=10*res[i-1]%MOD; } vector<ll> fac(N+1,1); vector<ll> inv(N+1,1); vector<ll> finv(N+1,1); for(int i=2;i<=N;i++){ fac[i]=(ll)i*fac[i-1]%MOD; inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD; finv[i]=finv[i-1]*inv[i]%MOD; } ll ans=0; ll x=fac[N-1]; for(int i=0;i<9;i++){ x*=finv[c[i]]; x%=MOD; } for(int i=0;i<N;i++){ for(int j=0;j<9;j++){ if(c[j]==0){ continue; } ll y=(x*fac[c[j]]%MOD)*finv[c[j]-1]%MOD; y=res[i]*y%MOD; y*=(ll)j+1; y%=MOD; ans+=y; ans%=MOD; } } cout<<ans<<endl; }