提出 #46945971

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=(l);i<=(r);++i)
const int N=2010;
const int mod=924844033;
typedef long long ll;
using namespace std;
typedef vector<ll> poly;
template<typename T1,typename T2>
void Add(T1 &a,T2 b){a+=b;if(a>=mod)a-=mod;return;}
template<typename T1,typename T2>
void Sub(T1 &a,T2 b){a-=b;if(a<0)a+=mod;return;}
struct Chain{int len;poly f;}chain[N<<1];
bool vis[N][2];
ll binom[N][N],fac[N];
int n,k,tot;
poly operator * (const poly &a,const poly &b)
{
    int len_a=(a.size()-1),len_b=(b.size()-1);poly res;res.resize((len_a+len_b+1));
    For(i,0,len_a){For(j,0,len_b){ll delta=a[i];(delta*=b[j])%=mod;Add(res[i+j],delta);}}
    return res;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;tot=0;For(i,1,n){vis[i][0]=false;vis[i][1]=false;}
    binom[0][0]=1;For(i,1,n)binom[i][0]=1;For(j,1,n)binom[0][j]=0;For(i,1,n){For(j,1,n){binom[i][j]=binom[i-1][j-1];Add(binom[i][j],binom[i-1][j]);}}
    fac[0]=1;For(i,1,n){fac[i]=i;(fac[i]*=fac[i-1])%=mod;}
    For(i,1,n)
    {
        if(vis[i][0]==false)
        {
            ++tot;int it=i,type=0,now_len=0;
            while(it<=n){vis[it][type]=true;++now_len;it+=k;type^=1;if(it>n)break;}
            chain[tot].len=now_len;
        }
        if(vis[i][1]==false)
        {
            ++tot;int it=i,type=1,now_len=0;
            while(it<=n){vis[it][type]=true;++now_len;it+=k;type^=1;if(it>n)break;}
            chain[tot].len=now_len;
        }
    }
    For(i,1,tot)
    {
        chain[i].f.resize(chain[i].len);
        int lim=(chain[i].len-1);
        For(edge_cnt,0,lim)chain[i].f[edge_cnt]=binom[chain[i].len-edge_cnt][edge_cnt];
    }
    poly prod_f=chain[1].f;For(i,2,tot)prod_f=(prod_f*chain[i].f);
    {int len=(prod_f.size()-1);For(i,len+1,n)prod_f.emplace_back(0);};
    ll ans=0;For(i,0,n){ll delta=prod_f[i];(delta*=fac[n-i])%=mod;if(i&1)Sub(ans,delta);else Add(ans,delta);}cout<<ans;return 0;
}

提出情報

ジャッジ結果