### Ashik_01's blog

By Ashik_01, history, 8 months ago, ,

Can anyone plz help me with this problem?Problem

• 0

 » 8 months ago, # |   0 Auto comment: topic has been updated by Ashik_01 (previous revision, new revision, compare).
 » 8 months ago, # | ← Rev. 2 →   0 Just precalculate all factorials in the range [0, 107] modulo 1000000000000037.Then the rest is just range sum.Edit. I tried it out. The answer is correct. But I didn't notice the memory limit (This solution will get MLE). Sorry.
•  » » 8 months ago, # ^ |   +5 Lets solve it offline. There are maximum 2*n different numbers. Calculate factorial only for this numbers. Notice that, when we multiplying the big numbers, there can exists number that  > 1023. So use binary multiplying. My Code#include #define mp make_pair #define pb push_back #define f first #define s second #define forn(i, a, b) for(int i = (a); i <= (b); ++i) #define forev(i, b, a) for(int i = (b); i >= (a); --i) #define VAR(v, i) __typeof(i) v=(i) #define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define all(x) (x).begin(), (x).end() #define sz(x) ((int)(x).size()) #define inf INT_MAX #define int ll using namespace std; typedef long long ll; typedef long double ld; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector Vll; typedef vector > vpii; typedef vector > vpll; const int maxn = (int) 1e7 + 100; const int mod = (int) 1e15 + 37; const double pi = acos(-1.0); int t, ans[222], id; ll f[222], sum[222]; vpii g[222]; vi ok[222]; map was; int binmult(int a, int b){ int res = 0; while(b){ if(b & 1) res += a; b >>= 1; a = (a + a) % mod; } return res; } main () { cin >> t; vi all; forn(i, 1, t){ int l, r; cin >> l >> r; if(!l){ if(!was[r]) was[r] = ++id; if(!was[0]) was[0] = ++id; ok[was[r]].pb(i); all.pb(r); continue; } if(!was[r]) was[r] = ++id; if(!was[l - 1]) was[l - 1] = ++id; g[was[r]].pb(mp(was[l - 1], i)); all.pb(l - 1); all.pb(r); } if(!was[0]) was[0] = ++id; all.pb(0); for(auto x : ok[was[0]]) ans[x] = 1; sort(all(all)); all.resize(unique(all(all)) - all.begin()); f[was[0]] = 1, sum[was[0]] = 1; forn(ii, 1, sz(all) - 1){ int i = all[ii], j = all[ii - 1], curf = f[was[j]], curs = sum[was[j]]; forn(k, j + 1, i){ curf = binmult(curf, k); curs = (curs + curf) % mod; } f[was[i]] = curf, sum[was[i]] = curs; for(auto x : g[was[i]]){ ans[x.s] = (sum[was[i]] - sum[x.f] + mod) % mod; } for(auto x : ok[was[i]]){ ans[x] = curs; } } forn(i, 1, t) cout << ans[i] << endl; }
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +10 You can use 1000-ary multiplication as given (mod = 10 ^15) * 10 ^ 3 < MAX_LONG_INT. It will cost maximum of only 3 operations reducing the log(n) factor. int base = 1000; LL mulmod(LL b, LL a, LL mod) { // (b * a) % mod if(!b) return 0; return ((mulmod(b/base, a, mod) * base ) % mod + (a * (b % base)) % mod) % mod; }