結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー Carpenters-Cat
提出日時 2025-10-31 21:44:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,589 bytes
コンパイル時間 1,242 ms
コンパイル使用メモリ 119,460 KB
実行使用メモリ 10,920 KB
最終ジャッジ日時 2025-10-31 21:44:55
合計ジャッジ時間 9,542 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:160:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  160 |         scanf(" %d %d", &N, &K);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <numeric>
#include <vector>
#include <utility>
#include <set>
#include <list>
#include <stack>
#include <cmath>
#include <cassert>
#include <map>
using namespace std;
using ll = long long;
using Vi = vector<int>;
using VVi = vector<Vi>;
using Vl = vector<ll>;
using VVl = vector<Vl>;
using Pii = pair<int, int>;
using Pli = pair<ll, int>;
using Vii = vector<Pii>;
using VVii = vector<Vii>;
using Tiii = tuple<int, int, int>;
class unionfind {
    int N;
    Vi par;
    Vi siz;
    Vi val;
    public :
    unionfind(Vi A) {
	N = A.size();
	par.resize(N);
	iota(par.begin(), par.end(), 0);
	siz.assign(N, 1);
	val = A;
    }
    int root(int v) {
	return (par[v] == v ? v : this->root(par[v]));
    }
    int rVal(int v) {
	return val[root(v)];
    }
    int gVal(int v) {
	return val[v];
    }
    int merge(int a, int b) {
	a = root(a); b = root(b);
	if (siz[a] < siz[b]) swap(a, b);
	if (a == b) return 0;
	par[b] = a;
	siz[a] += b;
	return 1;
    }
};
int dfs(const VVi& gr, const Vi& D, vector<pair<int, int>>& E, int s, int p = -1) {
    int n = D[s] & 1;
    for (auto v : gr[s]) {
	if (v == p) continue;
	int d = dfs(gr, D, E, v, s);
	if (d) {
	    E.emplace_back(v, s);
	}
	n ^= d;
    }
    return n;
}
void createEuler(vector<list<Pii>>& gr, Vi& did, Vi& ans, int s) {
    // cout << s << endl;
    auto& V = gr[s];
    if (V.empty()) {
	ans.push_back(s);
	return;
    }
    // cout << "GO" << endl;
    auto pt = V.begin();
    while (pt != V.end()) {
	if (did[pt->second] == 1) {
	    auto nx = next(pt);
	    V.erase(pt);
	    pt = nx;
	} else if (!did[pt->second]) {
	    auto [f, s] = *pt;
	    did[s] = -1;
	    did[(s < did.size() / 2 ? s + did.size() / 2 : s - did.size() / 2)] = 1;
	    // cout << "to : " << f << endl;
	    createEuler(gr, did, ans, f);
	    auto nx = next(pt);
	    V.erase(pt);
	    pt = nx;
	    did[s] = 1;
	} else {
	    pt = next(pt);
	}
    }
    // cout << "END : " << s << endl;
    ans.push_back(s);
}
ll mpow(ll a, ll n, ll m) {
    return (n ? (mpow((a * a) % m, n >> 1, m) * (n & 1 ? a : 1ll)) % m : 1ll);
}
void ddfs(const VVi& tr, Vi& siz, Vi& par, int s = 0) {
    siz[s] = 1;
    for (auto v : tr[s]) {
	if (par[s] == v) continue;
	par[v] = s;
	ddfs(tr, siz, par, v);
	siz[s] += siz[v];
    }
}

