QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#231018#7647. 树哈希Lynkcat40 1ms4196kbC++175.3kb2023-10-28 23:13:052023-10-28 23:13:05

Judging History

你现在查看的是最新测评结果

  • [2023-10-28 23:13:05]
  • 评测
  • 测评结果:40
  • 用时:1ms
  • 内存:4196kb
  • [2023-10-28 23:13:05]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll __int128
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
inline char gc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
#define gc getchar
inline ll read(){char c=gc();ll su=0,f=1;for (;c<'0'||c>'9';c=gc()) if (c=='-') f=-1;for (;c>='0'&&c<='9';c=gc()) su=su*10+c-'0';return su*f;}
inline void write(ll x){if (x<0){putchar('-');write(-x);return;}if (x>=10) write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x),putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
const int N=105;
const string F[N][N]={
{"1","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"},
{"0","1","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"},
{"0","1","2","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"},
{"0","1","9","6","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"},
{"0","1","40","60","24","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"},
{"0","1","135","620","420","120","0","0","0","0","0","0","0","0","0","0","0","0","0","0"},
{"0","1","576","4950","7320","3240","720","0","0","0","0","0","0","0","0","0","0","0","0","0"},
{"0","1","2331","38262","104790","84000","27720","5040","0","0","0","0","0","0","0","0","0","0","0","0"},
{"0","1","9976","329056","1337616","1809360","994560","262080","40320","0","0","0","0","0","0","0","0","0","0","0"},
{"0","1","49167","2585088","17861760","34401024","29620080","12398400","2721600","362880","0","0","0","0","0","0","0","0","0","0"},
{"0","1","261520","23298570","230333760","650991600","770091840","484596000","163900800","30844800","3628800","0","0","0","0","0","0","0","0","0"},
{"0","1","1264923","201666410","3048704010","11992068000","19491650640","16352915040","8108100000","2301868800","379209600","39916800","0","0","0","0","0","0","0","0"},
{"0","1","7499196","2029955400","40907450760","221673303720","476230803840","528497101440","342689719680","140287593600","34328448000","5029516800","479001600","0","0","0","0","0","0","0"},
{"0","1","48145851","18853513692","569381450352","4090163288640","11572348427640","16380248639040","13684449018240","7234033847040","2523759638400","542788646400","71610739200","6227020800","0","0","0","0","0","0"},
{"0","1","282624902","208545510264","8152163189352","77086057904856","278283437271840","500100673952880","520865364539520","348317835465600","155595814133760","47326914835200","9081072000000","1089728640000","87178291200","0","0","0","0","0"},
{"0","1","1816866915","2162998664400","120347621661540","1468956736840320","6748418405088360","15050302055989200","19370055105601200","15895265315529600","8864170595280000","3432547140422400","925996911840000","160408055808000","17653603968000","1307674368000","0","0","0","0"},
{"0","1","13547611072","26305324897680","1848599474688960","28794041030008800","164309578733664000","452558599710497280","707131804060281600","703619397050169600","476068505552640000","227886842902118400","77965463742566400","18904612446720000","2984984690688000","303380453376000","20922789888000","0","0","0"},
{"0","1","95657990591","296154537531504","29061239330523120","574300481045592000","4063118701715892000","13596933593369468160","25639747059038112000","30447531987666393600","24644556812542867200","14192444692384358400","5957501607119462400","1827273024357580800","402504785819136000","58392019445760000","5513155135488000","355687428096000","0","0"},
{"0","1","728122042512","3992150752821090","485883201817925856","11765951504681397120","101850607783224760320","411387714895093372800","924886619869925905920","1302381750288843544320","1241872782824440166400","847186002528696230400","425046860209017446400","159037105867037798400","44240722425265766400","8930511022777344000","1198310945255424000","105639166144512000","6402373705728000","0"},
{"0","1","5844862093851","49629324211196850","8133726351536089362","247590273863499582816","2594284833364382851200","12553781400629160148800","33409626709338411517440","55227445993192438667520","61602037034137852412160","49023018235978449062400","28922067190973897740800","12867542548242897715200","4347066225570292224000","1107072798346548633600","206284747564127232000","25748212919869440000","2128789257154560000","121645100408832000"}};
int mod;
int n,q;
string st[N];
poly G[N],E[N];
int fac[N],inv[N];
int tot;
map<string,int>Mp,vis;
int ans;
inline ll quickPower(ll x,ll y)
{
    ll res=1;
    while (y)
    {
        if (y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
void BellaKira()
{
    n=read(),q=read(),mod=read();
    for (int i=1;i<=n;i++)
    {
        int ans=0;
        for (int j=1;j<=i;j++)
        {
            int nw=0;
            for (auto u:F[i-1][j-1]) nw=(nw*10+u-'0')%mod;
            ans=(ans+nw%mod*quickPower(q,j)%mod)%mod;
        }
        writeln(ans);
    }
}
signed main()
{
    // freopen("biao.txt","w",stdout);
    IOS;
    cin.tie(0);
    int T=1;
    while (T--)
    {
        BellaKira();
    }
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 40
Acceptable Answer

Test #1:

score: 40
Acceptable Answer
time: 1ms
memory: 4136kb

input:

100 910342260 935929297

output:

910342260
816177711
569226551
514707635
267406725
391906453
250727611
208481307
81485772
23235693
216730633
285646992
175230876
274553119
174038157
203318484
775234565
322891510
933522659
900692754
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

points 0.40 You got 40 pts!

Test #2:

score: 40
Acceptable Answer
time: 1ms
memory: 3984kb

input:

100 222959056 947643239

output:

222959056
358599927
365062242
287299555
872152310
785181552
689517811
751458049
373969559
887125628
238000283
265869067
862846962
717459206
118380127
903859172
38731072
220551290
311944377
678478487
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

points 0.40 You got 40 pts!

Test #3:

score: 40
Acceptable Answer
time: 1ms
memory: 3920kb

input:

100 135352674 235854343

output:

135352674
116843515
129198122
128256418
202034449
101078108
134511179
26177395
38146936
177689345
171471260
220203615
2725266
54489245
202150371
51581049
9159057
174134120
214954721
6858381
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

points 0.40 You got 40 pts!

Test #4:

score: 40
Acceptable Answer
time: 1ms
memory: 4196kb

input:

100 538608644 566215339

output:

538608644
365236991
134179965
39370099
416828003
17910602
226317362
529379896
407121368
81806097
249408176
336758120
296361261
35236747
429449088
328368699
409154256
418665686
24463075
203118458
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

points 0.40 You got 40 pts!

Test #5:

score: 40
Acceptable Answer
time: 1ms
memory: 3984kb

input:

100 56831820 281897771

output:

56831820
213573518
5338712
114481529
104176011
222091299
258318286
168492731
248042852
279768543
163273831
250332871
125456436
55441194
94771937
85241933
265069860
227132810
189427807
26222782
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

points 0.40 You got 40 pts!