結果
| 問題 | No.1239 Multiplication -2 |
| ユーザー |
 PCTprobability
|
| 提出日時 | 2020-09-25 22:34:20 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 18,554 bytes |
| コンパイル時間 | 6,378 ms |
| コンパイル使用メモリ | 372,976 KB |
| 実行使用メモリ | 8,068 KB |
| 最終ジャッジ日時 | 2024-06-28 07:00:32 |
| 合計ジャッジ時間 | 8,267 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | AC | 2 ms
5,376 KB |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 2 ms
5,376 KB |
| testcase_14 | AC | 2 ms
5,376 KB |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | AC | 116 ms
8,064 KB |
| testcase_18 | AC | 165 ms
8,068 KB |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | AC | 216 ms
7,772 KB |
| testcase_22 | AC | 45 ms
5,376 KB |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | AC | 59 ms
5,376 KB |
| testcase_26 | AC | 134 ms
6,312 KB |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
ソースコード
////////////////////////////////////////////////////////////////////////////////
// Give me AC!!! //
////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <random>
#include <cmath>
#include <limits>
#include <iostream>
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
namespace mp = boost::multiprecision;
using namespace mp;
using ull = __int128;
using ll = long long;
using cll = cpp_int;
using ld = long double;
using Graph = vector<vector<int>>;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
#define PQ priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>>
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define coutY cout<<"YES"<<endl
#define couty cout<<"Yes"<<endl
#define coutN cout<<"NO"<<endl
#define coutn cout<<"No"<<endl
#define coutdouble(a,b) cout << fixed << setprecision(a) << double(b) ;
#define vi(a,b) vector<int> a(b)
#define vl(a,b) vector<ll> a(b)
#define vs(a,b) vector<string> a(b)
#define vll(a,b,c) vector<vector<ll>> a(b, vector<ll>(c));
#define intque(a) queue<int> a;
#define llque(a) queue<ll> a;
#define intque2(a) priority_queue<int, vector<int>, greater<int>> a;
#define llque2(a) priority_queue<ll, vector<ll>, greater<ll>> a;
#define pushback(a,b) a.push_back(b)
#define mapii(M1) map<int, int> M1;
#define cou(v,x) count(v.begin(), v.end(), x)
#define mapll(M1) map<ll,ll> M1;
#define mapls(M1) map<ll, string> M1;
#define mapsl(M1) map<string, ll> M1;
#define twolook(a,l,r,x) lower_bound(a+l, a+r, x) - a
#define sor(a) sort(a.begin(), a.end())
#define rever(a) reverse(a.begin(),a.end())
#define rep(i,a) for(ll i=0;i<a;i++)
#define vcin(n) for(ll i=0;i<ll(n.size());i++) cin>>n[i]
#define vcout(n) for(ll i=0;i<ll(n.size());i++) cout<<n[i]
#define vcin2(n) rep(i,ll(n.size())) rep(j,ll(n.at(0).size())) cin>>n[i][j]
const ll mod = 998244353;
const ll MOD = 998244353;
//const ll MOD = 1000000007;
//const ll mod = 1000000007;
constexpr ll MAX = 5000000;
//const ll _max = 9223372036854775807;
const ll _max = 1223372036854775807;
const ll INF = 2000000000000000000;
ll fac[MAX],finv[MAX],inv[MAX];
// テーブルを作る前処理
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
// 二項係数計算
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int modPow(long long a, long long n, long long p) {
if (n == 0) return 1; // 0乗にも対応する場合
if (n == 1) return a % p;
if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
long long t = modPow(a, n / 2, p);
return (t * t) % p;
}
ll clocks(ll a,ll b,ll c){
return a*3600+b*60+c;
}
ll divup(ll b,ll d){
if(b%d==0){
return b/d;
}
else{
return b/d+1;
}
}
struct Edge {
int to; // 辺の行き先
int weight; // 辺の重み
Edge(int t, int w) : to(t), weight(w) { }
};
using Graphw = vector<vector<Edge>>;
ll zero(ll a){
return max(ll(0),a);
}
template< typename T >
struct FormalPowerSeries : vector< T > {
using vector< T >::vector;
using P = FormalPowerSeries;
using MULT = function< P(P, P) >;
static MULT &get_mult() {
static MULT mult = nullptr;
return mult;
}
static void set_fft(MULT f) {
get_mult() = f;
}
void shrink() {
while(this->size() && this->back() == T(0)) this->pop_back();
}
P operator+(const P &r) const { return P(*this) += r; }
P operator+(const T &v) const { return P(*this) += v; }
P operator-(const P &r) const { return P(*this) -= r; }
P operator-(const T &v) const { return P(*this) -= v; }
P operator*(const P &r) const { return P(*this) *= r; }
P operator*(const T &v) const { return P(*this) *= v; }
P operator/(const P &r) const { return P(*this) /= r; }
P operator%(const P &r) const { return P(*this) %= r; }
P &operator+=(const P &r) {
if(r.size() > this->size()) this->resize(r.size());
for(int i = 0; i < r.size(); i++) (*this)[i] += r[i];
return *this;
}
P &operator+=(const T &r) {
if(this->empty()) this->resize(1);
(*this)[0] += r;
return *this;
}
P &operator-=(const P &r) {
if(r.size() > this->size()) this->resize(r.size());
for(int i = 0; i < r.size(); i++) (*this)[i] -= r[i];
shrink();
return *this;
}
P &operator-=(const T &r) {
if(this->empty()) this->resize(1);
(*this)[0] -= r;
shrink();
return *this;
}
P &operator*=(const T &v) {
const int n = (int) this->size();
for(int k = 0; k < n; k++) (*this)[k] *= v;
return *this;
}
P &operator*=(const P &r) {
if(this->empty() || r.empty()) {
this->clear();
return *this;
}
assert(get_mult() != nullptr);
return *this = get_mult()(*this, r);
}
P &operator%=(const P &r) {
return *this -= *this / r * r;
}
P operator-() const {
P ret(this->size());
for(int i = 0; i < this->size(); i++) ret[i] = -(*this)[i];
return ret;
}
P &operator/=(const P &r) {
if(this->size() < r.size()) {
this->clear();
return *this;
}
int n = this->size() - r.size() + 1;
return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev(n);
}
P pre(int sz) const {
return P(begin(*this), begin(*this) + min((int) this->size(), sz));
}
P operator>>(int sz) const {
if(this->size() <= sz) return {};
P ret(*this);
ret.erase(ret.begin(), ret.begin() + sz);
return ret;
}
P operator<<(int sz) const {
P ret(*this);
ret.insert(ret.begin(), sz, T(0));
return ret;
}
P rev(int deg = -1) const {
P ret(*this);
if(deg != -1) ret.resize(deg, T(0));
reverse(begin(ret), end(ret));
return ret;
}
P diff() const {
const int n = (int) this->size();
P ret(max(0, n - 1));
for(int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i);
return ret;
}
P integral() const {
const int n = (int) this->size();
P ret(n + 1);
ret[0] = T(0);
for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1);
return ret;
}
// F(0) must not be 0
P inv(int deg = -1) const {
assert(((*this)[0]) != T(0));
const int n = (int) this->size();
if(deg == -1) deg = n;
P ret({T(1) / (*this)[0]});
for(int i = 1; i < deg; i <<= 1) {
ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);
}
return ret.pre(deg);
}
// F(0) must be 1
P log(int deg = -1) const {
assert((*this)[0] == 1);
const int n = (int) this->size();
if(deg == -1) deg = n;
return (this->diff() * this->inv(deg)).pre(deg - 1).integral();
}
P sqrt(int deg = -1) const {
const int n = (int) this->size();
if(deg == -1) deg = n;
if((*this)[0] == T(0)) {
for(int i = 1; i < n; i++) {
if((*this)[i] != T(0)) {
if(i & 1) return {};
if(deg - i / 2 <= 0) break;
auto ret = (*this >> i).sqrt(deg - i / 2) << (i / 2);
if(ret.size() < deg) ret.resize(deg, T(0));
return ret;
}
}
return P(deg, 0);
}
P ret({T(1)});
T inv2 = T(1) / T(2);
for(int i = 1; i < deg; i <<= 1) {
ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2;
}
return ret.pre(deg);
}
// F(0) must be 0
P exp(int deg = -1) const {
assert((*this)[0] == T(0));
const int n = (int) this->size();
if(deg == -1) deg = n;
P ret({T(1)});
for(int i = 1; i < deg; i <<= 1) {
ret = (ret * (pre(i << 1) + T(1) - ret.log(i << 1))).pre(i << 1);
}
return ret.pre(deg);
}
P pow(int64_t k, int deg = -1) const {
const int n = (int) this->size();
if(deg == -1) deg = n;
for(int i = 0; i < n; i++) {
if((*this)[i] != T(0)) {
T rev = T(1) / (*this)[i];
P C(*this * rev);
P D(n - i);
for(int j = i; j < n; j++) D[j - i] = C[j];
D = (D.log() * k).exp() * (*this)[i].pow(k);
P E(deg);
if(i * k > deg) return E;
auto S = i * k;
for(int j = 0; j + S < deg && j < D.size(); j++) E[j + S] = D[j];
return E;
}
}
return *this;
}
T eval(T x) const {
T r = 0, w = 1;
for(auto &v : *this) {
r += w * v;
w *= x;
}
return r;
}
};
//aはbの何乗以下かを満たす数の内最大の物,(a,10)はaの桁数
ll expless(ll a,ll b){
ll k=0;
ll o=1;
while(a>=o){
k++;
o=o*b;
}
return k;
}
//aをb進法で表す
//b進法のaを10進法に直す
ll tenbase(ll a,ll b){
ll c=expless(a,10);
ll ans=0;
ll k=1;
for(int i=0;i<c;i++){
ans+=(a%10)*k;
k=k*b;
a=a/10;
}
return ans;
}
vector<pair<long long, long long> > prime_factorize(long long N) {
vector<pair<long long, long long> > res;
for (long long a = 2; a * a <= N; ++a) {
if (N % a != 0) continue;
long long ex = 0; // 指数
// 割れる限り割り続ける
while (N % a == 0) {
++ex;
N /= a;
}
// その結果を push
res.push_back({a, ex});
}
// 最後に残った数について
if (N != 1) res.push_back({N, 1});
return res;
}
ll atll(ll a,ll b){
b++;
ll c=expless(a,10);
ll d=c-b;
ll f=1;
for(int i=0;i<d;i++){
f=f*10;
}
a=(a/f);
return a%10;
}
//aがbで何回割り切るか
ll exp(ll a,ll b){
ll ans=0;
while(a%b==0){
a=a/b;
ans++;
}
return ans;
}
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int X[6]={1,1,0,-1,-1,0};
const int Y[6]={0,1,1,0,-1,-1};
template<typename T>
vector<T> smallest_prime_factors(T n) {
vector<T> spf(n + 1);
for (int i = 0; i <= n; i++) spf[i] = i;
for (T i = 2; i * i <= n; i++) {
// 素数だったら
if (spf[i] == i) {
for (T j = i * i; j <= n; j += i) {
// iを持つ整数かつまだ素数が決まっていないなら
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
return spf;
}
vector<pair<ll,ll>> factolization(ll x, vector<ll> &spf) {
vector<pair<ll,ll>> ret;
ll p;
ll z;
while (x != 1) {
p=(spf[x]);
z=0;
while(x%p==0){
z++;
x /= p;
}
ret.push_back({p, z});
}
return ret;
}
vector<bool> is;
vector<long long int> prime_(ll n){
is.resize(n+1, true);
is[0] = false;
is[1] = false;
vector<long long int> primes;
for (int i=2; i<=n; i++) {
if (is[i] == true){
primes.push_back(i);
for (int j=i*2; j<=n; j+=i){
is[j] = false;
}
}
}
return primes;
}
vector<ll> dijkstra(ll f,ll n,vector<vector<vector<ll>>>& edge){
//最短経路としてどの頂点が確定済みかをチェックする配列
vector<ll> confirm(n,false);
//それぞれの頂点への最短距離を保存する配列
//始点は0,始点以外はINFで最短距離を初期化する
vector<ll> mincost(n,INF);mincost[f]=0;
//確定済みの頂点の集合から伸びる辺を伝ってたどり着く頂点の始点からの距離を短い順に保存するPriority queue
PQ mincand;mincand.push({mincost[f],f});
//mincandの要素がゼロの時、最短距離を更新できる頂点がないことを示す
while(!mincand.empty()){
//最短距離でたどり着くと思われる頂点を取り出す
vector<ll> next=mincand.top();mincand.pop();
//すでにその頂点への最短距離が確定済みの場合は飛ばす
if(confirm[next[1]]) continue;
//確定済みではない場合は確定済みにする
confirm[next[1]]=true;
//その確定済みの頂点から伸びる辺の情報をとってくる(参照の方が速い)、lは辺の本数
vector<vector<ll>>& v=edge[next[1]];ll l=SIZE(v);
REP(i,l){
//辺の先が確定済みなら更新する必要がない((✳︎2)があれば十分なので(✳︎1)は実はいらない)
if(confirm[v[i][0]]) continue; //(✳︎1)
//辺の先のmincost以上の場合は更新する必要がない(辺の先が確定済みの時は満たす)
if(mincost[v[i][0]]<=next[0]+v[i][1]) continue; //(✳︎2)
//更新
mincost[v[i][0]]=next[0]+v[i][1];
//更新した場合はその頂点が(確定済みでない頂点の中で)最短距離になる可能性があるのでmincandに挿入
mincand.push({mincost[v[i][0]],v[i][0]});
}
}
return mincost;
}
ll so(ll a){
ll ans=0;
if(a==0){
return 0;
}
while(a%2==0){
a/=2;
ans++;
}
return ans;
}
ll HOM(ll n,ll r){
return COM(n+r-1,r);
}
ll binary(ll bina){
ll ans = 0;
for (ll i = 0; bina>0 ; i++)
{
ans = ans+(bina%2)*pow(10,i);
bina = bina/2;
}
return ans;
}
class UnionFind {
public:
vector<ll> parent; //parent[i]はiの親
vector<ll> siz; //素集合のサイズを表す配列(1で初期化)
map<ll,vector<ll>> group;//素集合ごとに管理する連想配列(keyはそれぞれの素集合の親、valueはその素集合の要素の配列)
//コンストラクタ
UnionFind(ll n):parent(n),siz(n,1){
//全ての要素の根が自身であるとして初期化
for(ll i=0;i<n;i++){parent[i]=i;}
}
//データxの属する木の根を取得(経路圧縮も行う)
ll root(ll x){
if(parent[x]==x) return x;
return parent[x]=root(parent[x]);//代入式の値は代入した変数の値なので、経路圧縮できる
}
//xとyの木を併合
void unite(ll x,ll y){
ll rx=root(x);//xの根
ll ry=root(y);//yの根
if(rx==ry) return;//同じ木にある時
//小さい集合を大きい集合へと併合(ry→rxへ併合)
if(siz[rx]<siz[ry]) swap(rx,ry);
siz[rx]+=siz[ry];
parent[ry]=rx;//xとyが同じ木にない時はyの根ryをxの根rxにつける
}
//xとyが属する木が同じかを判定
bool same(ll x,ll y){
ll rx=root(x);
ll ry=root(y);
return rx==ry;
}
//xの素集合のサイズを取得
ll size(ll x){
return siz[root(x)];
}
//素集合をそれぞれグループ化
void grouping(ll n){
//経路圧縮を先に行う
REP(i,n)root(i);
//mapで管理する(デフォルト構築を利用)
REP(i,n)group[parent[i]].PB(i);
}
};
vector<long long> enum_divisors(long long N) {
vector<long long> res;
for (long long i = 1; i * i <= N; ++i) {
if (N % i == 0) {
res.push_back(i);
// 重複しないならば i の相方である N/i も push
if (N/i != i) res.push_back(N/i);
}
}
// 小さい順に並び替える
sort(res.begin(), res.end());
return res;
}
vector<ll> zaatu(vector<ll> a,ll n){
map<ll,ll> mp;
for (int i = 0; i < n; i++) {
cin >> a[i];
mp[a[i]] = 0;
}
// 小さい値から順に番号を付けていく
ll num = 0;
for (auto x : mp) {
mp[x.first] = num;
num++;
}
vector<ll> ans;
for(int i=0;i<n;i++){
ans.push_back(mp[a[i]]);
}
return ans;
}
ll vectorcheck(vector<ll> t,ll key){
auto iter = lower_bound(ALL(t), key);
auto iter2 = upper_bound(ALL(t), key);
if((iter-t.begin())!=(iter2-t.begin())){
return 1;
}
else{
return 0;
}
}
ll mygcd(ll x, ll y) {
if(x<y){
swap(x,y);
}
if(y==0){
return x;
}
if(x % y == 0) {
return y;
} else {
return mygcd(y, x % y);
//x%y==0でないときはユーグリットの互除法を使って再帰的に関数を呼び出す。
}
}
ll answer(vector<ll> n){
if(int(n.size())==0){
return 0;
}
ll ans=0;
ll tmp=0;
ll tmp2=0;
ll tmp3=0;
ll tmp4=0;
ll t=1;
for(int i=0;i<int(n.size());i++){
t=1;
tmp=0;
tmp2=0;
tmp3=0;
tmp4=0;
if(n.at(i)==-2||n.at(i)==2){
tmp=modPow(2,i-1,mod);
tmp3=modPow(2,int(n.size())-1-i-1,mod);
for(int j=i-1;j>=0;j--){
if(n.at(j)==2||n.at(j)==-2){
break;
}
if(t*n.at(j)==1){
tmp+=modPow(2,j-1,mod);
tmp%=mod;
}
else{
tmp2+=modPow(2,j-1,mod);
tmp2%=mod;
}
t=t*n.at(j);
}
for(int j=i+1;j<int(n.size());j++){
if(n.at(j)==2||n.at(j)==-2){
break;
}
if(t*n.at(j)==1){
tmp3+=modPow(2,int(n.size())-1-j-1,mod);
tmp3%=mod;
}
else{
tmp4+=modPow(2,int(n.size())-1-j-1,mod);
tmp4%=mod;
}
t=t*n.at(j);
}
if(n.at(i)==2){
ans+=tmp4*tmp+tmp3*tmp2;
}
else{
ans+=tmp4*tmp2+tmp*tmp3;
}
ans%=mod;
}
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << fixed << setprecision(30);
ll ans=0;
ll n;
cin>>n;
vector<ll> a(n);
vcin(a);
vector<ll> tmp;
vector<ll> q;
ll o=0;
ll s=0;
ll l=0;
for(int i=0;i<n;i++){
if(i==n-1){
l=1;
}
if(a.at(i)==0){
// cout<<ans<<" ";
ans+=answer(tmp)*modPow(2,n-1-o-s-l,mod);
tmp=q;
ans%=mod;
o=0;
s=1;
// cout<<ans<<endl;
}
else{
o++;
tmp.push_back(a.at(i));
}
}
ans+=answer(tmp)*modPow(2,n-1-o-s+l,mod);
ans%=mod;
// cout<<ans<<endl;
ll k=modPow(2,n-1,mod);
ans*=modPow(k,mod-2,mod);
ans%=mod;
cout<<ans<<endl;
vector<ll> c={-2,1};
// cout<<answer(c)<<endl;
}