結果

問題 No.1321 塗るめた
コンテスト
ユーザー vjudge1
提出日時 2025-10-13 15:49:33
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 1,031 bytes
コンパイル時間 4,537 ms
コンパイル使用メモリ 210,284 KB
実行使用メモリ 8,556 KB
最終ジャッジ日時 2025-10-13 15:49:40
合計ジャッジ時間 6,961 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int kmaxn=1e5+10,mod=998244353,kmaxA=5005+10,kmaxB=5005;
int qr[kmaxn],ni[kmaxn],n2[kmaxn],nt2[kmaxn];
int S[kmaxA][kmaxB];
int ksm(int x,int y){
    int w=1;
    while(y){if(y&1)w=w*x%mod;x=x*x%mod;y>>=1;}
    return w;
}
int C(int x,int y){
    if(x<y||y<0)return 0;
    return qr[x]*ni[y]%mod*ni[x-y]%mod;
}
void Ft(){
    qr[0]=ni[0]=1;
    for(int i=1;i<kmaxn;i++){
        qr[i]=qr[i-1]*i%mod;
        ni[i]=ksm(qr[i],mod-2);
    }
    n2[0]=nt2[0]=1;for(int i=1;i<kmaxn;i++)n2[i]=n2[i-1]*2%mod;
    int c=(mod+1)/2;for(int i=1;i<kmaxn;i++)nt2[i]=nt2[i-1]*c%mod;
}
int n,m,k;
signed main(){
//    freopen("main.in","r",stdin);
//    freopen("main.out","w",stdout);
    ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);Ft();
    cin>>n>>m>>k;
    int ans=0;
    for(int i=k;i>=1;i--){
        ans=(ans+(k%2==i%2?1:mod-1)*C(m,k)%mod*C(k,i)%mod*(ksm(i+m,n)-ksm(m,n)+mod)%mod)%mod;
//        cout<<ans<<"\n";
    }
    cout<<ans<<"\n";
    return 0;
}
0