結果
| 問題 | No.2310 [Cherry 5th Tune A] Against Regret |
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2023-03-01 00:20:44 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,291 ms / 6,000 ms |
| コード長 | 9,314 bytes |
| 記録 | |
| コンパイル時間 | 3,572 ms |
| コンパイル使用メモリ | 211,540 KB |
| 最終ジャッジ日時 | 2025-02-11 00:24:08 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
// マクロの定義
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define unless(cond) if (!(cond))
// オーバーロードマクロ
#define overload2(_1, _2, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload5(_1, _2, _3, _4, _5, name, ...) name
// 繰り返し系
#define rep1(n) for (ll i=0; i<n; i++)
#define rep2(i,n) for (ll i=0; i<n; i++)
#define rep3(i,a,b) for (ll i=a; i<b; i++)
#define rep4(i,a,b,c) for (ll i=a; i<b; i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define foreach1(x,a) for (auto &&x: a)
#define foreach2(x,y,a) for (auto &&[x,y]: a)
#define foreach3(x,y,z,a) for (auto &&[x,y,z]: a)
#define foreach4(x,y,z,w,a) for (auto &&[x,y,z,w]: a)
#define foreach(...) overload5(__VA_ARGS__,foreach4,foreach3,foreach2,foreach1)(__VA_ARGS__)
// 除算に関する関数
template<typename T, typename U>
T floor(T x, U y){return (x>0 ? x/y: (x-y+1)/y);}
template<typename T, typename U>
T ceil(T x, U y){return (x>0 ? (x+y-1)/y: x/y);}
template<typename T, typename U>
T mod(T x, U y){
T q=floor(x,y);
return x-q*y;
}
template<typename T, typename U>
pair<T,T> divmod(T x, U y){
T q=floor(x,y);
return {q,x-q*y};
}
// 指数に関する関数
ll intpow(ll x, ll y){
ll a=1;
while (y){
if (y&1) a*=x;
x*=x;
y>>=1;
}
return a;
}
ll modpow(ll x, ll y, ll z){
ll a=1;
while (y){
if (y&1) (a*=x)%=z;
(x*=x)%=z;
y>>=1;
}
return a;
}
ll sum(vector<int> &X){
ll y=0;
for (auto &&x: X) y+=x;
return y;
}
template<typename T>
T sum(vector<T> &X){
T y=T(0);
for (auto &&x: X) y+=x;
return y;
}
// max, min
template<typename T, typename U>
inline bool chmax(T &a, const U b){
return (a<b ? a=b, 1: 0);
}
template<typename T, typename U>
inline bool chmin(T &a, const U b){
return (a>b ? a=b, 1: 0);
}
template<class... T>
constexpr auto max(T... a){
return max(initializer_list<common_type_t<T...>>{a...});
}
template<class... T>
constexpr auto min(T... a){
return min(initializer_list<common_type_t<T...>>{a...});
}
template<class T>
T max(vector<T> X){
T alpha=X[0];
for (auto x:X) chmax(alpha, x);
return alpha;
}
template<class T>
T min(vector<T> X){
T alpha=X[0];
for (auto x:X) chmin(alpha, x);
return alpha;
}
//特別な演算
template<class T, class U>
pair<T,U> operator+(const pair<T,U> &lhs, const pair<T,U> &rhs){
return pair<T,U>(lhs.first + rhs.first, lhs.second + rhs.second);
}
template<class T, class U>
pair<T,U> operator-(const pair<T,U> &lhs, const pair<T,U> &rhs){
return pair<T,U>(lhs.first - rhs.first, lhs.second - rhs.second);
}
template<class T, class U>
pair<T,U> operator+=(pair<T,U> &lhs, const pair<T,U> &rhs){return lhs=lhs+rhs;}
template<class T, class U>
pair<T,U> operator-=(pair<T,U> &lhs, const pair<T,U> &rhs){return lhs=lhs-rhs;}
// 入出力
template<class... T>
void input(T&... a){(cin >> ... >> a);}
void print(){cout << "\n";}
template<class T, class... Ts>
void print(const T& a, const Ts&... b){
cout << a;
(cout << ... << (cout << " ", b));
cout << "\n";
}
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>
vector<T> vector_input(int N, int index){
vector<T> X(N+index);
for (int i=index; i<index+N; i++) cin >> X[i];
return X;
}
template<typename T>
istream &operator>>(istream &is, vector<T> &X){
for (auto &x: X) is >> x;
return is;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &X){
int N=(int)len(X);
os << "[";
rep(i,N) os << (i ? ", ": "") << X[i];
return os << "]";
}
template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &S){
os << "{{";
int i=0;
for (T a: S) {os << (i ? ", ": "") << a; i++;}
return os << "}}";
}
template<typename T>
ostream &operator<<(ostream &os, const set<T> &S){
os << "{";
int i=0;
for (T a: S) {os << (i ? ", ": "") << a; i++;}
return os << "}";
}
template<typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &S){
os << "{{";
int i=0;
for (T a: S) {os << (i ? ", ": "") << a; i++;}
return os << "}}";
}
template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &S){
os << "{";
int i=0;
for (T a: S) {os << (i ? ", ": "") << a; i++;}
return os << "}";
}
template<typename A, typename T>
ostream &operator<<(ostream &os, const unordered_map<A,T> &M){
os << "{{";
int i=0;
for (auto p:M) {os << (i ? ", ": "") << p.first << ": " << p.second; i++;}
return os << "}}";
}
template<typename A, typename T>
ostream &operator<<(ostream &os, const map<A,T> &M){
os << "{";
int i=0;
for (auto p:M) {os << (i ? ", ": "") << p.first << ": " << p.second; i++;}
return os << "}";
}
//===============================================
template<const int mod>
struct modint{
int64_t a;
public:
// 初期化
constexpr modint (): a(0){}
constexpr modint (int64_t a): a((a%mod+mod)%mod) {}
// マイナス元
modint operator-() const { return modint(-a);}
// 加法
modint& operator+=(const modint &y){
if ((a+=y.a)>=mod) a-=mod;
return *this;
}
friend modint operator+(const modint &x, const modint &y) {return modint(x)+=y;}
// 減法
modint& operator-=(const modint &y){
if ((a+=mod-y.a)>=mod) a-=mod;
return *this;
}
friend modint operator-(const modint &x, const modint &y) {return modint(x)-=y;}
// 乗法
modint& operator*=(const modint &y){
(a*=y.a)%=mod;
return *this;
}
friend modint operator*(const modint &x, const modint &y) {return modint(x)*=y;}
// 除法
modint& operator/=(const modint &y){
return (*this)*=y.inverse();
}
friend modint operator/(const modint &x, const modint &y) {return modint(x)/=y;}
// モジュラー逆元
bool invertible() const{
int64_t x=a, y=mod;
while (y) swap(x%=y,y);
return x==1;
}
modint inverse() const{
int64_t s=1, t=0;
int64_t x=a, y=mod;
while (y){
auto q=x/y;
swap(x-=q*y,y);
swap(s-=q*t,t);
}
assert(x==1);
return modint(s);
}
// インクリメント
modint& operator++(){
if (++a==mod) a=0;
return *this;
}
modint operator++(int){
modint x(*this);
if (++a==mod) a=0;
return x;
}
// デクリメント
modint& operator--(){
if (a==0) a=mod-1;
else a--;
}
modint operator--(int){
modint x(*this);
if (a==0) a=mod-1;
else a--;
return x;
}
// 比較
friend bool operator==(const modint &x, const modint &y) { return (x.a==y.a);}
friend bool operator!=(const modint &x, const modint &y) { return (x.a!=y.a);}
// 入力
friend istream &operator>>(istream &is, modint &x) {
is >> x.a;
x.a=(x.a%mod+mod)%mod;
return (is);
}
// 出力
friend ostream &operator<<(ostream &os, const modint &x) { return os << x.a;}
};
template<int mod>
modint<mod> pow(modint<mod> x, int64_t n){
if (n<0) return pow(x,-n).inverse();
modint<mod> y(1);
while (n){
if (n&1) y*=x;
x*=x; n>>=1;
}
return y;
}
using modint998244353=modint<998244353>;
using modint1000000007=modint<1000000007>;
//===============================================
int main(){
int N; cin >> N;
vector<vector<modint998244353>> X(N+1, vector<modint998244353>(N+1,0));
for (int u=0; u<=N; u++){
for (int v=0; v<=N; v++){
cin >> X[u][v];
}
}
vector<vector<modint998244353>> S(N+1, vector<modint998244353>(N+1,0));
for (int u=0; u<=N; u++){
S[u][u]=1;
for (int v=u; v<=N; v++){
for (int w=v+1; w<=N; w++){
S[u][w]+=S[u][v]*X[v][w];
}
}
}
int Q=0; cin >> Q;
for (int q=1; q<=Q; q++){
int K; cin >> K;
vector<int> A(K),B(K),C(K);
vector<tuple<int,int,int>> V(0);
for (int k=0; k<K; k++){
cin >> A[k] >> B[k] >> C[k];
V.emplace_back(make_tuple(A[k],1,k));
V.emplace_back(make_tuple(B[k],0,k));
}
sort(all(V));
modint998244353 ans=S[0][N];
vector<modint998244353> DPa(K), DPb(K);
for (int k=0; k<K; k++){DPa[k]=S[0][A[k]];}
int v,t,k;
for (auto tup: V){
tie (v,t,k)=tup;
if (t==1){
DPb[k]+=DPa[k]*C[k];
}else{
ans+=DPb[k]*S[B[k]][N];
for (int l=0; l<K; l++){
DPa[l]+=DPb[k]*S[B[k]][A[l]];
}
}
}
cout << ans << "\n";
}
}