結果
問題 | No.2060 AND Sequence |
ユーザー |
![]() |
提出日時 | 2022-08-26 22:38:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,632 bytes |
コンパイル時間 | 1,371 ms |
コンパイル使用メモリ | 169,404 KB |
実行使用メモリ | 5,760 KB |
最終ジャッジ日時 | 2024-10-13 23:16:02 |
合計ジャッジ時間 | 2,621 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 WA * 1 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using P = pair<ll,ll>;#define fix(x) fixed << setprecision(x)#define asc(x) x, vector<x>, greater<x>#define rep(i, n) for(ll i = 0; i < n; i++)#define all(x) (x).begin(),(x).end()template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;}template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;}const ll MOD = 998244353;ll mpow(ll x, ll y){ll res = 1; x %= MOD;while(y){if(y%2) res = res * x % MOD;x = x * x % MOD;y /= 2;}return res;}const int MAX_N = 100100;vector<ll> fac(MAX_N), finv(MAX_N), inv(MAX_N);void init(){fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for(int i=2;i<MAX_N;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;}}ll mcomb(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;}ll mperm(int n,int k){if (n<k) return 0;if (n<0 || k<0) return 0;return fac[n] * finv[n-k] % MOD;}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);init();ll n,m;cin >> n >> m;ll ans = 1, a = __builtin_popcount(m);vector<ll> x(30,0);x[a] = 1;rep(i,30){if(m&(1<<i)){a--;rep(j,i+1){x[j+a] += mcomb(i,j);}}}for(int i=1;i<30;i++){ans += mpow(n,i) * x[i];ans %= MOD;}cout << ans << '\n';return 0;}