結果
問題 | No.2649 [Cherry 6th Tune C] Anthem Flower |
ユーザー |
|
提出日時 | 2024-02-23 21:43:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 670 ms / 2,000 ms |
コード長 | 3,221 bytes |
コンパイル時間 | 2,787 ms |
コンパイル使用メモリ | 202,620 KB |
最終ジャッジ日時 | 2025-02-19 19:38:23 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;long long mod = 998244353;//入力が必ずmod未満の時に使う.struct mint{long long v = 0;mint(){} mint(int a){v = a;} mint(long long a){v = a;} mint(unsigned long long a){v = a;}long long val(){return v;}void modu(){v %= mod;}mint repeat2mint(long long a,long long b){mint ret = 1,p = a; int Log = 60;if(b <= 2e9) Log = 30;for(int i=0; i<Log; i++){if(b&(1LL<<i)) ret *= p; p *= p;}return ret;};mint operator+(mint b){return (v+b.v)%mod;}mint operator-(mint b){return (v-b.v+mod)%mod;}mint operator*(mint b){return v*b.v%mod;}mint operator/(mint b){if(b.v == 0) assert(false);return v*(repeat2mint(b.v,mod-2)).v%mod;}void operator+=(mint b){v = (v+b.v)%mod;}void operator-=(mint b){v = (v-b.v+mod)%mod;}void operator*=(mint b){v = v*b.v%mod;}void operator/=(mint b){if(b.v == 0) assert(false);v = v*repeat2mint(b.v,mod-2).v%mod;}void operator++(int){v = (v+1)%mod; return;}void operator--(int){v = (v-1+mod)%mod; return;}bool operator==(mint b){if(v == b.v) return true; else return false;}bool operator!=(mint b){if(v != b.v) return true; else return false;}bool operator>(mint b){if(v > b.v) return true; else return false;}bool operator>=(mint b){if(v >= b.v) return true; else return false;}bool operator<(mint b){if(v < b.v) return true; else return false;}bool operator<=(mint b){if(v <= b.v) return true; else return false;}mint pow(long long x){return repeat2mint(v,x);}mint inv(){return mint(1)/v;}};int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int T; cin >> T;while(T--){string s; cin >> s; cin >> mod;reverse(s.begin(),s.end());int N = s.size();vector<long long> A,B;for(auto c : s) A.push_back((int)(c-'0'));A.push_back(0);B = A;B.at(0)++;for(int i=0; i<N; i++){if(B.at(i) == 10) B.at(i) = 0,B.at(i+1)++;else break;}vector<long long> C;if(A.at(0)%2 == 0){long long now = 0;for(int i=N-1; i>=0; i--){long long c = 0;if(now) c = 5;if(A.at(i)%2) now = 1;else now = 0;c += A.at(i)/2;C.push_back(c);}reverse(C.begin(),C.end());A = C;}else{long long now = 0;for(int i=N; i>=0; i--){long long c = 0;if(now) c = 5;if(B.at(i)%2) now = 1;else now = 0;c += B.at(i)/2;C.push_back(c);}reverse(C.begin(),C.end());B = C;}vector<mint> p10(N+1,1);for(int i=1; i<=N; i++) p10.at(i) = p10.at(i-1)*10;mint a = 0,b = 0;for(int i=0; i<A.size(); i++) a += p10.at(i)*A.at(i);for(int i=0; i<B.size(); i++) b += p10.at(i)*B.at(i);cout << (a*b).v << endl;}}