結果
問題 | No.336 門松列列 |
ユーザー | sugim48 |
提出日時 | 2016-01-15 22:56:56 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 287 ms / 2,000 ms |
コード長 | 1,989 bytes |
コンパイル時間 | 719 ms |
コンパイル使用メモリ | 82,840 KB |
実行使用メモリ | 19,280 KB |
最終ジャッジ日時 | 2023-09-02 18:44:06 |
合計ジャッジ時間 | 4,519 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 285 ms
19,064 KB |
testcase_01 | AC | 2 ms
4,368 KB |
testcase_02 | AC | 282 ms
19,120 KB |
testcase_03 | AC | 282 ms
19,048 KB |
testcase_04 | AC | 287 ms
19,144 KB |
testcase_05 | AC | 1 ms
4,368 KB |
testcase_06 | AC | 282 ms
19,072 KB |
testcase_07 | AC | 284 ms
19,280 KB |
testcase_08 | AC | 285 ms
19,084 KB |
testcase_09 | AC | 286 ms
19,060 KB |
testcase_10 | AC | 287 ms
19,060 KB |
testcase_11 | AC | 287 ms
19,148 KB |
ソースコード
#define _USE_MATH_DEFINES #include <algorithm> #include <cstdio> #include <functional> #include <iostream> #include <cfloat> #include <climits> #include <cstdlib> #include <cstring> #include <cmath> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <time.h> #include <vector> using namespace std; #define rep(i,a,n) for (int i=a;i<(int)n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) #define ACCU accumulate #define TWO(x) (1<<(x)) #define TWOL(x) (1ll<<(x)) #define clr(a) memset(a,0,sizeof(a)) typedef vector<int> VI; typedef vector<string> VS; typedef long long ll; typedef long double LD; typedef pair<int,int> PII; typedef vector<PII> VPII; const int inf=0x20202020; const ll mod=1000000007; const double eps=1e-9; const double pi=3.1415926535897932384626; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} // head ll f[1010000],g[1010000],dp[2600]; class PermutationCounts { public: int countPermutations(int N, vector <int> pos) { f[0]=1; rep(i,1,1000001) f[i]=f[i-1]*i%mod; rep(i,0,1000001) g[i]=powmod(f[i],mod-2); sort(all(pos)); pos.insert(pos.begin(),0); pos.pb(N); int m=SZ(pos)-1; dp[0]=1; rep(i,1,m+1) { dp[i]=0; rep(j,0,i) dp[i]=(dp[i]-dp[j]*g[pos[i]-pos[j]])%mod; } ll ans=dp[m]*f[N]%mod; if (m%2) ans*=-1; if (ans<0) ans+=mod; return ans; } }; int main() { int N; cin >> N; if (N <= 2) { cout << 0 << endl; return 0; } PermutationCounts pc; vector<int> a, b; for (int i = 0; i + 1 < N; i++) if (i % 2 == 0) a.push_back(i + 1); else b.push_back(i + 1); cout << (pc.countPermutations(N, a) + pc.countPermutations(N, b)) % mod << endl; }