結果
問題 | No.645 Count Permutation |
ユーザー |
|
提出日時 | 2025-01-27 19:17:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 1,310 bytes |
コンパイル時間 | 1,808 ms |
コンパイル使用メモリ | 160,668 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-27 19:17:11 |
合計ジャッジ時間 | 3,004 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 34 |
ソースコード
#include<bits/stdc++.h> #define lowbit(x) x & (-x) #define pi pair<ll, ll> #define ls(k) k << 1 #define rs(k) k << 1 | 1 #define fi first #define se second #define int long long using namespace std; typedef __int128 __; typedef long double lb; typedef double db; typedef unsigned long long ull; typedef long long ll; const int N = 65, mod = 1e9 + 7; inline ll read(){ ll x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9'){ if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9'){ x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; } inline void write(ll x){ if(x < 0){ putchar('-'); x = -x; } if(x > 9) write(x / 10); putchar(x % 10 + '0'); } int n, l, r, ans, s1, s2, sum = 1; int dp[N]; signed main(){ n = read(), l = read(), r = read(); for(int i = 1; i <= n; ++i){ sum = 1ll * sum * i % mod; if(i == n - 1) s1 = sum; if(i == n) s2 = sum; } if(!l) ans = (s2 - s1 + mod) % mod; dp[1] = 1; for(int i = 2; i < n; ++i){ for(int j = N - 2; j >= 1; --j){ dp[j + 1] = (dp[j + 1] + dp[j]) % mod; dp[j] = 1ll * dp[j] * (i - 1) % mod; } } for(int i = 1; i < 62; ++i) if(l <= (1ll << i) && (1ll << i) <= r) ans = (ans + dp[i]) % mod; write(ans); return 0; }