結果
問題 | No.1552 Simple Dice Game |
ユーザー |
![]() |
提出日時 | 2021-06-18 23:52:36 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 292 ms / 2,500 ms |
コード長 | 2,156 bytes |
コンパイル時間 | 3,291 ms |
コンパイル使用メモリ | 142,644 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-22 21:41:11 |
合計ジャッジ時間 | 6,972 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#include <cmath>#include <deque>#include <algorithm>#include <iterator>#include <list>#include <tuple>#include <map>#include <unordered_map>#include <queue>#include <set>#include <unordered_set>#include <stack>#include <string>#include <vector>#include <fstream>#include <iostream>#include <functional>#include <numeric>#include <iomanip>#include <stdio.h>//eolibraries#define lnf 3999999999999999999#define inf 999999999#define fi first#define se second#define pb push_back#define ll long long#define ld long double#define all(c) (c).begin(),(c).end()#define sz(c) (int)(c).size()#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end())#define pii pair <int,int>#define rep(i,n) for(int i = 0 ; i < n ; i++)#define drep(i,n) for(int i = n-1 ; i >= 0 ; i--)#define crep(i,x,n) for(int i = x ; i < n ; i++)#define vi vector <int>#define vec(...) vector<__VA_ARGS__>#define fcin ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);//eodefineusing namespace std;const int max_n = 103002;const ll mod = 998244353;ll n,m;ll binpow(ll a, ll b) {a %= mod; ll res = 1;while (b) { if (b%2) res = res * a % mod; a = a * a % mod; b /= 2; }return res % mod;}ll fact[max_n],invfact[max_n];void prefact() {fact[0]=fact[1]=1;invfact[1]=1;rep(i,max_n-3){if(i>1)fact[i] = fact[i-1]*i; fact[i] %= mod;if(i>1)invfact[i]=mod-invfact[mod%i]*(mod/i)%mod;}}ll sub(ll a , ll b){a%=mod; b%=mod;return (((a-b)%mod)+mod)%mod;}ll prod(ll a , ll b){a%=mod; b%=mod;return ((a*b)%mod);}ll add(ll a , ll b){a%=mod; b%=mod;return (a+b)%mod;}ll f(ll i){return (i*(i+1))/2;}int main(){fcin;prefact();cin>>n>>m;ll ans=0,g=0;drep(i,m+1){if(i==0)break;// ll k=()ll x=binpow((m-i+1),n-1);ll sum=f(m)-f(i-1);ll d = prod(x,prod(sum,n));d = sub(d,g);ans = sub(ans,prod(i,d));// cout<<d<<" ";g = add(g,d);}g=0;crep(i,1,m+1){ll x=binpow(i,n-1);ll sum=f(i);ll d=prod(x,prod(sum,n));d = sub(d,g);ans = add(ans,prod(i,d));g = add(g,d);// cout<<d<<" ";}cout<<ans<<"\n";/**/return 0;}