void calc(const VVi& tr, Vi& ID1, Vi& ID2, int& lst, int s = 0) {
    for (auto& v : tr[s]) {
	ID1[v] = lst;
	if (v == lst + 1) {
	    lst++;
	}
	calc(tr, ID1, ID2, lst, v);
	ID2[v] = lst;
    }
}
const ll m = 998244353;
class segTree {
	public :
	int siz;
	Vl bitt;
	segTree(const Vl& A) {
		siz = 1;
		while (siz < A.size()) siz <<= 1;
		bitt.assign((siz << 1), 0);
		for (int i = 0; i < A.size(); i ++) {
			bitt[i + siz] = A[i];
		}
		for (int i = siz-1; i > 0; i --) {
			bitt[i] = bitt[i*2] | bitt[i*2+1];
		}
	}
	void set(int id, ll x) {
		id += siz;
		bitt[id] = x;
		id >>= 1;
		while (id) {
			bitt[id] = bitt[id * 2] | bitt[id * 2 + 1];
			id >>= 1;
		}
	}
	ll sumSub(int l, int r, int id, int a, int b) {
		if (r <= a || b <= l) return 0;
		if (l <= a && b <= r) return bitt[id];
		int md = (a + b) / 2;
		return sumSub(l, r, id*2, a, md) | sumSub(l, r, id*2+1, md, b);
	}
	ll sum(int l, int r) {
		if (l >= r) return 0;
		return sumSub(l, r, 1, 0, siz);
	}
};
void solve() {
	int N, K;
	scanf(" %d %d", &N, &K);
	string s;
	cin >> s;
	int cnt[] = {0, 0, 0};
	for (auto& c : s) {
		cnt[(c == '?' ? 2 : (c - '0'))] ++;
	}
	string t(K-1, '?');
	// cout << t << endl;
	// return;
	int cH = K-1, cZ = 0;
	int cA = 0;
	ll ans = 0;
	Vl pww(K, 1);
	for (int i = 1; i < K; i ++) {
		pww[i] = (pww[i-1] * 2) % m;
	}
	Vl kai(K, 1), fkai(K);
	for(int i = 1; i < K; i ++) kai[i] = (kai[i-1] * i) % m;
	fkai.back() = mpow(kai.back(), m-2, m);
	for (int i = K-1; i; i --) fkai[i-1] = (fkai[i] * i) % m;
	auto comb = [&](int n, int r) -> ll {
		if (r < 0 || n < r) return 0ll;
		return (((kai[n] * fkai[r]) % m) * fkai[n-r]) % m;
	};
	ll X0 = 1, X1 = 1;
	ll r0 = (K-1) / 2, r1 = (K-1) / 2;
	for (int i = N-1; i >= 0; i --) {
		// printf("%d\n", i);
		char nxx = t[(i+1)%(K-1)];
		if (cnt[0] == 0) {
			if (N - i - 1 <= K - 1) {
				if (N - i - 1 == K - 1) {
					// printf("(cA, r0) = (%d, %d)\n", cA, r0);
					for (int k = 0; k <= r0; k ++) {
						ans += comb(cA, k);
						ans %= m;
					}
				}
			} else if (nxx != '1') {
				int cH2 = cH, cZ2 = cZ;
				if (nxx == '?') {
					cH2 --;
					cZ2 ++;
				}
				ans += comb(cH2, (K - 1) / 2 - cZ2);
			}
		}
		if (cnt[1] == 0) {
			if (N - i - 1 <= K - 1) {
			if (N - i - 1 == K - 1) {
				// printf("(cA, r1) = (%d, %d)\n", cA, r1);
				for (int k = 0; k <= r1; k ++) {
					ans += comb(cA, k);
					ans %= m;
				}
			}
			} else if (nxx != '0') {
				int cH2 = cH, cZ2 = cZ;
				if (nxx == '?') {
					cH2 --;
				}
				// printf("%d %d\n", cH2, (K - 1) / 2 - cZ2);
				ans += comb(cH2, (K - 1) / 2 - cZ2);
			}
		}
		// printf("%d\n", i);
		if (s[i] == '?') {
			cA ++;
		} else {
			if (s[i] == '0') {
				r0 --;
			} else {
				r1 --;
			}
			if ((int)s[i] + t[i%(K-1)] == (int)'0' + '1') {
				// puts("B");
				break;
			}
			if (t[i%(K-1)] == '?') {
				cH --;
				t[i%(K-1)] = s[i];
				cZ += (s[i] == '0');
			}
		}
		// printf("%d\n", i);
		cnt[(s[i] == '?' ? 2 : (s[i] - '0'))] --;
		ans %= m;
		// printf("%d : %lld\n", i, ans);
		// cout << t << endl;
	}
	printf("%lld\n", ans);
	// puts("");
}
const int N = 81181819;
vector<int> ans = {};
std::vector<int> Bs;
bool isS(int a, int b) {
	while (b) {
		if (b % 10 < a % 10) return false;
		b /= 10;
		a /= 10;
	}
	return a == 0;
}
vector<int> calc(int X, int mx, int mlen = 7) {
	if (X == 0) {
		return ans;
	}
	if (ans.size() >= mlen) return {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
	vector<int> ret = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
	ans.push_back(0);
	for (auto& a : Bs) {
		if (!isS(a, mx) || a > X) continue;
		int Y = X - a;
		ans.back() = a;
		auto b = calc(Y, a, mlen);
		if (b.size() <= mlen) {
			ret = b;
			mlen = b.size();
		}
	}
	ans.pop_back();
	return ret;
}
int main () {
	int L = (((((((2 * 3) + 1) * 3 + 1) * 3 + 2) * 3 + 1) * 3 + 2) * 3 + 1) * 3 + 2;
	// cout << L << endl;
	int XX[] = {0, 1, 8};
	for (int i = L; i; i --) {
		int y = 0;
		int b = 1;
		int j = i;
		while (j) {
			y += b * XX[j % 3];
			j /= 3;
			b *= 10;
		}
		Bs.push_back(y);
	}
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		ans = {};
		auto ret = calc(N - n, 88888888);
		cout << ret.size() << endl;
		for (auto a : ret) cout << a << endl;
	}
	// int T = 1;
	// cin >> T;
	// // T = 1;
	// while (T--) {
	// 	solve();
	// }
	// cout << flush;
}
0