fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<unordered_set>
  3. using namespace std;
  4. #define       fio         ios_base::sync_with_stdio(false)
  5.  
  6. #define       ll          long long int
  7.  
  8. #define       s(x)        scanf("%lld",&x)
  9. #define       s2(x,y)     s(x)+s(y)
  10. #define       s3(x,y,z)   s(x)+s(y)+s(z)
  11.  
  12. #define       p(x)        printf("%lld\n",x)
  13. #define       p2(x,y)     p(x)+p(y)
  14. #define       p3(x,y,z)   p(x)+p(y)+p(z)
  15. #define       all(x)      x.begin(),x.end()
  16. #define       F(i,a,b)    for(ll i = (ll)(a); i <= (ll)(b); i++)
  17. #define       RF(i,a,b)   for(ll i = (ll)(a); i >= (ll)(b); i--)
  18.  
  19. #define       ff          first
  20. #define       ss          second
  21. #define       mp(x,y)     make_pair(x,y)
  22. #define       pll         pair<ll,ll>
  23. #define       pb          push_back
  24.  
  25. ll inf = 1e18;
  26. ll mod = 1e9 + 7 ;
  27. ll gcd(ll a , ll b){return b==0?a:gcd(b,a%b);}
  28.  
  29. //setbase - cout << setbase (16); cout << 100 << endl; Prints 64
  30. //setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
  31. //setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
  32. //cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
  33.  
  34. /**************************CODE GOES HERE*********************************************/
  35.  
  36. ll modExpo(ll b,ll e){
  37. 	if(e==0)return 1ll;
  38. 	if(b==1)return 1ll;
  39. 	ll ans=1ll;
  40. 	while(e>0){
  41. 		if(e%2 == 1){
  42. 			ans=(ans*b)%mod;
  43. 		}
  44. 		b=(b*b)%mod;
  45. 		e=e/2;
  46. 	}
  47. 	return ans;
  48. }
  49.  
  50. int main()
  51. {
  52.    //freopen("input.txt","r",stdin);
  53.    //freopen("output.txt","w",stdout);
  54.   ll t=1;
  55.   ll tc=1ll;
  56.   s(t);
  57.   while(t--){
  58.   	ll N, K, x1, y1, C, D, E1, E2 , F;
  59.   	s3(N,K,x1);
  60.   	s3(y1,C,D);
  61.   	s3(E1,E2,F);
  62.  
  63.   	vector<ll>params(N+1);
  64.   	params[1]=(x1+y1)%F;
  65.   	F(i,2,N){
  66.   		ll x=(C*(x1)+D*(y1)+E1)%F;
  67.   		ll y=(D*(x1)+C*(y1)+E2)%F;
  68.   		params[i]=(x+y)%F;
  69.   		x1=x;
  70.   		y1=y;
  71.   	}
  72.   	// for(auto el:params)cout<<el<<" ";
  73.   	// cout<<endl;
  74.  
  75.   	// cout<<modExpo(3,0);
  76.   	// return 0;
  77.  
  78.     vector<ll>cumSum(1+N,0ll);
  79.     ll sum=K%mod;
  80.     cumSum[1]=sum;
  81.     for(ll i=2;i<=N;i++){
  82.       ll temp=modExpo(i,K);
  83.       temp=(i*temp)%mod;
  84.       temp=(temp*modExpo(i-1ll,mod-2ll))%mod;
  85.       ll temp1 = (i*modExpo(i-1ll,mod-2ll))%mod;
  86.       temp = (temp - temp1 + mod)%mod;
  87.       sum+=temp;
  88.       sum%=mod;
  89.       cumSum[i]=sum;
  90.     }
  91.  
  92.     ll ans=0ll;
  93.     for(ll i=1;i<=N;i++){
  94.         ll times=N-i+1ll;
  95.         ans+=((params[i]%mod) *(times*cumSum[i])%mod)%mod;
  96.         ans%=mod;
  97.         // for(ll k=1;k<=K;k++){
  98.         //   for(ll j=1;j<=i;j++){
  99.         //     ans+=(params[i]*(times*modExpo(j,k))%mod)%mod;
  100.         //     ans%=mod;
  101.         //   }
  102.         // }      
  103.     }
  104.  
  105.  //  	ll ans=0ll;
  106.  //  	for(ll k=1;k<=K;k++){
  107. 	//   	for(ll len=1ll;len<=N;len++){
  108. 	//   		for(ll i=1ll;i<=N-len+1ll;i++){
  109. 	//   			for(ll j=i,bb=1ll;j<i+len;j++,bb++){
  110. 	//   				ans=ans+(params[j]*modExpo(bb,k))%mod;
  111. 	//   				ans%=mod;
  112. 	//   			}
  113. 	//   		}
  114. 	//   	}
  115. 	// }
  116.   	cout<<"Case #"<<tc++<<": "<<ans<<endl;;
  117.   }
  118.   return 0;
  119.  }
