QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#231018 | #7647. 树哈希 | Lynkcat | 40 | 1ms | 4196kb | C++17 | 5.3kb | 2023-10-28 23:13:05 | 2023-10-28 23:13:05 |
Judging History
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!