結果

問題 No.3040 Aoiスコア
ユーザー tokitsukaze
提出日時 2025-02-28 22:07:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 306 ms / 1,000 ms
コード長 1,729 bytes
コンパイル時間 2,140 ms
コンパイル使用メモリ 197,232 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-28 22:07:10
合計ジャッジ時間 3,491 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:53:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
main.cpp:54:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   54 |         scanf("%s",s+1);
      |         ~~~~~^~~~~~~~~~
main.cpp:58:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |                 scanf("%d%d",&a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const int mod=998244353;
const int MAX=6000+10;
ll qpow(ll a,ll b)
{
    ll res=1;
    while(b>0)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll inv(ll x){return qpow(x,mod-2);}
int fac[MAX],invfac[MAX];
void init_comb(int n)
{
    assert(n<MAX);
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    invfac[n]=inv(fac[n]);
    for(int i=n-1;~i;i--) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
}
ll C(int n,int m)
{
    if(m>n||m<0||n<0) return 0;
    return 1ll*fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
ll A(int n,int m)
{
    if(m>n||m<0||n<0) return 0;
    return 1ll*fac[n]*invfac[n-m]%mod;
}
vector<int> mp[MAX];
char s[MAX];
ll pw24[MAX],pw26[MAX];
int main()
{
    int n,m,i,j,k,a,b,cnta,cnti,cntw,totw,noww;
    ll ans;
    pw24[0]=pw26[0]=1;
    for(i=1;i<MAX;i++)
    {
        pw24[i]=pw24[i-1]*24%mod;
        pw26[i]=pw26[i-1]*26%mod;
    }
    init_comb(MAX-10);
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(i=1;i<=n;i++) mp[i].clear();
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    totw=0;
    for(i=1;i<=n;i++) totw+=(s[i]=='?');
    ans=0;
    for(i=1;i<=n;i++)
    {
        if(s[i]!='o' && s[i]!='?') continue;
        cnta=cnti=cntw=0;
        if(s[i]=='?') noww=1;
        else noww=0;
        for(auto &to:mp[i])
        {
            if(s[to]=='a') cnta++;
            else if(s[to]=='i') cnti++;
            else if(s[to]=='?') cntw++;
        }
        noww+=cntw;
        for(j=cnta;j<=cnta+cntw;j++)
        {
            for(k=cnti;k<=cnti+(cnta+cntw)-j;k++)
            {
                ans+=1LL*j*k%mod
                    *C(cntw,j-cnta)%mod
                    *C(cntw-(j-cnta),k-cnti)%mod
                    *pw24[cnta+cnti+cntw-j-k]%mod
                    *pw26[totw-noww];
                ans%=mod;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0