小 S משחק עם 小 F במשחק הנקרא ״斗地主״.
小 S המסכן גילה שאינו מצליח לנצח את 小 F במשחק הקלפים, ולכן הוא רוצה להתערב מעט בתהליך ערבוב הקלפים כדי להטות אותו לטובתו.
בחפיסה יש $n$ קלפים, המסומנים מלמעלה למטה במספרים $1\sim n$. הניקוד של הקלף שמספרו $i$ הוא $f(i)$. בשאלה זו יש בדיוק שתי אפשרויות ל־$f(i)$: או $f(i)=i$ או $f(i)=i^2$.
דרך הערבוב דומה לזו שבחיי היומיום. להלן הגדרה פורמלית שלה:
תהליך הערבוב מורכב מ־$m$ סבבים, המתבצעים בזה אחר זה. בסבב הערבוב ה־$i$:
- 小 S מוציא את $A_i$ הקלפים העליונים. כך החפיסה נחלקת לשתי ערימות: הערימה הראשונה מכילה את $A_i$ הקלפים העליונים, והשנייה את $n-A_i$ הקלפים שנותרו. הסדר היחסי בתוך כל אחת מהערימות אינו משתנה. בפרט, כאשר $A_i=n$ או $A_i=0$, אחת הערימות ריקה.
- לאחר מכן ממזגים את שתי הערימות כדי ליצור ערימה שלישית חדשה. כאשר בערימה הראשונה נותרו $X$ קלפים ובשנייה נותרו $Y$ קלפים, בהסתברות $\frac{X}{X+Y}$ מוציאים את הקלף התחתון של הערימה הראשונה ומניחים אותו בראש הערימה השלישית החדשה, ובהסתברות $\frac{Y}{X+Y}$ מוציאים את הקלף התחתון של הערימה השנייה ומניחים אותו בראש הערימה השלישית החדשה.
- חוזרים על פעולה 2 עד ששתי הערימות ריקות. בכך מסתיים סבב ערבוב אחד.
מכיוון שהערבוב אקראי, 小 S אינו יכול לדעת איזה קלף בדיוק יימצא במיקום מסוים. אך הוא רוצה לשאול אתכם מהי תוחלת הניקוד של הקלף במיקום מסוים לאחר $m$ סבבי הערבוב. 小 S ישאל בסך הכול $Q$ שאלות כאלה.
קלט
קראו את הנתונים מהקובץ landlords.in.
השורה הראשונה מכילה שלושה מספרים שלמים חיוביים $n,m,\mathit{type}$: מספר הקלפים, מספר סבבי הערבוב וסוג הפונקציה $f(i)$, בהתאמה. כאשר $\mathit{type}=1$, מתקיים $f(i)=i$. כאשר $\mathit{type}=2$, מתקיים $f(i)=i^2$.
השורה הבאה מכילה $m$ מספרים שלמים, $A_1\sim A_m$.
השורה הבאה מכילה מספר שלם חיובי $Q$, מספר השאילתות של 小 S.
כל אחת מ־$Q$ השורות הבאות מכילה מספר שלם חיובי $c_i$. 小 S רוצה לדעת את תוחלת הניקוד של הקלף במיקום ה־$c_i$ מלמעלה. מובטח ש־$1\le c_i\le n$.
פלט
כתבו לקובץ landlords.out.
הדפיסו $Q$ שורות, בכל אחת מספר שלם אחד המייצג את התשובה מודולו $998\,244\,353$.
כלומר, נניח שהתשובה כשבר מצומצם היא $\frac{a}{b}$, כאשר $a,b$ זרים. הדפיסו את המספר השלם $x$ המקיים $bx\equiv a\pmod{998\,244\,353}$ וגם $0\le x<998\,244\,353$. ניתן להוכיח שמספר שלם כזה $x$ קיים ויחיד.
דוגמאות
קלט 1
4 1 1 3 1 1
פלט 1
249561090
הסבר
בהסתברות $\frac14$, הסדר הסופי מלמעלה למטה הוא $\{1,2,3,4\}$.
בהסתברות $\frac14$, הסדר הסופי מלמעלה למטה הוא $\{1,2,4,3\}$.
בהסתברות $\frac14$, הסדר הסופי מלמעלה למטה הוא $\{1,4,2,3\}$.
בהסתברות $\frac14$, הסדר הסופי מלמעלה למטה הוא $\{4,1,2,3\}$.
לכן, בסופו של דבר בהסתברות $\frac14$ הקלף הראשון הוא $4$, ובהסתברות $\frac34$ הקלף הראשון הוא $1$. לפיכך תוחלת הניקוד במיקום הראשון היא $\frac74$.
כדי לעזור לכם להבין באופן מוחשי יותר את תהליך הערבוב, הצגנו להלן את התהליך שתוצאתו $\{1,4,2,3\}$.
דוגמה 2
ראו את הקבצים landlords/landlords2.in ו־landlords/landlords2.ans בתיקיית המתחרה.
דוגמה 3
ראו את הקבצים landlords/landlords3.in ו־landlords/landlords3.ans בתיקיית המתחרה.
מגבלות והערות
לכל מקרי הבדיקה: $3\le n\le10^7$, $1\le m,Q\le5\times10^5$, $0\le A_i\le n$, $\mathit{type}\in\{1,2\}$.
המגבלות המדויקות של כל מקרה בדיקה מופיעות בטבלה הבאה:
| מקרה בדיקה | $n$ | $m$ | $\mathit{type}=$ | תכונות נוספות |
|---|---|---|---|---|
| $1$ | $\le10$ | $\le1$ | $1$ | אין |
| $2$ | $\le80$ | $\le80$ | $1$ | אין |
| $3$ | $\le80$ | $\le80$ | $2$ | אין |
| $4$ | $\le100$ | $\le5\times10^5$ | $2$ | כל ערכי $A_i$ זהים |
| $5$ | $\le10^7$ | $\le5\times10^5$ | $1$ | אין |
| $6$ | $\le10^7$ | $\le5\times10^5$ | $1$ | אין |
| $7$ | $\le10^7$ | $\le5\times10^5$ | $1$ | אין |
| $8$ | $\le10^7$ | $\le5\times10^5$ | $2$ | אין |
| $9$ | $\le10^7$ | $\le5\times10^5$ | $2$ | אין |
| $10$ | $\le10^7$ | $\le5\times10^5$ | $2$ | אין |
שימו לב: איננו מבטיחים כי $Q\le n$.
להלן ההגדרה של התוחלת $\mathbb{E}[x]$ של משתנה מקרי בדיד $X$:
נניח שהערכים האפשריים של המשתנה המקרי הבדיד $X$ הם $X_1,X_2,\ldots,X_k$, ו־$\Pr[X_1],\Pr[X_2],\ldots,\Pr[X_k]$ הן ההסתברויות ש־$X$ מקבל את הערכים המתאימים. אז תוחלת $X$ היא
$$\mathbb{E}[x]=\sum_{i=1}^{k}X_i\Pr[X_i].$$