結果

問題 No.1504 ヌメロニム
ユーザー kotatsugame
提出日時 2021-05-08 01:51:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 170 ms / 2,000 ms
コード長 627 bytes
コンパイル時間 2,159 ms
コンパイル使用メモリ 112,452 KB
実行使用メモリ 24,100 KB
最終ジャッジ日時 2024-09-15 13:39:46
合計ジャッジ時間 7,193 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 61
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main()
      | ^~~~

ソースコード

diff #

#include<iostream>
#include<atcoder/modint>
#include<atcoder/convolution>
using namespace std;
using mint=atcoder::modint998244353;
int N;
string S;
main()
{
	cin>>N>>S;
	vector<mint>I(N),J(N);
	for(int i=0;i<N;i++)
	{
		if(S[i]=='i')I[N-i-1]=1;
		else J[i]=1;
	}
	vector<mint>K=convolution(I,J);
	vector<mint>A(N-1);
	mint p=1;
	for(int i=0;i<N-1;i++)
	{
		A[i]=K[N+i]*p;
		p*=i+1;
	}
	vector<mint>B(N-1);
	vector<mint>inv(N-1);
	p=1/p;
	for(int i=N-2;i>=0;i--)
	{
		B[N-2-i]=p*=i+1;
		inv[i]=p;
	}
	vector<mint>C=convolution(A,B);
	int ans=0;
	for(int k=0;k<N-1;k++)
	{
		ans^=(C[N-2+k]*inv[k]).val();
	}
	cout<<ans<<endl;
}
0