Success #stdin #stdout 0.42s 10656KB
comments (?)
stdin
copy 
1
500000 9452 94317 5965 1489 39467 18916 75815 54537
110000 8295 14402 93014 13404 7756 74325 77427 84030
500000 10000 30561 21975 53591 31952 93102 76554 53104
1000000 10000 100000 100000 100000 100000 100000 100000 100000
600000 10000 18937 8116 94255 62475 814 34142 90468
870000 4741 51027 92754 55368 27584 66108 76391 79390
1000000 10000 81787 24267 6004 68145 23498 49500 23470
280000 5846 83440 36500 80682 92764 59074 96653 82402
1000000 10000 84975 37608 64435 51351 29939 28236 26151
580000 9240 61280 75136 59131 59515 55946 82679 76908
100000 10000 79147 72914 71942 2140 33364 72088 52616
900000 10000 67275 49382 26042 91717 18946 93469 74226
440000 8195 53487 80337 62873 98653 63778 32167 20656
300000 10000 81863 56812 89253 18861 4359 57934 95528
390000 6297 43615 66875 74844 77804 71414 402 17891
550000 9030 35499 52192 37901 39347 13957 50495 46559
370000 2651 53554 2469 75968 21383 96153 38235 87407
300000 10000 52530 86404 83500 86987 67468 59033 76381
1000000 10000 1 1 1 1 1 1 997
830000 1345 45872 7052 5012 89927 24374 11753 22418
100000 10000 769 40153 44676 95357 8402 65093 83119
600000 10000 57925 94840 88394 48407 45826 42784 44628
620000 5623 31391 91483 9337 3738 65811 95462 74442
900000 10000 39550 99855 33172 27952 40337 73033 76823
600000 10000 62911 35250 12497 48560 51624 46764 22519
700000 10000 88883 84087 80436 40529 71592 21857 71958
630000 5344 91466 72309 99771 55417 80836 24575 44587
400000 10000 30436 16222 17492 99878 52473 27627 21511
720000 9507 30533 53620 43866 89808 41868 21449 81026
900000 10000 63965 371 97158 13010 69228 67345 27765
900000 10000 15400 63232 12239 17840 5307 17400 29447
270000 2855 40409 70476 90125 81335 73824 91372 70556
100000 10000 36890 3440 94228 24195 12386 31475 54937
560000 8437 45499 38377 83488 77452 1765 19191 76453
700000 10000 43167 60140 51130 42777 98757 65632 92816
860000 5708 35521 29911 32171 90813 82311 58819 54891
720000 8898 45916 91167 36660 23302 27479 54618 34480
560000 1235 81569 96362 36297 47311 53688 84849 54749
200000 10000 12522 60685 62496 1145 78823 89333 95541
320000 2007 19901 59614 81284 37442 66872 1895 75756
700000 10000 74703 62754 69259 55924 7821 78471 84455
200000 10000 45032 85499 49962 89239 16618 47206 5739
100000 10000 7500 26627 34761 50169 89738 31322 39590
460000 1182 3423 44038 32608 43026 54835 16560 30707
400000 10000 94949 82522 91900 35042 54704 79202 49359
700000 10000 30812 72220 29116 24641 8256 12394 27484
790000 6015 58517 59888 95663 15015 54851 87049 9322
810000 8786 35590 2307 90010 61767 10936 19455 43789
800000 10000 73047 48812 36376 57716 1648 47805 28600
700000 10000 60222 19364 22480 48433 78266 64103 19763
110000 5635 71523 67561 63431 110 50807 29189 54319
710000 3425 62368 47810 91389 51433 28356 31249 73353
900000 10000 9462 28583 24338 91219 30445 83720 85216
30000 2495 54934 74437 55117 84895 73237 84017 26140
710000 3156 29238 18629 17624 57026 22614 63689 65691
100000 10000 1073 94928 23398 84181 15782 50485 12240
990000 8078 11651 59502 89354 6646 70490 95585 68893
400000 10000 40996 46599 81206 98021 69491 7754 30400
900000 10000 7303 60114 55656 84377 54880 55218 87590
790000 5222 99233 95942 4128 6529 19697 75122 75197
700000 10000 52454 31320 23334 70734 50264 59329 8426
500000 10000 97732 63772 80065 37771 78797 26105 73336
830000 3792 88289 14370 33374 36470 55861 96015 37584
300000 10000 41099 42026 12319 50537 82240 46600 5773
1000000 3604 95720 12254 26997 53853 90806 45971 99682
420000 9921 24455 23885 18189 60184 27151 88685 92262
540000 445 47507 89232 29976 48845 30413 75085 43608
340000 879 96760 50251 74517 95982 51820 42158 37360
500000 9865 58580 68572 96034 91421 39384 41716 30559
1000000 10000 9566 23616 26502 63618 63395 90787 24787
300000 10000 91318 19848 8848 14500 18775 97569 74751
400000 10000 15332 80945 68367 914 85997 85846 9015
1000000 10000 60757 73453 67621 56796 16700 51295 27085
900000 10000 11467 12699 69331 92399 55351 22733 11193
200000 10000 31143 29813 85245 68838 5962 42267 34078
10 10 10001 10002 10003 10004 10005 10006 89273
200000 10000 84938 38768 30905 70935 7085 49961 86216
700000 10000 79815 28749 84945 64376 19288 56362 23687
430000 37 79662 70672 99234 49249 95587 39275 64544
320000 8668 33972 34057 37743 76512 71011 29446 29088
230000 2934 37825 60241 52968 18909 84427 98432 16008
960000 5898 99231 13196 17780 16008 11302 25673 97524
990000 9158 50012 9039 31822 25965 51696 36612 64298
400000 10000 63387 30355 53252 58395 55785 94661 43869
630000 4933 57898 58833 87261 77063 17907 26323 51449
330000 8867 86600 22150 21684 99238 76352 76245 12655
950000 4422 779 78061 77478 56949 7092 26647 62626
730000 780 29026 96735 27590 33440 41109 46695 91946
680000 697 71035 59311 59541 67841 24047 40992 95211
750000 9712 62016 9498 50519 48059 59004 87609 56753
100000 10000 81056 47654 62309 73446 58256 97146 37070
20000 7140 5874 50976 88694 15069 5005 72660 77418
800000 10000 58219 42240 98174 41782 79330 62925 29285
900000 10000 55222 70311 79570 12427 77047 75664 3060
2 3 1 2 1 2 1 1 9
600000 10000 32662 29258 87428 3031 49520 57074 33428
800000 10000 59786 65720 44765 19238 94147 58102 23317
200000 10000 76913 87555 93016 85788 2618 54249 38532
250000 3365 77754 64338 26971 13977 15820 89964 37734
680000 6838 3537 72334 58095 33047 60398 72851 16049
stdout
copy 
Case #1: 123912999
https://ideone.com/YPwvcp
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!