結果
| 問題 | No.1629 Sorting Integers (SUM of M) |
| ユーザー |
 wunderkammer2
|
| 提出日時 | 2021-07-30 21:29:27 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 48 ms / 2,000 ms |
| コード長 | 6,344 bytes |
| コンパイル時間 | 1,229 ms |
| コンパイル使用メモリ | 122,416 KB |
| 最終ジャッジ日時 | 2025-01-23 11:14:24 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 14 |
ソースコード
#include<algorithm> //sort,二分探索,など#include<bit> //popcount#include<bitset> //固定長bit集合#include<cmath> //pow,logなど#include<complex> //複素数#include<deque> //両端アクセスのキュー#include<fstream> //ファイルストリーム（標準入力変更用）#include<functional> //sortのgreater#include<iomanip> //setprecision(浮動小数点の出力の誤差)#include<iostream> //入出力#include<iterator> //集合演算(積集合,和集合,差集合など)#include<map> //map(辞書)#include<numeric> //iota(整数列の生成),gcdとlcm(c++17)#include<queue> //キュー#include<set> //集合#include<stack> //スタック#include<string> //文字列#include<unordered_map> //イテレータあるけど順序保持しないmap#include<unordered_set> //イテレータあるけど順序保持しないset#include<utility> //pair#include<vector> //可変長配列//#include<atcoder/all>//using namespace atcoder;//名前using namespace std;typedef long long ll;typedef unsigned long long ull;typedef long double ld;typedef map<string, int> msi;typedef map<string, ll> msll;typedef pair<int, int> pii;typedef pair<ll, ll> pllll;typedef vector<int> vi;typedef vector<ll> vll;typedef vector<string> vs;typedef vector<bool> vb;typedef vector<vector<int>> vvi;typedef vector<vector<ll>> vvll;typedef vector<vector<string>> vvs;typedef vector<vector<bool>> vvb;//定数const ll MOD = 1000000007;const ll INF = 1000000000000000000;const double EPS = 1e-10;const int MAXR = 2 * 100000; //10^5:配列の最大のrange//マクロ#define rep(i,n) for(int i=0;i<n;i++)#define reps(i,s,e) for(int i=s;i<e;i++)#define repse(i,s,e) for(int i=s;i<=e;i++)#define rrep(i,n) for(int i=n-1;i>=0;i--)#define all(x) (x).begin(),(x).end()#define rall(x) (x).rbegin(),(x).rend()#define in1(x1) cin >> x1#define in2(x1, x2) cin >> x1 >> x2#define in3(x1, x2, x3) cin >> x1 >> x2 >> x3#define in4(x1, x2, x3, x4) cin >> x1 >> x2 >> x3 >> x4#define in5(x1, x2, x3, x4, x5) cin >> x1 >> x2 >> x3 >> x4 >> x5#define in6(x1, x2, x3, x4, x5, x6) cin >> x1 >> x2 >> x3 >> x4 >> x5 >> x6#define inN(x, N) rep(i, N) in1(x[i])#define outl(x) cout << x << endl#define out2l(x, y) cout << x << " " << y << endl#define out3l(x1, x2, x3) cout << x1 << " " << x2 << " " << x3 << endl#define out4l(x1, x2, x3, x4) cout << x1 << " " << x2 << " " << x3 << " " << x4 << endl#define outList(x) for(auto y : x) cout << y << " ";cout << endl//よく使う関数template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }inline ll div_ceil(ll a, ll b) { return (a + (b - 1)) / b; }inline string zeropad(int n, int m) { ostringstream sout; sout << setfill('0') << setw(m) << n; return sout.str(); }inline int sgn(const double a) { return (a < -EPS ? -1 : (a > EPS ? +1 : 0)); } //a > 0ならば+1, a == 0ならば0, a < 0ならば-1 を返す。 基本的にEPS込みの評価はこれで行う。template<class T> inline void unique(vector<T>& v) { sort(all(v)); v.erase(unique(all(v)), v.end()); }template<ll mod> class modint {public:ll val = 0;//コンストラクタmodint(ll x = 0) { while (x < 0)x += mod; val = x % mod; }//コピーコンストラクタmodint(const modint& r) { val = r.val; }//算術演算子modint operator -() { return modint(-val); } //単項modint operator +(const modint& r) { return modint(*this) += r; }modint operator -(const modint& r) { return modint(*this) -= r; }modint operator *(const modint& r) { return modint(*this) *= r; }modint operator /(const modint& r) { return modint(*this) /= r; }//代入演算子modint& operator +=(const modint& r) {val += r.val;if (val >= mod)val -= mod;return *this;}modint& operator -=(const modint& r) {if (val < r.val)val += mod;val -= r.val;return *this;}modint& operator *=(const modint& r) {val = val * r.val % mod;return *this;}modint& operator /=(const modint& r) {ll a = r.val, b = mod, u = 1, v = 0;while (b) {ll t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}val = val * u % mod;if (val < 0)val += mod;return *this;}//等価比較演算子bool operator ==(const modint& r) { return this->val == r.val; }bool operator <(const modint& r) { return this->val < r.val; }bool operator !=(const modint& r) { return this->val != r.val; }};using mint = modint<MOD>;//入出力ストリームistream& operator >>(istream& is, mint& x){//xにconst付けないll t; is >> t;x = t;return (is);}ostream& operator <<(ostream& os, const mint& x){return os << x.val;}//累乗mint modpow(const mint& a, ll n){if (n == 0)return 1;mint t = modpow(a, n / 2);t = t * t;if (n & 1)t = t * a;return t;}//二項係数の計算mint fac[MAXR + 1], finv[MAXR + 1], inv[MAXR + 1];//テーブルの作成void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;repse(i, 2, MAXR){fac[i] = fac[i - 1] * mint(i);inv[i] = -inv[MOD % i] * mint(MOD / i);finv[i] = finv[i - 1] * inv[i];}}//演算部分mint COM(ll n, ll k) {if (n < k)return 0;if (n < 0 || k < 0)return 0;return fac[n] * finv[k] * finv[n - k];}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);//標準入力をファイルに変更//std::ifstream in("input.txt");//std::cin.rdbuf(in.rdbuf());int N;in1(N);int M = 9;vi c(M);inN(c, M);COMinit();mint P = 0;rep(i, N) P += modpow(10, i);mint T = 1;ll tmp = N;rep(i, M){T *= COM(tmp, c[i]);tmp -= c[i];}mint ans = 0;rrep(i, M){mint N2 = N;ans += ((T * c[i]) / mint(N)) * P * (i + 1);}outl(ans);return 0;}