結果
| 問題 | No.2017 Mod7 Parade |
| ユーザー |
 asaringo
|
| 提出日時 | 2023-11-13 00:16:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 990 ms / 2,000 ms |
| コード長 | 12,876 bytes |
| コンパイル時間 | 2,818 ms |
| コンパイル使用メモリ | 226,464 KB |
| 最終ジャッジ日時 | 2025-02-17 21:48:21 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define overload2(a, b, c, ...) c#define overload3(a, b, c, d, ...) d#define overload4(a, b, c, d, e ...) e#define overload5(a, b, c, d, e, f ...) f#define overload6(a, b, c, d, e, f, g ...) g#define fast_io ios::sync_with_stdio(false); cin.tie(nullptr);#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")typedef long long ll;typedef long double ld;#define chmin(a,b) a = min(a,b);#define chmax(a,b) a = max(a,b);#define bit_count(x) __builtin_popcountll(x)#define leading_zero_count(x) __builtin_clz(x)#define trailing_zero_count(x) __builtin_ctz(x)#define gcd(a,b) __gcd(a,b)#define lcm(a,b) a / gcd(a,b) * b#define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__)#define rep1(i,n) for(int i = 0 ; i < n ; i++)#define rrep(i,a,b) for(int i = a ; i < b ; i++)#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)#define pt(a) cout << a << endl;#define print(...) printall(__VA_ARGS__);#define debug(a) cout << #a << " " << a << endl;#define all(a) a.begin(), a.end()#define endl "\n";#define v1(T,n,a) vector<T>(n,a)#define v2(T,n,m,a) vector<vector<T>>(n,v1(T,m,a))#define v3(T,n,m,k,a) vector<vector<vector<T>>>(n,v2(T,m,k,a))#define v4(T,n,m,k,l,a) vector<vector<vector<vector<T>>>>(n,v3(T,m,k,l,a))template<typename T,typename U>istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}template<typename T,typename U>ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}template<typename T>istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}template<typename T>ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}returnos;}template<typename T>istream &operator>>(istream&is,vector<vector<T>>&v){for(T &in:v){is>>in;}return is;}template<typename T>ostream &operator<<(ostream&os,const vector<vector<T>>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;}template<typename T>ostream &operator<<(ostream&os,const set<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}template<typename T>ostream &operator<<(ostream&os,const multiset<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}returnos;}template<class... Args> void printall(Args... args){for(auto i:initializer_list<common_type_t<Args...>>{args...}) cout<<i<<" ";cout<<endl;}const int mod = 1000000007 ;template< int mod >struct ModInt {int x;ModInt() : x(0) {}ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int) (1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }ModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ModInt(u);}ModInt pow(int64_t n) const {ModInt ret(1), mul(x);while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}friend istream &operator>>(istream &is, ModInt &a) {int64_t t;is >> t;a = ModInt< mod >(t);return (is);}static int get_mod() { return mod; }};using modint = ModInt< mod >;const int mod2 = 7 ;template< int mod2 >struct ModInt2 {int x;ModInt2() : x(0) {}ModInt2(int64_t y) : x(y >= 0 ? y % mod2 : (mod2 - (-y) % mod2) % mod2) {}ModInt2 &operator+=(const ModInt2 &p) {if((x += p.x) >= mod2) x -= mod2;return *this;}ModInt2 &operator-=(const ModInt2 &p) {if((x += mod2 - p.x) >= mod2) x -= mod2;return *this;}ModInt2 &operator*=(const ModInt2 &p) {x = (int) (1LL * x * p.x % mod2);return *this;}ModInt2 &operator/=(const ModInt2 &p) {*this *= p.inverse();return *this;}ModInt2 operator-() const { return ModInt2(-x); }ModInt2 operator+(const ModInt2 &p) const { return ModInt2(*this) += p; }ModInt2 operator-(const ModInt2 &p) const { return ModInt2(*this) -= p; }ModInt2 operator*(const ModInt2 &p) const { return ModInt2(*this) *= p; }ModInt2 operator/(const ModInt2 &p) const { return ModInt2(*this) /= p; }bool operator==(const ModInt2 &p) const { return x == p.x; }bool operator!=(const ModInt2 &p) const { return x != p.x; }ModInt2 inverse() const {int a = x, b = mod2, u = 1, v = 0, t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ModInt2(u);}ModInt2 pow(int64_t n) const {ModInt2 ret(1), mul(x);while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const ModInt2 &p) {return os << p.x;}friend istream &operator>>(istream &is, ModInt2 &a) {int64_t t;is >> t;a = ModInt2< mod2 >(t);return (is);}static int get_mod() { return mod2; }};using modint2 = ModInt2< mod2 >;template<typename T> struct Matrix{int row, col;vector<vector<T>> mat ;private:void init_(vector<vector<T>> A){row = A.size();col = A[0].size();mat = A;}void init_(vector<T> A, bool row_matrix = false){if(row_matrix) {col = (int)A.size();row = 1;mat.resize(1);mat[0] = A;}else {col = 1;row = (int)A.size();mat.resize(row,vector<T>(1));rep(i,row) mat[i][0] = A[i];}}Matrix<T> pow_(ll k){assert(row == col);vector<vector<T>> E(row,vector<T>(row,0));rep(i,row) rep(j,row) if(i == j) E[i][j] = 1;Matrix<T> res(E);Matrix<T> X(mat);while(k > 0){if(k & 1) res *= X;X *= X;k >>= 1 ;}return res;}void transpose_() {vector<vector<T>> res(col,vector<T>(row));rep(i,row) rep(j,col) res[j][i] = mat[i][j];mat = res;swap(row,col);}void concat_col_(vector<T> &Y) {Matrix X(Y);concat_col_(X);}void concat_col_(vector<vector<T>> &Y) {Matrix X(Y);concat_col_(X);}void concat_col_(Matrix &Y) {assert((int)Y.row == row);col += Y.col;rep(i,row) {rep(j,Y.col) mat[i].push_back(Y.mat[i][j]);}}void concat_row_(vector<T> &Y) {Matrix X(Y,true);concat_row_(X);}void concat_row_(vector<vector<T>> &Y) {Matrix X(Y);concat_row_(X);}void concat_row_(Matrix &Y) {assert((int)Y.col == col);row += Y.row;rep(i,Y.row) mat.push_back(Y.mat[i]);}void print_() {rep(i,row){rep(j,col) cout << mat[i][j] << " "; cout << endl;}}public:inline Matrix &operator+=(const Matrix Y) {rep(i,row) rep(j,col) mat[i][j] += Y.mat[i][j];return *this ;}inline Matrix &operator-=(const Matrix Y) {rep(i,row) rep(j,col) mat[i][j] -= Y.mat[i][j];return *this ;}inline Matrix &operator*=(const Matrix Y) {int x = row, y = Y.col, n = col;vector<vector<T>> res(x,vector<T>(y));rep(i,x) rep(j,y) rep(k,n) res[i][j] += mat[i][k] * Y.mat[k][j];swap(mat,res);row = x;col = y;return *this ;}inline Matrix operator-() const {rep(i,row) rep(j,col) mat[i][j] *= -1;return *this ;}inline Matrix operator+(const Matrix Y) const { return Matrix(*this) += Y; }inline Matrix operator-(const Matrix Y) const { return Matrix(*this) -= Y; }inline Matrix operator*(const Matrix Y) const { return Matrix(*this) *= Y; }inline bool operator==(const Matrix Y) const { return mat == Y.mat; }inline bool operator!=(const Matrix Y) const { return mat != Y.mat; }inline vector<T>&operator[](int i) { return mat[i] ; }Matrix(int n): row(n), col(0) { mat.resize(row); }Matrix(vector<T> A, bool row_matrix = false) { init_(A, row_matrix); }Matrix(vector<vector<T>> A){ init_(A); }void init(vector<T> A, bool row_matrix = false) { init_(A, row_matrix); }void init(vector<vector<T>> A) { init_(A); }size_t row_size() { return row; }size_t col_size() { return col; }Matrix pow(ll k){ return pow_(k); }void transpose() { transpose_(); }void concat_col(vector<vector<T>> &Y) { concat_col_(Y); }void concat_col(vector<T> &Y) { concat_col_(Y); }void concat_col(Matrix &Y) { concat_col_(Y); }void concat_row(vector<vector<T>> &Y) { concat_row_(Y); }void concat_row(vector<T> &Y) { concat_row_(Y); }void concat_row(Matrix &Y) { concat_row_(Y); }// void print() { print_(); }};// function : return : description// -----------------------------------------------------// init(vector<T>, row_matrix) : void : 1次元ベクトルに対して行列化する, 列行列か行行列を選択できる// init(vector<vector<T>>) : void : 2次元ベクトルに対して行列化する// row_size() : int : 行の大きさ// col_size() : int : 列の大きさ// pow(k) : Matrix : 行列をk乗する(n * n 行列であること)// transpose() : void : 転置する// concat_col(vector<vector<T>>) : void : 列に関して結合する// concat_col(vector<T>) : void : 列に関して結合する// concat_col(Matrix) : void : 列に関して結合する// concat_row(vector<vector<T>>) : void : 列に関して結合する// concat_row(vector<T>) : void : 列に関して結合する// concat_row(Matrix) : void : 列に関して結合する// print() : void : 行列を出力する// *注意* 取り敢えず全てをコピペすることを奨励// verify// https://atcoder.jp/contests/dp/tasks/dp_rint n;void solve(){cin >> n;vector<ll> D(n), L(n);rep(i,n) cin >> D[i] >> L[i];vector<vector<modint>> dp(n+1,vector<modint>(7,0));dp[0][0] = 1;rep(i,n){ll d = D[i];ll l = L[i];modint2 ten = 10;modint2 vt = ten.pow(l);vector<vector<modint2>> A = {{10, 1},{0, 1},};vector<modint2> b = {0, d};Matrix<modint2> mat(A), B(b);auto M = mat.pow(l) * B;auto val = M[0][0].x;auto vtn = vt.x;rep(j,7){dp[i+1][j] += dp[i][j];dp[i+1][(j * vtn + val)%7] += dp[i][j];}}modint res = 0;rep(i,7) {res += dp[n][i] * i;}pt(res)}int main(){fast_ioint t = 1;// cin >> t;rep(i,t) solve();}