結果

問題 No.3040 Aoiスコア
ユーザー tokitsukaze
提出日時 2025-02-28 22:07:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 319 ms / 1,000 ms
コード長 1,729 bytes
コンパイル時間 1,999 ms
コンパイル使用メモリ 197,700 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-20 20:58:14
合計ジャッジ時間 3,996 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
0