結果

問題 No.1388 Less than K
コンテスト
ユーザー vjudge1
提出日時 2026-01-06 09:19:02
言語 C++11（廃止可能性あり）
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 782 ms / 3,000 ms
コード長 1,743 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 676 ms
コンパイル使用メモリ 83,524 KB
実行使用メモリ 17,408 KB
最終ジャッジ日時 2026-01-06 09:19:19
合計ジャッジ時間 16,142 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 74
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 2e5 + 12;
const int B = 500;
const int mod = 998244353;
int n,m,k;
long long fct[MAXN<<1],rev[MAXN<<1],rfct[MAXN<<1];
long long f[MAXN<<1];
#define C(x,y) (fct[x]*rfct[y]%mod*rfct[(x)-(y)]%mod)
int p[MAXN<<1],q[MAXN<<1];
inline void upd(int&x,int y)
{
    x += y;
    if (x>=mod) x -= mod;
}
void solve1()
{
    f[0] = 1;
    p[k] = 1;
    for (int t=1;t<=n+m;t++)
    {
        for (int i=0;i<=2*k;i++)
        {
            if (i>0) upd(q[i-1],p[i]);
            if (i<2*k) upd(q[i+1],p[i]);
        }
        for (int i=0;i<=2*k;i++)
        {
            p[i] = q[i],q[i] = 0;
        }
        f[t] = p[k];
    }
}
inline long long cal(int D,int H)
{
    if (H<0) H = -H;
    if (H>D) return 0;
    return C(D,(D+H)/2);
}
void solve2()
{
    f[0] = 1;
    for (int t=2;t<=n+m;t+=2)
    {
        f[t] = cal(t,0);
        int x = 0,y = 0;
        for (int i=1;i<=t/(k*2)+3;i++)
        {
            if (i%2==1) x = (k*2+2-x),y = (-k*2-2-y);
            else y = (k*2+2-y),x = (-k*2-2-x);
            if (i%2==1) f[t] = (f[t] - cal(t,x) - cal(t,y) + 2ll*mod)%mod;
            else f[t] = (f[t] + cal(t,x) + cal(t,x))%mod;
        }
    }
}
int main()
{
    fct[0] = rfct[0] = rev[1] = fct[1] = rfct[1] = 1;
    for (int i=2;i<MAXN*2;i++)
        fct[i] = fct[i-1]*i%mod,
        rev[i] = (mod-mod/i)*rev[mod%i]%mod,
        rfct[i] = rfct[i-1]*rev[i]%mod;
    scanf("%d%d%d",&n,&m,&k);
    n--,m--;
    if (n>m) swap(n,m);
    k = k/2;
    if (k<=B/2) solve1();
    else solve2();
    long long ans = 0;
    for (int i=0;i<=n;i++)
    {
        ans = (ans + C(n+m,i*2)*f[i*2]%mod*C(n+m-2*i,n-i))%mod;
    }
    printf("%lld",ans);
    return 0;
}
0